Si P = BQP, ¿esto implica que PSPACE (= IP) = AM?

Recientemente, Watrous et al probaron que QIP (3) = PSPACE es un resultado notable. Este fue un resultado sorprendente para mí por decir lo menos y me hizo pensar ...

Me preguntaba qué pasaría si las computadoras cuánticas pudieran ser simuladas eficientemente por computadoras clásicas. ¿Podría esto estar SIMPLEMENTE relacionado con la división entre IP y AM? Lo que quiero decir es que IP se caracteriza por un número polinómico de rondas de interacción clásica, mientras que AM tiene 2 rondas de interacción clásica. ¿La simulación de una Computación Cuántica podría reducir la cantidad de interacción para IP de polinomio a un valor constante?

Gran pregunta! Respuesta corta: no se conoce ninguna implicación como ; pero eso no significa que no valga la pena intentar probar ...

Sin embargo, diría que encontrar esa implicación parece poco probable. Creo que el mensaje de la teoría de la complejidad cuántica es que, si bien las computadoras cuánticas no son una panacea de uso múltiple para resolver problemas difíciles, pueden ser mucho más poderosas que las computadoras clásicas en ciertas circunstancias específicas.

Por ejemplo, en la complejidad de las consultas, los algoritmos cuánticos pueden resolver eficientemente ciertos problemas que los clásicos probablemente no pueden, cuando se promete que la entrada obedecerá a una buena estructura global. Por ejemplo, el algoritmo de Shor se basa en un algoritmo para encontrar rápidamente el período desconocido de una función prometida para ser periódica. Por otro lado, los algoritmos de consulta cuántica no son demasiado fuertes que los clásicos para resolver problemas en los que no se supone una estructura especial en la entrada. (Ver la encuesta de Buhrman y de Wolf sobre la complejidad de las consultas para este último punto).

Del mismo modo, creo que los resultados nos dicen que la interacción no es inesperadamente débil (incluso si P = B Q P ), sino que el cálculo cuántico es inesperadamente fuerte,específicamenteen el contexto de interacción con probadores computacionalmente ilimitados.$\mathsf{QIP}(3) = \mathsf{QIP} = \mathsf{IP}$$\mathsf{P} = \mathsf{BQP}$

Estoy de acuerdo con lo que Andy ha escrito y quería que esta "respuesta" fuera un comentario a su respuesta, pero evidentemente es demasiado largo para un comentario ...

De todos modos, puede ser útil decir algo más sobre qué aspecto de la computación cuántica (o tal vez la información cuántica) permite probar la contención de PSPACE en QIP (3). Las pruebas conocidas de esta contención no se derivan de la capacidad del verificador para calcular funciones que resultan ser computables en tiempo polinómico cuántico. Una explicación más precisa es que las pruebas hacen uso de las formas específicas en que un probador puede manipular estados cuánticos enredados que comparte con el verificador. Si el probador no fuera capaz de manipular la información cuántica, o si de alguna manera pudiera manipular mágicamente los estados entrelazados compartidos de una manera más fuerte de lo que permite la teoría de la información cuántica, las pruebas no funcionarían.

Entonces, en mi opinión, la contención de PSPACE en QIP (3) no dice nada sobre la relación entre AM y PSPACE.

Las respuestas de John Watrous y Andy Drucker son excelentes para comprender algunos de los problemas involucrados.

Solo agregaré a la respuesta de Andy que, no solo no se conoce tal implicación, sino que mostrar tal implicación requiere técnicas no relativizadoras (de las cuales esencialmente solo se conoce una - aritmetización). Lance Fortnow y John Rogers [1] construyeron un oráculo donde pero P H es infinito (y en particular eso significa P S P A C E ⊇ P $P = BQP$$PH$$PSPACE \supseteq PH \supset\neq AM$

$IP = PSPACE$

[1] L. Fortnow y J. Rogers. Limitaciones de complejidad en la computación cuántica . Journal of Computer and System Sciences, 59 (2): 240-252, 1999. Número especial para trabajos seleccionados de la 13ª Conferencia IEEE sobre Complejidad Computacional. También disponible aquí .

Las otras respuestas son excelentes, y esto no pretende reemplazar o contradecir ninguna de ellas, simplemente ofrecer una intuición de por qué P = BQP no necesariamente implica igualdad entre los sistemas de prueba interactivos cuánticos y clásicos (para rondas fijas, etc.). Sin embargo, ahora sabemos que QIP = IP gracias al trabajo de Jain, Ji, Upadhyay y Watrous, por lo que ciertamente no estoy tratando de afirmar que tales igualdades nunca sucedan.

Si solo asumimos que P = BQP, entonces aprendemos algo solo sobre qué problemas de decisión pueden ser respondidos por los modelos cuánticos y clásicos. No es lo mismo que implicar que los modelos son en realidad los mismos. La principal diferencia es que las computadoras cuánticas pueden procesar estados en superposición, lo que significa que su entrada y salida no necesita restringirse a los estados clásicos. Esta es una diferencia muy importante entre los modelos cuánticos y clásicos, ya que la entrada / salida cuántica permite consultar oráculos con superposiciones de estados clásicos o comunicar estados cuánticos (que pueden tener descripciones clásicas exponenciales) entre un verificador y un probador. De hecho, existen oráculos que separan BQP de P, y la comunicación cuántica conduce a una complejidad de comunicaciones reducida para una serie de problemas. Así,

Por esta razón, la pregunta de si P = BQP no es el factor decisivo para determinar si los modelos cuánticos y clásicos son iguales en situaciones que utilizan consultas de comunicación / oráculo.