Separazione BQP e PH

Question

Stavo leggendo l'articolo di Quanta qui che mostra che esiste un problema che raggiunge la "separazione oracolare tra BQP e PH". In termini semplici, esiste un problema che un computer quantistico può risolvere con molte meno chiamate a un oracolo rispetto a un computer classico (anche nel regno in cui P = NP).

Perché questo è un risultato più forte del noto algoritmo Deutsch-Jozsa per decidere se una funzione è costante o bilanciata? Anche in quel caso, un computer classico doveva fare$O(n)$chiama un oracolo (la funzione) mentre un computer quantistico potrebbe farlo con una singola query. Questo non prova che i computer quantistici siano distinti da ogni possibile computer classico, anche se P = NP?

Answer 1

Il problema Deutsch-Josza fornisce una separazione oracolare tra $\mathsf{EQP}$ (tempo quantistico-polinomiale esatto) e $\mathsf{P}$, ma non c'è alcuna preclusione contro l'aggiunta di randomizzazione per ottenere un algoritmo classico efficiente.

Ad esempio, il problema Deutsch-Josza è banalmente in $\mathsf{BPP}$. Si potrebbe fare solo un piccolo numero di chiamate all'oracolo; se vedi due output diversi, sai che l'oracolo è bilanciato, ma se vedi sempre lo stesso risultato puoi concludere che l'oracolo è costante con alta probabilità.

Inoltre c'è una ragionevole congettura di derandomizzazione che $\mathsf{BPP}$ è uguale a $\mathsf{P}$. Quindi il problema Deutsch-Josza è dentro$\mathsf{P}$, modulo tale congettura di derandomizzazione.

Tuttavia, il "problema di relazione" considerato nel documento Raz-Tal e discusso nell'articolo di Quanta fornisce una separazione oracolare tra $\mathsf{BQP}$ e $\mathsf{PH}$. Questo problema di relazione non è probabile in$\mathsf{BPP}$.

Ad esempio, non puoi, con alta probabilità, eseguire il tuo oracolo con un computer classico in tempo polinomiale e quindi usare qualcosa di simile al limite di Chernoff sugli output per determinare se la distribuzione data è la distribuzione uniforme o la distribuzione di relazione.