3
$\begingroup$

It is often said that Simon’s algorithm provided the first example of an exponential speedup over the best known classical algorithm. However, the Deutsch-Jozsa algorithm was published before Simon’s and looks to me that it also provides an exponential speedup since it solves the problem by making a single query while in the worst case Deutsch-Jozsa needs 2^n-1 + 1 queries on a classical computer. What is the proper analysis for Deutsch-Jozsa and what kind of speedup it achieves?

$\endgroup$

1 Answer 1

6
$\begingroup$

The confusion likely stems from deciding what counts as a "classical algorithm".

The Deutsch-Jozsa algorithm (DJ) provides exponential speedup over a deterministic classical computer on determining whether a function $f$ is constant or balanced, with the promise that exactly one of these is true. However soon as you allow your classical computer to perform random sampling of $f$, and tolerate small failure probability, the quantum advantage disappears. Since random sampling is a realistic feature of classical computers, one could argue DJ does not show a true advantage over classically accessible models of computation.

Simon's algorithm, on the other hand, demonstrates exponential speedup even over probabilistic computers. More formally, Simon's provides an oracle separation between BQP (class of problems efficiently solvable by quantum computers) and BPP (class of problems efficiently solvable by classical computers).

To summarize, if "classical algorithm" is defined to include reasonable access to random sampling, then Simons is indeed the first algorithm to prove exponential quantum speedup.

$\endgroup$
2
  • 1
    $\begingroup$ I'd just add to this very good answer that contrary to Simon's algorithm, Shor's algorithm only has an exponential speedup when compared to all other known methods. It is not yet known (though it is believed) that no classical algorithm can factorize numbers in polynomial time $\endgroup$
    – Tristan Nemoz
    Commented Jun 8, 2022 at 7:08
  • $\begingroup$ @TristanNemoz Thanks for pointing this out! I am considering removing the last sentence since it may be more misleading than I intended. $\endgroup$
    – Jacob
    Commented Jun 9, 2022 at 14:27

Your Answer

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

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