Separaciones oraculares entre circuitos cuánticos de profundidad poli y logarítmica

16

El siguiente problema aparece en la lista de Aaronson Diez desafíos grandes para la teoría de la computación cuántica .

Es siQPAG=siPAGPAGsiQnorteC En otras palabras, ¿se puede comprimir la parte "cuántica" de cualquier algoritmo cuántico a profundidad de pagolylosol(norte) , siempre que estemos dispuestos a hacer polinomios? tiempo postprocesamiento clásico? (Se sabe que esto es cierto para el algoritmo de Shor.) Si es así, ¡construir una computadora cuántica de propósito general sería mucho más fácil de lo que generalmente se cree! Por cierto, no es difícil dar una separación de oráculo entre siQPAG y siPAGPAGsiQnorteC , pero la pregunta es si hay alguna función concreta "instanciando" tal oráculo.

Jozsa ha conjeturado que la respuesta a la pregunta es sí en el "modelo de computación cuántica basado en la medición": donde se permiten mediciones locales, puertas locales adaptativas y posprocesamiento clásico eficiente. Consulte también esta publicación relacionada .

Cuestión . Me gustaría saber sobre las separaciones oraculares actualmente conocidas entre estas clases (o, al menos, la separación del oráculo a la que se refiere Aaronson).

Juan Bermejo Vega
fuente
55
Supongo que el problema de los árboles pegados es un buen candidato para la separación. La intuición es que una computadora clásica es esencialmente inútil para esta tarea, y un circuito cuántico de profundidad de polylog solo puede alcanzar polylog profundamente en los árboles pegados, pero debe alcanzar el vértice de salida que está polinómicamente lejos del vértice de entrada.
Robin Kothari

Respuestas:

12

siQPAGsiPAGPAGsiQnorteC

Scott Aaronson
fuente
1
Ya veo, gracias Scott. Bueno, personalmente me gusta esto BQP = BPP ^ BQNC? pregunta, debido a su importancia para construir computadoras cuánticas. Creo que debería valer la pena darle uno o dos pensamientos.
Juan Bermejo Vega
1
Esta pregunta parece haberse resuelto: ver arXiv: 1909.10303 y arXiv: 1909.10503 .
Sanketh Menda