Séparation BQP et PH

Question

Je lisais ici l' article Quanta qui montre qu'il existe un problème qui réalise "la séparation d'oracle entre BQP et PH". En termes simples, il existe un problème qu'un ordinateur quantique peut résoudre avec beaucoup moins d'appels à un oracle qu'un ordinateur classique ne le pourrait (même dans le domaine où P = NP).

Pourquoi est-ce un résultat plus fort que l'algorithme bien connu de Deutsch-Jozsa pour décider si une fonction est constante ou équilibrée? Dans ce cas aussi, un ordinateur classique devait faire$O(n)$appelle un oracle (la fonction) alors qu'un ordinateur quantique pourrait le faire avec une seule requête. Cela ne prouve-t-il pas que les ordinateurs quantiques sont distincts de tout ordinateur classique possible, même si P = NP?

Answer 1

Le problème Deutsch-Josza fournit une séparation oracle entre $\mathsf{EQP}$ (temps quantique-polynomial exact) et $\mathsf{P}$, mais il n'y a pas d'interdiction d'ajouter la randomisation pour obtenir un algorithme classique efficace.

Par exemple, le problème Deutsch-Josza est trivialement $\mathsf{BPP}$. On pourrait simplement faire un petit nombre d'appels à l'oracle; si jamais vous voyez deux sorties différentes, vous savez que l'oracle est équilibré, mais si vous voyez toujours le même résultat, vous pouvez conclure que l'oracle est constant avec une probabilité élevée.

En outre, il existe une conjecture de dérandomisation raisonnable selon laquelle $\mathsf{BPP}$ est égal à $\mathsf{P}$. Le problème Deutsch-Josza est donc en$\mathsf{P}$, modulo une telle conjecture de dérandomisation.

Cependant, le "problème de relation" considéré dans l'article de Raz-Tal et discuté dans l'article de Quanta fournit une séparation oracle entre $\mathsf{BQP}$ et $\mathsf{PH}$. Ce problème de relation est peu probable$\mathsf{BPP}$.

Par exemple, vous ne pouvez pas, avec une probabilité élevée, exécuter votre oracle avec un ordinateur classique en temps polynomial, puis utiliser quelque chose qui ressemble à la limite de Chernoff sur les sorties pour déterminer si la distribution donnée est la distribution uniforme ou la distribution de relation.