QMA (Complexitat)

En teoria de la complexitat, la classe de complexitat QMA (Quantum Merlin Authur) és el conjunt dels problemes de decisió que una resposta SI es pot verificar per un prova quàntica interactiva d'un sol missatge en un temps polinòmic.

Més formalment, un llenguatge L és a QMA(c,s) si existeix un verificador quàntic en temps polinòmic V i un polinomi p(x) tal que:

• $\mathrm{\forall }x\in L$, existeix un estat quàntic $|\psi ⟩$tal que la probabilitat que V accepti l'entrada $(|x⟩,|\psi ⟩)$és més gran que c.
• $\mathrm{\forall }x\notin L$, per tots els estats quàntics $|\psi ⟩$ la probabilitat que V accepti l'entrada $(|x⟩,|\psi ⟩)$ és menor que s.

on $|\psi ⟩$té rang de tots els estats quàntics amb com a molt p(|x|) qubits.

La definició de la classe QMA és defineix igual a $\text{QMA}(2/3,1/3)$. Tot i això, les constants no son gaire importants, ja que la classe no varia per qualsevol valor de c i s sempre que c > s.

De fet, per dos polinomis qualsevol q(n) i r(n), es te:

$\text{QMA}(\frac{2}{3},\frac{1}{3})=\text{QMA}(\frac{1}{2}+\frac{1}{q(n)},\frac{1}{2}-\frac{1}{q(n)})=\text{QMA}(1-2^{-r(n)},2^{-r(n)})$

Un problema es diu que és QMA-hard, anàloga a NP-hard, si tot problema de QMA es pot reduir a ell. Un problema és a QMA-complet si és dins de QMU-hard i a QMA.

Relació amb d'altres classes

La classe QCMA (o MQA), (per Quantum Classical Merlin Arthur) és similar a QMA, però la prova ha de ser una cadena clàssica. No se sap si QMA és igual a QCMA, tot i que clarament QCMA està dins de QMA.

La classe QIP (k) (per Quantum Interactive Polynomial time (k missatges)), és una generalització de QMA on Merlin i Arthur poden comunicar-se k vegades. QMA és QIP(1). Se sap que QIP(2) és dins de PSPACE.

QIP és QIP(k) on k pot ser polinòmic en nombre de qubits. Se sap que QIP(3) = QIP i que QIP = IP = PSPACE.

QMA està relacionada amb d'altres classes de la següent forma:

$𝖯\subseteq 𝖭𝖯\subseteq 𝖬𝖠\subseteq 𝖰𝖢𝖬𝖠\subseteq 𝖰𝖬𝖠\subseteq 𝖯𝖯\subseteq 𝖯𝖲𝖯𝖠𝖢𝖤$

La primera inclusió prové de la pròpia definició de la classe NP. Les dues següents inclusions provenen del fet que el verificador es va fent més potent a cada cas. QCMA està dins de QMA, ja que el verificador pot forçar al provador que enviï una prova clàssica mesurant les proves tan aviat com arriben. El fet que QMA és dins de PP es va demostrar per Alexei Kitaev i John Watrous. Es desconeix si les inclusions son estrictes o no.