1 Востаннє редагувалося koala (18.01.2020 20:00:33)

Тема: 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-і роки, є помилковою.

(Переклад мій, дуже сподіваюся, що нічого не наплутав)

англійська, робота

https://arxiv.org/abs/2001.04383
We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages

англійська, пояснення

https://www.scottaaronson.com/blog/?p=4512
(1) There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever (!!), or indeed that a given Turing machine halts.
(2) There is a two-prover game, analogous to the Bell/CHSH game, for which Alice and Bob can do markedly better with a literally infinite amount of entanglement than they can with any finite amount of entanglement.
(3) There is no algorithm even to approximate the entangled value of a two-prover game (i.e., the probability that Alice and Bob win the game, if they use the best possible strategy and as much entanglement as they like). Instead, this problem is equivalent to the halting problem.
(4) There are types of correlations between Alice and Bob that can be produced using infinite entanglement, but that can’t even be approximated using any finite amount of entanglement.
(5) The Connes embedding conjecture, a central conjecture from the theory of operator algebras dating back to the 1970s, is false.

Квантова всемогутність дещо відкладається. Приблизно до часу винайдення класичної всемогутності з P=NP.

Подякували: wander1

2

Re: MIP*=RE

Надто заплутано. Не осилив.

3

Re: MIP*=RE

Наскільки я це все розумію, то:
- існують задачі, які не розв'язуються класичними комп'ютерами (машина Тюрінга працюватиме необмежено довго);
- ці задачі ніби мають розв'язуватися квантовими комп'ютерами;
- але неможливо довести, що квантовий комп'ютер дав правильну відповідь - проблема доведення еквівалентна розв'язанню задачі (потребує нескінченої кількості квантових заплутувань).

Подякували: leofun011