Тема: MIP*=RE
На arXiv.org опублікована робота з таким заголовком Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen.
Перше речення анотації: ми показуємо, що клас MIP* мов, що можуть бути вирішеними класичним верифікатором, що взаємодіє з декількома всемогутними квантовими доказчувачами спільним сплутуванням, дорівнює класу RE рекурсивно перелічених мов.
Scott Aaronson трохи роз'яснює, що:
(1) Існує протокол, за допомогою якого два заплутані доказувачі можуть переконати верифікатор поліноміального часу у відповіді на будь-яку обчислювальну проблему (!!), або ж що задана машина Тюрінга зупиниться.
(2) Існує гра з двома доказувачами, аналогічна грі Bell/CHSH, у якій Аліса і Боб можуть отримати суттєво кращий результат з буквально нескінченною кількістю заплутаностей, ніж вони можуть з будь-якою обмеженою кількістю заплутувань.
(3) Не існує алгоритму навіть для того, щоб приблизно знайти заплутане значення гри з двома доказувачами (тобто ймовірність того, що Аліса та Боб виграють гру, якщо вони використовуватимуть найкращу можливу стратегію та стільки заплутувань, скільки їм треба). Натомість ця проблема еквівалентна проблемі зупинки.
(4) Існують типи кореляцій між Алісою та Бобом, які можна створити за допомогою нескінченної кількості заплутувань, але їх навіть неможливо приблизно обчислити, використовуючи будь-яку скінчену кількість заплутувань.
(5) Гіпотеза про вбудовування Коннеса - центральне припущення теорії операторних алгебр, сформульована ще в 1970-і роки, є помилковою.
(Переклад мій, дуже сподіваюся, що нічого не наплутав)
Квантова всемогутність дещо відкладається. Приблизно до часу винайдення класичної всемогутності з P=NP.