QMA

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории сложности, QMA — это квантовый аналог 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.

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

Примечания[править | править вики-текст]

  1. Dorit Aharonov & Tomer Naveh (2002), "Quantum NP - A Survey", arΧiv:quant-ph/0210077v1 [quant-ph] 
  2. 1 2 John Watrous (2008), "Quantum Computational Complexity", arΧiv:0804.3401v1 [quant-ph] 
  3. 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. (2003) «PSPACE has constant-round quantum interactive proof systems». Theor. Comput. Sci. (Elsevier Science Publishers Ltd.) 292 (3): 575–588. DOI:10.1016/S0304-3975(01)00375-9. ISSN 0304-3975.
  5. 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

Ссылки[править | править вики-текст]