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

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

  1. ↑ «Complexity Zoo:Q - Complexity Zoo». Arxivat de l'original el 2015-12-22. [Consulta: 8 gener 2019].
  2. ↑ Watrous, John «PSPACE has 2-round quantum interactive proof systems». arXiv:cs/9901015, 27-01-1999.
  3. ↑ «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.
  4. ↑ 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. 
  5. ↑ 50th Annual IEEE Symposium on Foundations of Computer Science, 2009 FOCS '09 ; 25 - 27 Oct. 2009, Atlanta, Georgia, USA ; proceedings. ISBN 9781424451166. 
  6. ↑ STOC'10 : proceedings of the 2010 ACM International Symposium on Theory of Computing : June 5-8, 2010, Cambridge, MA, USA. ISBN 9781450300506.