En la teoría de la complejidad computacional , la clase QIP (que significa Prueba Interactiva Cuántica ) es el análogo de computación cuántica de la clase de complejidad clásica IP , que es el conjunto de problemas solucionables por un sistema de prueba interactivo con un verificador de tiempo polinomial y un demostrador computacionalmente ilimitado. Informalmente, IP es el conjunto de lenguajes para los cuales un demostrador computacionalmente ilimitado puede convencer a un verificador de tiempo polinomial para que acepte cuando la entrada está en el lenguaje (con alta probabilidad) y no puede convencer al verificador para que acepte cuando la entrada no está en el lenguaje (de nuevo, con alta probabilidad). En otras palabras, el demostrador y el verificador pueden interactuar durante polinomialmente muchas rondas, y si la entrada está en el lenguaje, el verificador debe aceptar con una probabilidad mayor que 2/3, y si la entrada no está en el lenguaje, el verificador debe rechazar con una probabilidad mayor que 2/3. En IP, el verificador es como una máquina BPP . En QIP, la comunicación entre el probador y el verificador es cuántica, y el verificador puede realizar cálculos cuánticos. En este caso, el verificador es como una máquina BQP .
Al restringir el número de mensajes utilizados en el protocolo a un máximo de k , obtenemos la clase de complejidad QIP(k). QIP y QIP(k) fueron introducidos por John Watrous [1] , quien junto con Kitaev demostró en un artículo posterior [2] que QIP = QIP(3), lo que demuestra que 3 mensajes son suficientes para simular un protocolo interactivo cuántico de ronda polinomial. Dado que QIP(3) ya es QIP, esto deja 4 clases posiblemente diferentes: QIP(0), que es BQP , QIP(1), que es QMA , QIP(2) y QIP.
Kitaev y Watrous también demostraron que QIP está contenido en EXP , la clase de problemas solucionables por una máquina de Turing determinista en tiempo exponencial. [2] Luego se demostró que QIP(2) estaba contenido en PSPACE , el conjunto de problemas solucionables por una máquina de Turing determinista en el espacio polinomial. [3] Ambos resultados fueron subsumidos por el resultado de 2009 de que QIP está contenido en PSPACE, [4] que también prueba que QIP = IP = PSPACE, ya que se demuestra fácilmente que PSPACE está en QIP usando el resultado IP = PSPACE .