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.
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. 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.
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.
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.
Referències
Categoria:Classes de complexitat