Класс QMA

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

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

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

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

${\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)})}$.

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

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

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

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

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

${\displaystyle {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{MA}}\subseteq {\mbox{QCMA}}\subseteq {\mbox{QMA}}\subseteq {\mbox{PP}}\subseteq {\mbox{PSPACE}}}$

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

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