QMA (Complejidad)

En teoría de la complejidad, la clase de complejidad QMA (Quantum Merlin Authur) es el conjunto de los problemas de decisión o lenguajes que una respuesta SI puede llegar a verificarse por una prueba cuántica interactiva de un solo mensaje en un tiempo polinómico (estado cuántico) ejecutado en una computadora cuántica.

De forma más formal, un lenguaje L está en QMA (c,s ) si existe un verificador cuántico en tiempo polinómico V y un polinomio p ( x ) tal que:​​

• $\forall x\in L$, existe un estado cuántico $|\psi \rangle$ tal que la probabilidad de que V acepte la entrada $(|x\rangle ,|\psi \rangle )$ sea mayor que c.
• $\forall x\notin L$, por todos los estados cuánticos $|\psi \rangle$ tal que la probabilidad de que V acepte la entrada $(|x\rangle ,|\psi \rangle )$ sea menor que s.

Donde, en este caso, $|\psi \rangle$ tiene de rango a todos los estados cuánticos con a lo sumo p(|x|) qubits .

La definición de la clase QMA se define igual a ${\mbox{QMA}}({2}/{3},1/3)$. Sin embargo, las constantes no son muy importantes, ya que la clase no varía por cualquier valor de c y s siempre que c > s. Por tanto, hay que tener en cuento esto y fijarse.

De hecho, por dos polinomios cualquieras q(n) y r(n), se tiene que:

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

Un problema se dice que es QMA-hard, análoga a NP-hard, si todo problema de QMA se puede llegar a reducir a él. De esta forma, un problema está en QMA-completo si este está dentro de QMU-hard y en QMA.

Relación con otras clases

La clase QCMA (o MQA), (para Quantum Classical Merlin Arthur) es bastante similar a QMA, pero en este caso la prueba debe de ser una cadena clásica. No se sabe si QMA es igual a QCMA, aunque sí está claro que QCMA está dentro de QMA.​

La clase QIP ( k ) (para Quantum Interactive Polynomial time (k mensajes)), es una especie de generalización de QMA donde Merlin y Arthur pueden comunicarse k veces. QMA es QIP(1). Se sabe que QIP(2) está dentro de PSPACE .​

QIP es QIP( k ) donde k puede ser polinómico en número de qubits. Se sabe que QIP(3) = QIP y que QIP = IP = PSPACE .​​

La clase de complejidad QMA está relacionada con otras clases de la siguiente forma:

${\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {QCMA}}\subseteq {\mathsf {QMA}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}}$

La primera inclusión que se puede apreciar en la imagen proviene de la propia definición de la clase NP. Las dos siguientes inclusiones proceden de que el verificador se va haciendo cada vez más potente en cada caso. QCMA está dentro de QMA, ya que el verificador puede llegar a forzar al probador que envíe una prueba clásica midiendo las pruebas tan pronto como lleguen. El hecho de que QMA está dentro de PP se demostró por los físicos Alexei Kitaev y John Watrous. Por último, cabe mencionar que se desconoce si las inclusiones son siempre estrictas o si es el caso de que no.