QMA (Complexitat)

En teoria de la complexitat, la classe de complexitat QMA (Quàntum Merlin Authur) és el conjunt dels problemes de decisió o llenguages que una resposta SI pot aplegar a verificar-se per una prova quàntica interactiva d'un sol mensage en un temps polinòmic (estat quàntic) eixecutat en una computadora quàntica.

De forma més formal, un llenguage L està en QMA (c,s) si existix un verificador quàntic en temps polinòmic V i un polinomi p (x) tal que:

• $\mathrm{\forall }x\in L$, existix un estat quàntic $|\psi ⟩$ tal que la provabilitat de que V accepte l'entrada $(|x⟩,|\psi ⟩)$ siga major que c.
• $\mathrm{\forall }x\notin L$, per tots els estats quàntics $|\psi ⟩$ tal que la provabilitat de que V accepte l'entrada $(|x⟩,|\psi ⟩)$ siga menor que s.

A on, en este cas, $|\psi ⟩$ té de ranc a tots els estats quàntics en com a molt p(|x|) qubits.

La definició de la classe QMA es definix igual a $\text{QMA}(2/3,1/3)$. No obstant, les constants no són molt importants, ya que la classe no varia per qualsevol valor de c i s sempre que c > s. Per tant, cal tindre en conte açò i fixar-se.

De fet, per dos polinomis cualquieras q(n) i r(n), es té que:

$\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 aplegar a reduir a ell. D'esta forma, un problema està en QMA-complet si este està dins de QMU-hard i en QMA.

Relació en atres classes

La classe QCMA (o MQA), (per a Quàntum Classical Merlin Arthur) és prou similar a QMA, pero en este cas la prova deu ser una cadena clàssica. No se sap si QMA és igual a QCMA, encara que sí està clar que QCMA està dins de QMA.

La classe QIP (k) (per a Quàntum Interactive Polynomial clave (k mensages)), és una espècie de generalisació de QMA a on Merlin i Arthur poden comunicar-se k voltes. QMA és QIP(1). Se sap que QIP(2) està dins de PSPACE.

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

La classe de complexitat QMA està relacionada en atres classes de la següent forma:

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

La primera inclusió que es pot apreciar en l'image prové de la pròpia definició de la classe NP. Les dos següents inclusions procedixen de que el verificador es va fent cada volta més potent en cada cas. QCMA està dins de QMA, ya que el verificador pot aplegar a forçar al provador que envie una prova clàssica medint les proves tan pronte com apleguen. El fet de que QMA està dins de PP es va demostrar pels físics Alexei Kitaev i John Watrous. Per últim, cal mencionar que es desconeix si les inclusions són sempre estrictes o si és el cas de que no.