From Wikipedia, the free encyclopedia
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:[1][2]
on 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 . 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:
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.
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.[2]
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.[3]
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.[4][5]
QMA està relacionada amb d'altres classes de la següent forma:
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.