Simon's algorithm was the exponential separation that convinced Shor, as a hidden bitwise mask, unfindable classically without exponential work, falls to a handful of quantum queries and some linear algebra.
Imagine a black box that computes a function of bit strings, so you may feed it inputs and read the outputs but not look inside. The function repeats itself under a hidden mask, so two inputs give the same output exactly when they differ by a secret string, meaning one is obtained from the other by flipping the bits where the secret has ones, and the task is to find the secret. Classically all you can do is hunt for a collision, two inputs with the same output, and the same counting that governs shared birthdays in a crowd says this costs a number of queries growing exponentially with the length of the strings.
Simon's procedure queries the box once with the register in superposition, holding every input at once, then measures in a way that asks about interference patterns across inputs rather than about any single input. Each run hands you one random linear equation the secret must satisfy, so after about as many runs as the secret has bits, followed by solving those simultaneous equations, the secret is yours.
It was the first exponential separation between quantum and classical computation for a promise problem, one whose input is guaranteed in advance to have the required structure. Its direct descendant is famous, as Shor read Simon's paper and asked what the same trick does to periods that are arithmetic rather than bitwise.
Simon's algorithm is one of the corpus's algorithm witnesses, in the family that works by querying an oracle between two layers of Hadamard gates, beside Deutsch- Jozsa and Bernstein-Vazirani. The standing disclaimer applies, as witnesses mark the scope of what the library can express and don't support the foundations.
What's proved is the per-outcome content of one round, starting from the state left after the query and a measurement of the output register, an equal superposition of the two inputs that share the observed output. Outcomes that aren't orthogonal to the secret, meaning those whose bitwise parity against the secret is odd, have probability zero, and every orthogonal outcome carries the same probability. The classical post-processing, collecting equations and solving them, is stated as the reading of the result and not re-verified.
After the oracle query and a second-register measurement, the first register is a coset state |x0> + |x0 + s>, and the Hadamard transform gives outcome y the amplitude (1/sqrt 2)^{n+1} (-1)^{<x0,y>} (1 + (-1)^{<s,y>}), which vanishes unless <s,y> = 0 mod 2 and is otherwise uniform of squared norm 2/2^n. The corpus proves both halves, as outcomes with <s,y> = 1 have probability zero (simon_orthogonal), and every outcome with <s,y> = 0 carries the same probability (simon_uniform).
So each round samples uniformly from the subspace orthogonal to s, and n - 1 independent samples determine s by linear algebra over F_2.
Daniel Simon proved the separation in 1993 while at the Universite de Montreal. The paper was initially rejected before appearing at FOCS 1994, in the same conference and the same session as Shor's factoring paper, which cites it as the trigger. Simon spent most of his subsequent career at Microsoft Research working on cryptography.
Source links are pinned to a commit, so they do not drift. The anchors above are checked mechanically against the Lean tree on every build. The mathematics is not, and cannot be: that is a human responsibility and it rests with the author.
Part of Constraint-Surface Dynamics · Formalised in csd-lean4.
Google Analytics counts visits to this page, which stores cookies in your browser. They record how the page was reached, not who you are, and nothing is passed on. Blocking cookies for this site breaks nothing here. Details.