3
$\begingroup$

I was reading the Quanta article here which shows that there exists a problem which achieves "oracle separation between BQP and PH". In simple terms, there exists a problem which a quantum computer can solve with far fewer calls to an oracle than a classical computer could (even in the realm where P=NP).

Why is this a stronger result than the well-known Deutsch-Jozsa algorithm to decide if a function is constant or balanced? In that case too, a classical computer had to make $O(n)$ calls to an oracle (the function) while a quantum computer could do so with a single query. Does this not prove that quantum computers are distinct from any possible classical computer, even if P=NP?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

The Deutsch-Josza problem provides an oracle separation between $\mathsf{EQP}$ (exact quantum-polynomial time) and $\mathsf{P}$, but there's no preclusion against adding randomization to get an efficient classical algorithm.

For example, the Deutsch-Josza problem is trivially in $\mathsf{BPP}$. One could just make a small number of calls to the oracle; if you ever see two different outputs you know the oracle is balanced, but if you always see the same outcome then you can conclude that the oracle is constant with high-probability.

Further there is a reasonable derandomization conjecture that $\mathsf{BPP}$ is equal to $\mathsf{P}$. Thus the Deutsch-Josza problem is in $\mathsf{P}$, modulo such a derandomization conjecture.

However, the "forrelation problem" considered in the Raz-Tal paper and discussed in the Quanta article provides an oracle separation between $\mathsf{BQP}$ and $\mathsf{PH}$. This forrelation problem is not likely in $\mathsf{BPP}$.

For example, you can't, with high probability, run your oracle with a classical computer in polynomial time, and then use something akin to Chernoff's bound on the outputs to determine whether the given distribution is the uniform distribution or the forrelation distribution.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you comment as well on the relation between BQP and EQP? There is an old discussion here - mathoverflow.net/a/40787/144468 - but perhaps EQP is better defined now? Also, if the derandomization conjecture is true, then does it mean that the Deutsch Jozsa algorithm doesn't demonstrate any quantum advantage? $\endgroup$
    – user1936752
    Oct 15, 2020 at 15:58
  • 1
    $\begingroup$ The MO question was asked by a monster in the field, and was answered by another monster in the field; I am not going to provide any other insight, even if it's ten years on! It's just that EQP is "exact" quantum polynomial time, without having to rely on something like Chernoff's bound, while BQP allows for randomization and the Chernoff bound. Additionally Deutsch-Josza does demonstrate a quantum advantage even if derandomization conjectures were true, in the sense that DJ solves the problem with only one call to the oracle while a derandomized algorithm would need at least two calls. $\endgroup$
    – Mark Spinelli
    Oct 15, 2020 at 17:04
  • $\begingroup$ *was answered by two monsters in the field! $\endgroup$
    – Mark Spinelli
    Jul 1 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.