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

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

Про 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. ↑ John Watrous (2008), "Quantum Computational Complexity", arΧiv:0804.3401v1 [quant-ph] 

Литература

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

Ссылки

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

Классы сложности алгоритмов

 

Cчитаются лёгкими	P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными	NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными	EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов

Связать^?

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