Vés al contingut

QIP (Complexitat)

De la Viquipèdia, l'enciclopèdia lliure

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]