Какова связь между QMA и AM?

12

Я читал в СП Иордане, Д. Госсе, «PJ Лява -полных задачи для stoquastic гамильтонианов и матриц МарковаQMA » , что маловероятно , что .QMA⊆AM

Я был удивлен этим утверждением. Итак, каковы правильные отношения между и A M ?QMAAM

cc.complexity-theory complexity-classes quantum-computing interactive-proofs qma Зелах 02
источник
@Kaveh, ваше редактирование заголовка неверно. Слово «стохастик» было написано правильно. Такая же путаница произошла в комментариях cstheory.stackexchange.com/questions/3161/…
Алессандро
1
@Alessandro Cosentino: Я изменил его обратно на Stoquastic, спасибо.
Каве

Ответы:

22

Не известно никаких отношений между QMA и AM, и разумно предположить, что они несопоставимы.

Если окажется, что QMA содержится в AM, это будет абсолютно огромный результат в квантовой сложности. Конечно, это означало бы, что BQP находится в PH, что само по себе было бы огромным, но оно бы выходило за рамки этого - оно, безусловно, потребовало бы значительных откровений о структуре квантовых алгоритмов и квантовых сертификатов.

Сказав это, доказательства против не очень убедительны. Оракул, относительно которого QMA не содержится в AM, помог бы, и кажется, что такой результат может быть не за горами - но у нас даже этого пока нет.

Доказательство обратного сдерживания AM в QMA также будет огромным. По крайней мере, здесь у нас есть оракул, относительно которого AM не содержится в QMA (и фактически даже не содержится в PP).

Джон Уотроус
источник
Содержится ли BQP в QMA? Я спрашиваю, потому что «классический» эквивалент (BPP против NP) вообще не известен. (это из моего прочтения вашего комментария «это будет означать, что BQP находится в PH»
Суреш Венкат
5
@ Суреш: Да, это так. BQP и QMA имеют те же отношения, что и P и NP, или BPP и MA. В этих трех примерах первый класс тривиально во втором, потому что второй класс определяется как первый класс с доступом к «сертификату» или «доказательству» полиномиального размера.
Робин Котари
ну правильно. потому что BQP и QMA имеют рандомизированный элемент, в отличие от BPP и NP (ср. этот другой вопрос о связи между QMA и NP: cstheory.stackexchange.com/questions/1443/understanding-qma )
Суреш Венкат
12

Еще одна вещь, которую нужно добавить к ответу Джона:

Согласно вероятной гипотезе дерандомизации, AM = NP. В этом случае, конечно, мы бы имели AM ⊆ QMA.

Скотт Ааронсон
источник