Simon's algorithm

In plain terms

Here is the problem. A black-box function repeats itself under a hidden bitwise mask: two inputs collide exactly when they differ by a secret string s. Find s. Classically all you can do is hunt for a collision, and birthday arithmetic says that costs exponentially many queries.

Simon's procedure queries the box once in superposition, then measures in the Hadamard basis. Each run hands you one random linear equation that the secret must satisfy. About n runs, one Gaussian elimination, and s is yours.

It was the first exponential quantum-classical separation for a promise problem, and its direct descendant is famous: Shor read Simon's paper and asked what the same trick does to periods that are arithmetic rather than bitwise.

In CSD

One of the corpus's algorithm witnesses (the Hadamard-oracle family, beside Deutsch-Jozsa and Bernstein-Vazirani), with the standing disclaimer: witnesses mark scope, they do not support foundations.

What is proved is the per-outcome content of one round on the coset state: outcomes not orthogonal to the secret have probability zero (simon_orthogonal), and every orthogonal outcome carries the same probability (simon_uniform). The classical post-processing -- collecting equations and solving -- is stated as the reading, not re-verified.

Mathematically

After the oracle query and a second-register measurement, the first register is a coset state |x0> + |x0 + s>; 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.

So each round samples uniformly from the subspace orthogonal to s; n - 1 independent samples determine s by linear algebra over F_2.

The name

Daniel Simon proved the separation in 1993 while at the Universite de Montreal; the paper was initially rejected before landing at FOCS 1994 -- the same conference, 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.