QIP (Complexitat)
En teoria de la complexitat, la classe de complexitat QIP és la classe quàntica anàloga a la classe de complexitat IP, que és el conjunt de problemes que es poden resoldre per un sistema de demostració interactiu amb un verificador de temps polinòmic i un demostrador sense restriccions.[1][2]
De manera informal, la classe IP és el conjunt de llenguatges els quals un demostrador sense restriccions pot convèncer un verificador per acceptar si l'entrada és del llenguatge (amb molta probabilitat) i no pot convèncer-lo per acceptar si l'entrada no pertany al llenguatge (de nou, amb alta probabilitat). A IP, el verificador és una màquina com les de la classe BPP; a QIP, la comunicació entre el demostrador i el verificador és quàntica i el verificador pot realitzar operacions quàntiques. En aquest cas, el verificador és com una màquina BQP.
Relacions amb d'altres classes
[modifica]Restringint la quantitat de missatges que s'intercanvien en el protocol a com a molt k, es té la classe de complexita QIP(k). QIP i QIP(k) van ser definides per John Watrous.[3] Ell i Alexei Kitaev van provar que QIP = QIP(3), que vol dir que intercanviant com a molt 3 missatges és suficient per simular un protocol quàntic interactiu.[4]
Donat que QIP(3) és QIP, es tenen 4 classes diferents: QIP(0), que és BQP, QIP(1) que és QMA, QIP(2) i QIP.
Els mateixos investigadors van provar també que QIP està dins de la classe EXPTIME.
També es va demostrar que QIP(2) està dins de PSPACE.[5]
El 2009 es va demostrar que QIP està contingut dins de PSPACE, que prova també que QIP = IP = PSPACE, ja que es pot demostrar fàcilment que PSPACE és dins de QIP saben que IP = PSPACE.[6]
Referències
[modifica]- ↑ «Complexity Zoo:Q - Complexity Zoo». Arxivat de l'original el 2015-12-22. [Consulta: 8 gener 2019].
- ↑ Watrous, John «PSPACE has 2-round quantum interactive proof systems». arXiv:cs/9901015, 27-01-1999.
- ↑ «PSPACE has constant-round quantum interactive proof systems» (en anglès). Theoretical Computer Science, 292, 3, 31-01-2003, pàg. 575–588. DOI: 10.1016/S0304-3975(01)00375-9. ISSN: 0304-3975.
- ↑ Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing : Portland, Oregon, May 21-23, [2000]. Nova York, N.Y.: ACM Press, [2000]. ISBN 1581131844.
- ↑ 50th Annual IEEE Symposium on Foundations of Computer Science, 2009 FOCS '09 ; 25 - 27 Oct. 2009, Atlanta, Georgia, USA ; proceedings. ISBN 9781424451166.
- ↑ STOC'10 : proceedings of the 2010 ACM International Symposium on Theory of Computing : June 5-8, 2010, Cambridge, MA, USA. ISBN 9781450300506.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
