Leer sobre

¿Qué debo leer para entender este problema?

El poder de los circuitos cuánticos de pequeña profundidad. ¿Es ? En otras palabras, ¿se puede comprimir la parte "cuántica" de cualquier algoritmo cuántico a la profundidad de polylog (n), siempre que estemos dispuestos a realizar un posprocesamiento clásico en tiempo polinómico? (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 B Q P y B P P B Q N $BQP = BPP^{BQNC}$$BQP$$BPP^{BQNC}$, pero la pregunta es si hay alguna función concreta "instanciando" tal oráculo. --Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html

Esto fue conjeturado por R. Jozsa en la Sección 8 de arXiv: quant-ph / 0508124 . Si ya está familiarizado con la computación cuántica y la teoría de la complejidad cuántica, puede comenzar leyendo esa sección.

Una lectura importante es arXiv: quant-ph / 0006004 , donde Cleve y Watrous muestran que el algoritmo de Shor está en esa clase.