Класс QMA

В теории сложности, QMA (от англ. Quantum Merlin Arthur) — это квантовый аналог NP в классической теории сложности и аналог MA в вероятностной. Он связан с BQP также, как NP связан с P, или MA связан с BPP.

Неформально — это множество языков для принадлежности к которым есть полиномиальное квантовое доказательство, принимаемое полиномиальным по времени квантовым алгоритмом с высокой вероятностью.

Определение

Язык L принадлежит [math]\displaystyle{ \mbox{QMA}(c,s) }[/math] если существует полиномиальный по времени квантовый алгоритм V и многочлен p(x) такой, что:

• [math]\displaystyle{ \forall x \in L }[/math], существует квантовое состояние [math]\displaystyle{ |\psi\rangle }[/math] такое, что вероятность того, что V примет [math]\displaystyle{ (|x\rangle, |\psi\rangle) }[/math] больше чем [math]\displaystyle{ c }[/math].
• [math]\displaystyle{ \forall x \notin L }[/math], для любого квантового состояния [math]\displaystyle{ |\psi\rangle }[/math], вероятность того, что V примет [math]\displaystyle{ (|x\rangle, |\psi\rangle) }[/math] меньше чем [math]\displaystyle{ s }[/math].

где [math]\displaystyle{ |\psi\rangle }[/math] квантовое состояние с p(x) кубитами.

Класс [math]\displaystyle{ \mbox{QMA} }[/math] определим как класс равный [math]\displaystyle{ \mbox{QMA}({2}/{3},1/3) }[/math]. На самом деле константы не важны и класс не изменится, если [math]\displaystyle{ c }[/math] и [math]\displaystyle{ s }[/math] произвольные константы такие, что [math]\displaystyle{ c }[/math] больше [math]\displaystyle{ s }[/math]. Также для любых многочленов [math]\displaystyle{ q(n) }[/math] и [math]\displaystyle{ r(n) }[/math], верно

[math]\displaystyle{ \mbox{QMA}\left(\frac{2}{3},\frac{1}{3}\right) =\mbox{QMA}\left(\frac{1}{2}+\frac{1}{q(n)},\frac{1}{2}-\frac{1}{q(n)}\right)=\mbox{QMA}(1-2^{-r(n)},2^{-r(n)}) }[/math].

Связанные классы

[math]\displaystyle{ \mbox{QCMA} }[/math] (или [math]\displaystyle{ \mbox{MQA} }[/math]) название читается как квантовый классический Мерлин Артур (или Мерлин Квантовый Артур), является аналогом QMA, но доказательство (присылаемое Мерлином) должно быть обычной строкой. Неизвестно совпадают ли QMA и QCMA.

[math]\displaystyle{ \mbox{QIP}(k) }[/math] — это класс языков распознаваемых квантовыми интерактивными протоколами с полиномиальным временем и k раундами, является обобщением QMA в котором разрешается передавать не одно сообщение, а k. Из определения следует, что QMA совпадает с QIP(1). Про QIP(2) известно, что он содержится в PSPACE.

[math]\displaystyle{ \mbox{QIP} }[/math] — это класс языков из QIP(k), где k разрешается быть полиномиальным от числа кубит. Известно, что QIP(3) = QIP. Так же известно, что QIP = IP.

[math]\displaystyle{ \mbox{QMA}_1 }[/math] — это класс языков принимаемых квантовым протоколами Мерлин Артур с идеальной полнотой.

Отношения с другими классами

Про QMA известно, что

[math]\displaystyle{ \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{MA} \subseteq \mbox{QCMA} \subseteq \mbox{QMA}\subseteq \mbox{PP} \subseteq \mbox{PSPACE} }[/math]

Первое вложение следует из определения NP. Следующие два включения верны из-за того, что верифаеры становятся более сильными. Утверждение о том, что QMA содержится в PP был доказан Алексеем Китаевым и Джоном Ватрусом. PP также содержится в PSPACE.

Неизвестно какие из этих включений строгие.

Литература

• «Algorithms for quantum computation: discrete logarithms and factoring» P.W. Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Ссылки

• А. Х. Шень, М. Н. Вялый, Курс лекций «Классические и квантовые вычисления». Лекция 8: Определение квантового вычисления. Примеры // Интуит.ру, 15.03.2007