Separación de BQP y PH

Question

Estaba leyendo el artículo de Quanta aquí que muestra que existe un problema que logra la "separación de oráculo entre BQP y PH". En términos simples, existe un problema que una computadora cuántica puede resolver con muchas menos llamadas a un oráculo de las que podría hacer una computadora clásica (incluso en el ámbito donde P = NP).

¿Por qué es este un resultado más fuerte que el conocido algoritmo de Deutsch-Jozsa para decidir si una función es constante o equilibrada? En ese caso también, una computadora clásica tuvo que hacer$O(n)$llamadas a un oráculo (la función) mientras que una computadora cuántica podría hacerlo con una sola consulta. ¿No prueba esto que las computadoras cuánticas son distintas de cualquier computadora clásica posible, incluso si P = NP?

Answer 1

El problema de Deutsch-Josza proporciona una separación de oráculo entre $\mathsf{EQP}$ (tiempo exacto del polinomio cuántico) y $\mathsf{P}$, pero no hay impedimento para agregar aleatorización para obtener un algoritmo clásico eficiente.

Por ejemplo, el problema de Deutsch-Josza es trivialmente en $\mathsf{BPP}$. Uno podría simplemente hacer una pequeña cantidad de llamadas al oráculo; si alguna vez ve dos salidas diferentes, sabe que el oráculo está equilibrado, pero si siempre ve el mismo resultado, puede concluir que el oráculo es constante con alta probabilidad.

Además, existe una conjetura de desaleatorización razonable de que $\mathsf{BPP}$ es igual a $\mathsf{P}$. As, el problema de Deutsch-Josza est en$\mathsf{P}$, módulo tal conjetura de desaleatorización.

Sin embargo, el "problema de la relación" considerado en el artículo de Raz-Tal y discutido en el artículo de Quanta proporciona una separación oráculo $\mathsf{BQP}$ y $\mathsf{PH}$. Este problema de relación no es probable en$\mathsf{BPP}$.

Por ejemplo, no puede, con alta probabilidad, ejecutar su oráculo con una computadora clásica en tiempo polinomial y luego usar algo similar al límite de Chernoff en las salidas para determinar si la distribución dada es la distribución uniforme o la distribución de relación.