Hispanopedia WikiEn la teoría de la complejidad computacional , la clase QIP (que significa Prueba Interactiva Cuántica ) es el análogo en computación cuántica de la clase de complejidad clásica IP , que es el conjunto de problemas resolubles por un sistema de prueba interactiva con un verificador de tiempo polinomial y un probador computacionalmente 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 de aceptar cuando la entrada está en el lenguaje (con alta probabilidad) y no puede convencer al verificador de aceptar cuando la entrada no está en el lenguaje (nuevamente, con alta probabilidad). En otras palabras, el probador y el verificador pueden interactuar durante un número polinomial de rondas, y si la entrada está en el lenguaje, el verificador debería aceptar con una probabilidad mayor que 2/3, y si la entrada no está en el lenguaje, el verificador debería 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 computación cuántica. 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 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 resolubles por una máquina de Turing determinista en tiempo exponencial. [ 2 ] Luego se demostró que QIP(2) está contenido en PSPACE , el conjunto de problemas resolubles por una máquina de Turing determinista en 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 .
Referencias
- ↑ Watrous, John (2003), "PSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante", Theor. Comput. Sci. , 292 (3), Essex, Reino Unido: Elsevier Science Publishers Ltd.: 575– 588, doi : 10.1016/S0304-3975(01)00375-9 , ISSN 0304-3975
- 1 2 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 la 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: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science , IEEE Computer Society, pp. 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 la ACM sobre teoría de la computación , ACM, págs. 573–582 , ISBN 978-1-4503-0050-6
Enlaces externos
- Complexity Zoo : QIP
- Clases de complejidad probabilística
- Teoría de la complejidad cuántica