Quantum Timeline From Feynman's idea to Quantum Supremacy

MilestoneTheory & algorithmsConfirmed

Daniel Simon finds an exponential quantum speedup that inspires Shor

Nov 1994

Computer scientist Daniel Simon presents a contrived problem, finding the hidden period of a special kind of function, that a quantum computer can solve exponentially faster than any classical probabilistic method. An earlier conference had rejected the paper, despite Peter Shor arguing for it.

Why it matters

Shor adapted Simon's period-finding approach to build his factoring algorithm, even though Simon's own problem had no obvious practical use.

Daniel Simon

See it on the timeline

Related

Sources (3)

  • Proceedings of the 35th Annual Symposium on Foundations of Computer Science (IEEE) On the power of quantum computation
    Primary sourceNov 1994
    “We present here a problem of distinguishing between two fairly natural classes of function, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class.”
  • arXiv (John Preskill) Quantum computing 40 years later
    Independent coverageJun 2021
    “Soon after, Daniel Simon showed that a quantum computer could achieve an exponential speedup in solving an idealized version of the problem of finding the period of function [6]. Though Simon’s problem had no obvious applications, it inspired Peter Shor”
  • arXiv (Peter W. Shor) The Early Days of Quantum Computation
    Independent coverageAug 21, 2022
    “I didn’t really get anywhere until I saw Dan Simon’s paper [28] where he solves a contrived problem, “Simon’s problem”, using a quantum computer algorithm that works much better than the best classical algorithm for this problem. I saw this paper because I was on the program committee for the 1994 STOC conference, where we rejected the paper (despite my arguing for it).”

Each quote above was checked automatically against the original page. Added Oct 15, 2026. Spotted an error? Tell us and we will review it.