Separação BQP e PH
Eu estava lendo o artigo do Quanta aqui que mostra que existe um problema que atinge a "separação do oráculo entre BQP e PH". Em termos simples, existe um problema que um computador quântico pode resolver com muito menos chamadas para um oráculo do que um computador clássico poderia (mesmo no reino onde P = NP).
Por que este é um resultado mais forte do que o conhecido algoritmo de Deutsch-Jozsa para decidir se uma função é constante ou balanceada? Nesse caso também, um computador clássico teve que fazer$O(n)$chamadas para um oráculo (a função) enquanto um computador quântico poderia fazer isso com uma única consulta. Isso não prova que os computadores quânticos são distintos de qualquer computador clássico possível, mesmo se P = NP?
Respostas
O problema Deutsch-Josza fornece uma separação oráculo entre $\mathsf{EQP}$ (tempo polinomial quântico exato) e $\mathsf{P}$, mas não há obstáculo contra a adição de randomização para obter um algoritmo clássico eficiente.
Por exemplo, o problema Deutsch-Josza é trivial em $\mathsf{BPP}$. Pode-se fazer apenas um pequeno número de chamadas para o oráculo; se você vir duas saídas diferentes, saberá que o oráculo está balanceado, mas se você sempre vir o mesmo resultado, pode concluir que o oráculo é constante com alta probabilidade.
Além disso, há uma conjectura de desrandomização razoável de que $\mathsf{BPP}$ é igual a $\mathsf{P}$. Assim, o problema Deutsch-Josza está em$\mathsf{P}$, módulo de tal conjectura de desregulamentação.
No entanto, o "problema de relação" considerado no artigo Raz-Tal e discutido no artigo Quanta fornece uma separação oráculo entre $\mathsf{BQP}$ e $\mathsf{PH}$. Este problema de relação não é provável em$\mathsf{BPP}$.
Por exemplo, você não pode, com alta probabilidade, executar seu oráculo com um computador clássico em tempo polinomial e então usar algo semelhante ao limite de Chernoff nas saídas para determinar se a distribuição dada é a distribuição uniforme ou a distribuição de relação.