En teoría de la complejidad computacional , la clase QIP (que significa tiempo polinómico interactivo cuántico ) es el análogo en computación cuántica de la clase de complejidad clásica IP , que es el conjunto de problemas que se pueden resolver mediante un sistema de prueba interactivo con un verificador de tiempo polinomial y uno computacional. demostrador ilimitado. De manera informal, IP es el conjunto de lenguajes para los cuales un probador computacionalmente ilimitado puede convencer a un verificador de tiempo polinomial para que acepte cuando la entrada está en el idioma (con alta probabilidad) y no puede convencer al verificador para que acepte cuando la entrada no está en el idioma. (nuevamente, con alta probabilidad). En otras palabras, el probador y el verificador pueden interactuar durante muchas rondas polinomiales, y si la entrada está en el idioma, el verificador debe aceptarla con una probabilidad mayor que 2/3, y si la entrada no está en el idioma, el verificador debe rechazarla. con 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 como máximo 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 muestra que 3 mensajes son suficientes para simular una interacción cuántica de ronda polinomial. protocolo. 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 que puede resolver una máquina determinista de Turing en tiempo exponencial. [2] Luego se demostró que QIP(2) estaba contenido en PSPACE , el conjunto de problemas que puede resolver una máquina determinista de Turing en el espacio polinomial. [3] Ambos resultados fueron subsumidos por el resultado de 2009 de que QIP está contenido en PSPACE, [4] lo que también demuestra que QIP = IP = PSPACE, ya que se muestra fácilmente que PSPACE está en QIP usando el resultado IP = PSPACE .