Последствия $MIP^\ast=RE$ Относительно квантовых алгоритмов
Доказательство (ожидающей экспертной оценки) $MIP^\ast=RE$в этом препринте был провозглашен значительным прорывом. Значение этого результата рассматривается Генри Юэном (одним из авторов) в этом сообщении в блоге . Скотт Ааронсон также перечисляет некоторые из основных последствий в этом сообщении в блоге .
Для нелокальной игры ($G$), определим верхнюю грань вероятностей успеха для нерелятивистских стратегий тензорного произведения как $\omega^\ast(G)$, и верхняя грань вероятностей успеха для стратегии релятивистского коммутирующего оператора (QFT) как $\omega^{co}(G)$. Поскольку нерелятивистский QM является частным случаем QFT, ясно, что оптимальная стратегия коммутирующего оператора, по крайней мере, так же хороша, как оптимальная стратегия, основанная на тензорном произведении,$\omega^\ast(G) \le \omega^{co}(G)$.
Насколько я понимаю, сообщение Юэня является одним из последствий $MIP^\ast=RE$ существуют нелокальные игры, для которых $\omega^\ast(G) < \omega^{co}(G)$. В частности, он говорит
Должна быть игра $G$, то квантовое значение для которого отличается от значения коммутирующего оператора. Но это означает, что проблема Цирельсона имеет отрицательный ответ, и поэтому гипотеза Конна о вложении неверна.
Я понимаю, что это означает, что существует класс проблем, для которых алгоритмы, использующие методы QFT (коммутирующие операторы), имеют более высокую вероятность успеха, чем алгоритмы, использующие методы из нерелятивистской QM (тензорные произведения, формализм квантовых схем).
Первая часть моего вопроса, если это доказательство в силе :
- Делает $MIP^\ast=RE$ подразумевают, что существует набор проблем, которые можно решить более эффективно, используя математический формализм QFT (коммутирующие операторы), а не нерелятивистский формализм QM (обычные квантовые схемы)?
Если я не ошибаюсь, это, кажется, прямо следует из заявлений Юэна. Если это так, возможно ли, что существует набор нелокальных игр, для которых$\omega^\ast(G) < 0.5$ а также $\omega^{co}(G) > 0.5$? В частности, вторая часть моего вопроса:
- Делает $MIP^\ast=RE$ подразумевают, что существует (или может быть) набор проблем, которые могут быть решены с помощью коммутирующих операторов, которые не могут быть решены с помощью квантовых схем, или эта возможность ограничена универсальностью модели квантовой схемы?
РЕДАКТИРОВАТЬ: Генри Юэн создал MIP * Wiki для тех, кто заинтересован в лучшем понимании этого класса сложности или$MIP^\ast = RE$ результат.
Ответы
Я не знаю, является ли результат MIP * = RE, и в частности утверждение, что существует нелокальная игра $G$ где $\omega^*(G) \neq \omega^{co}(G)$, имеет какие-либо алгоритмические последствия для квантовых компьютеров. Здесь нужно сказать пару вещей.
Результат MIP * = RE говорит о том, какие вычислительные проблемы можно проверить с помощью нелокальных игр, в отличие от того, что можно решить с помощью нелокальных игр (во всяком случае, я не уверен, что это будет означать!). Различие между проверкой и решением заключается в следующем: в нелокальной игре мы предполагаем, что Алиса и Боб волшебным образом знают ответ на проблему (поэтому мы предполагаем, что они могут решить любую вычислительную задачу мгновенно). Их задача не в том, чтобы ее решить, а в том, чтобы доказатьклассическому верификатору с полиномиальным временем они известны ответ. Простое знание ответа на что-то не означает, что вы можете убедить кого-то еще в ответе. Могут ли Алиса и Боб использовать корреляции из структуры тензорного произведения или из структуры коммутирующих операторов, влияет на то, что они могут доказать проверяющему. MIP * = RE показывает, что с помощью корреляций тензорного произведения Алиса и Боб могут доказать, что они знают, что машина Тьюринга в конечном итоге останавливается. Этого нельзя сделать, если Алиса и Боб разделяют корреляции коммутирующих операторов; поэтому модель коммутирующего оператора отличается от модели тензорного произведения.
Второе, что я хотел упомянуть отдельно, это интересный вопрос, можно ли определить модель квантовых вычислений, которая говорит о коммутирующих операторах и бесконечномерных системах. Похоже, что Клив и др. Пытались придумать для этого модель, которую они называют моделью C * -цепи:https://arxiv.org/pdf/1811.12575.pdf. Возможно, вам это покажется интересным.