Given a function that secretly repeats itself, how fast can you find the repeat?
These three are historically where quantum computing stopped being only physics. Each solves a promise problem: the input is guaranteed to have one of a small number of structures, and the algorithm's job is to find out which, and each does it with a query-complexity gap over any classical algorithm that can be proven outright, not benchmarked. None of them do anything commercially useful on their own; their importance is that they are the first proofs, small and completely worked, of the exact mechanism (phase kickback, then interference) that later algorithms on this site (Shor's, Grover's) scale up to problems that matter. The honest caveat, stated once here because it applies to all three: these are separations against an oracle (a black box promised to compute f, queried as a whole) not proofs that quantum computers are faster at every real problem. That is a real, provable gap in the query-complexity model, not a lesser one, but it is a different claim from separating complexity classes like P and BQP outright, which remains open.
f maps n bits to n bits, and it's promised to be exactly two-to-one in a very specific way: there is a secret nonzero string s such that f(x)=f(x⊕s) for every x, and f is injective on the rest. Every output value is hit by exactly the pair {x, x⊕s}. Finding s classically means finding a collision: querying inputs until two of them happen to produce the same output. By the birthday paradox, that takes on the order of √(2ⁿ) queries: the same reason birthday collisions in a room of people show up far sooner than "half the days in a year" naive intuition suggests, except here the exponential in n makes even the square root genuinely large.
The quantum algorithm sidesteps searching for a collision entirely. It queries f in superposition, and, without ever needing to know what s is yet. Each run hands back a random string y that is guaranteed to satisfy one linear equation: y is orthogonal to s (mod 2). Collect roughly n such equations, solve the linear system with ordinary Gaussian elimination, and out comes s. The exponential collision-search is replaced by roughly n queries plus classical linear algebra: from √(2ⁿ) down to O(n), an exponential gap, and Simon (1994) proved the classical lower bound is real: no classical algorithm, randomized or not, can do fundamentally better than the birthday bound.
Why this topic sits here rather than being a footnote: Simon's algorithm was the direct historical inspiration for Shor's. Both are "hidden subgroup" problems in different disguises (Simon's hides a period in (ℤ/2ℤ)ⁿ, Shor's factoring hides a period in ℤ/Nℤ) and the tool that generalises "measure in the Hadamard basis and get a linear constraint" into "measure in the Fourier basis and get the actual period" is the quantum Fourier transform, the next section on this page.
Start with two n-qubit registers in |0⟩⊗n|0⟩⊗n, apply H⊗n to the first register only, then Uf: |x⟩|0⟩ → |x⟩|f(x)⟩:
(1/√2ⁿ) Σₓ |x⟩|f(x)⟩
Group the sum by pairs sharing a label: for each output value, the two contributing inputs are x₀ and x₀⊕s, so this is a superposition over (1/√2n−1)Σ over representative x₀ of (|x₀⟩+|x₀⊕s⟩)|f(x₀)⟩ /√2. Applying H⊗n to the first register again and reading off the amplitude at any string y:
amplitude(y) ∝ (−1)^(x₀·y) + (−1)^((x₀⊕s)·y) = (−1)^(x₀·y) [ 1 + (−1)^(s·y) ]
The bracket is 2 if s·y=0 (mod 2) and exactly 0 otherwise, so every measured y satisfies y·s=0 (mod 2), and the distribution over such y is uniform (2n−1 equally likely strings, all consistent with s). Collecting n−1 linearly independent such y (checked via Gaussian elimination over 𝔽₂, which also detects and discards any dependent sample) determines the (n−1)-dimensional space orthogonal to s, which pins down s itself up to the one bit that y=0 alone can never resolve: resolved by one classical check, f(0)=f(candidate s)? Verified numerically over 8 random secrets s at n=3: every measured y satisfies y·s≡0 (mod 2) exactly, the measurable set is exactly the predicted 2n−1=4 strings including y=0 every time. Simon, SIAM J. Comput. 26(5), 1474 (1997; FOCS 1994).
The direct forerunner of Shor's algorithm Swap "period s under XOR" for "period r under multiplication mod N" and "Hadamard transform over (ℤ/2ℤ)ⁿ" for "quantum Fourier transform over ℤ/Nℤ", and Simon's algorithm becomes the period-finding core of Shor's algorithm: the reason RSA and ECDSA are breakable by a large enough quantum computer. The QFT (topic 11) is the piece of machinery that makes that generalisation precise rather than asserted.
Check yourself
Each run of Simon's algorithm returns a random string y. What is guaranteed about it?
Every measured y satisfies one linear equation, y dot s = 0 (mod 2). About n of them, solved by ordinary Gaussian elimination, pin s down.