Класс QMA

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

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

Определение

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

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

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

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

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

.

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

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

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

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

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

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

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

{\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.

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

Примечания

↑ Dorit Aharonov; Tomer Naveh (2002). "Quantum NP - A Survey". arXiv:quant-ph/0210077v1. {{cite arXiv}}: |class= игнорируется (справка)
↑ ¹ ² John Watrous (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].
↑ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John^[англ.]. Two-Message Quantum Interactive Proofs Are in PSPACE // FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science (англ.). — IEEE Computer Society, 2009. — P. 534—543. — ISBN 978-0-7695-3850-1.
↑ Watrous, John^[англ.]. PSPACE has constant-round quantum interactive proof systems (англ.) // Theoretical Computer Science^[англ.] : journal. — Essex, UK: Elsevier Science Publishers Ltd., 2003. — Vol. 292, no. 3. — P. 575—588. — ISSN 0304-3975. — doi:10.1016/S0304-3975(01)00375-9.
↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John^[англ.]. QIP = PSPACE // STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing (англ.). — ACM, 2010. — P. 573—582. — ISBN 978-1-4503-0050-6.

Литература

«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

[1] Dorit Aharonov; Tomer Naveh (2002). "Quantum NP - A Survey". arXiv:quant-ph/0210077v1. {{cite arXiv}}: |class= игнорируется (справка)

[JW-2] ¹ ² John Watrous (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].

[3] Jain, Rahul; Upadhyay, Sarvagya; Watrous, John^[англ.]. Two-Message Quantum Interactive Proofs Are in PSPACE // FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science (англ.). — IEEE Computer Society, 2009. — P. 534—543. — ISBN 978-0-7695-3850-1.

[4] Watrous, John^[англ.]. PSPACE has constant-round quantum interactive proof systems (англ.) // Theoretical Computer Science^[англ.] : journal. — Essex, UK: Elsevier Science Publishers Ltd., 2003. — Vol. 292, no. 3. — P. 575—588. — ISSN 0304-3975. — doi:10.1016/S0304-3975(01)00375-9.

[5] Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John^[англ.]. QIP = PSPACE // STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing (англ.). — ACM, 2010. — P. 573—582. — ISBN 978-1-4503-0050-6.

[1]

[2]

[3]

[4]

[5]