En la teoría de la complejidad computacional , la clase QIP (que significa tiempo polinomial interactivo cuántico ) es el análogo de la 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 polinómico y uno computacionalmente. probador ilimitado. De manera informal, la PI es el conjunto de idiomaspara lo cual un comprobador 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 de que acepte cuando la entrada no está en el idioma (nuevamente, con alta probabilidad). En otras palabras, el probador y el verificador pueden interactuar polinomialmente muchas rondas, y si la entrada está en el idioma, el verificador debe aceptar con una probabilidad mayor que 2/3, y si la entrada no está en el idioma, el verificador debe ser rechazado. con probabilidad mayor a 2/3. En IP, el verificador es como una máquina BPP . En QIP, la comunicación entre el comprobador 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 usados 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), que muestra que 3 mensajes son suficientes para simular un polinomio-redondo cuántico interactivo 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 de Turing determinista en tiempo exponencial. [2] Se demostró entonces que QIP (2) estaba contenido en PSPACE , el conjunto de problemas que puede resolver una máquina de Turing determinista en un 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 muestra fácilmente que PSPACE está en QIP usando el resultado IP = PSPACE .
Referencias
- ^ Watrous, John (2003), "PSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante", Theor. Computación. Sci. , Essex, Reino Unido: Elsevier Science Publishers Ltd., 292 (3): 575–588, doi : 10.1016 / S0304-3975 (01) 00375-9 , ISSN 0304-3975
- ^ a b Kitaev, Alexei; Watrous, John (2000), "Paralelización, amplificación y simulación de tiempo exponencial de sistemas de prueba interactivos cuánticos", STOC '00: Actas del trigésimo segundo simposio anual de ACM sobre teoría de la computación , ACM, págs. 608–617, ISBN 978-1-58113-184-0
- ^ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009), "Two-Message Quantum Interactive Proofs Are in PSPACE", FOCS '09: Actas del 50º Simposio anual del IEEE sobre los fundamentos de la informática de 2009 , IEEE Computer Society, págs. 534–543, ISBN 978-0-7695-3850-1
- ^ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2010), "QIP = PSPACE", STOC '10: Actas del 42º simposio de ACM sobre teoría de la computación , ACM, págs. 573–582, ISBN 978-1-4503-0050-6