A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Simon's algorithm finds a hidden period string s for a function f:{0,1}^n -> {0,1}^n satisfying f(x) = f(y) if and only if x = y or x = y xor s. Classically, finding s requires O(2n/2) queries (birthday bound). Simon's algorithm uses O(n) quantum queries, each producing a random vector orthogonal to s, and classical Gaussian elimination recovers s — achieving an exponential speedup. It was the first algorithm to prove an exponential quantum advantage over all classical algorithms (including probabilistic ones) and directly inspired Shor's factoring algorithm.
Simon's problem is the bridge between the toy oracle problems (Deutsch-Jozsa, Bernstein-Vazirani) and the practically significant quantum algorithms (Shor). You are given a black-box function f:{0,1}^n -> {0,1}^n with the promise that there exists a secret string s such that f(x) = f(y) if and only if x = y or x = y xor s. If s = 0...0, the function is one-to-one; otherwise, it is two-to-one with period s. Your task is to find s.
Classically, this is essentially a collision-finding problem. By the birthday paradox, you need O(2n/2) queries before you expect to find a collision f(x) = f(y) with x != y, from which s = x xor y. No classical algorithm — deterministic or randomized — can do substantially better. Simon's quantum algorithm uses only O(n) queries and O(n2) total time (including classical post-processing), achieving an exponential speedup.
The quantum subroutine works as follows. Prepare two n-qubit registers, both initialized to |0>^n. Apply Hadamard to the first register to create a uniform superposition. Apply the oracle to compute f into the second register, producing the state (1/sqrt(2n)) sum_x |x>|f(x)>. Now measure the second register, obtaining some value f(x_0). The first register collapses to (|x_0> + |x_0 xor s>)/sqrt(2) — a superposition of the two preimages. Apply Hadamard to the first register and measure, obtaining a random n-bit string y. The key constraint is that y dot s = 0 (mod 2): only strings orthogonal to s have nonzero amplitude after the Hadamard transform, because the two terms |x_0> and |x_0 xor s> interfere constructively only for such y.
Each run yields one random equation y dot s = 0 (mod 2). After O(n) runs, you have a system of linear equations over GF(2) that you solve by Gaussian elimination. With high probability, n-1 of these equations are linearly independent, uniquely determining s (the only nontrivial element of the null space of the constraint matrix). The total cost is O(n) quantum oracle queries plus O(n3) classical computation for Gaussian elimination — exponentially better than the classical 2n/2. Simon's algorithm established the template of quantum Fourier sampling that Shor later adapted: create a periodic quantum state, apply a Fourier transform to extract the period, and use classical post-processing to recover the answer.