Simon's problem: a black-box function f : {0,1}n → {0,1}n hides a secret string s ≠ 0 such that f(x) = f(x ⊕ s) for every x, and is otherwise injective. Classically, finding s needs Ω(2n/2) queries (birthday-bound collision search). The quantum algorithm needs only O(n).
Circuit: |0⟩ⁿ --H⊗ⁿ--•--H⊗ⁿ-- measure
|
|0⟩ⁿ --------U_f
After the oracle and second Hadamard layer, the
measured register collapses to y with:
P(y) = 1/2ⁿ⁻¹ if y·s ≡ 0 (mod 2)
P(y) = 0 otherwise
(interference cancels every y not orthogonal to s)
Each valid measurement y gives one linear constraint y·s ≡ 0 over GF(2). This simulator samples y honestly from that exact distribution using a hidden secret, and maintains a GF(2) linear basis (XOR-basis) of the equations collected — the bars below are every nonzero n-bit candidate for s, and a candidate's bar collapses to zero the moment it fails a new constraint. Once the basis reaches rank n − 1, exactly one nonzero candidate survives — that is s, recovered by solving the linear system, no further search needed.
- n slider — register width; the candidate space is 2n − 1 nonzero strings.
- New Hidden Secret — picks a fresh random nonzero s and resets everything (n stays).
- Query Oracle — one real quantum measurement sample y from P(y) above; y = 0 carries no information, exactly as in a real device.
- Auto-query — repeats queries automatically until the candidate space collapses to one survivor.
- GF(2) Reduced Basis — the row-echelon XOR-basis built from independent equations so far, one row per leading bit position; this is the actual linear system being solved for s.
Real-world relevance: Simon's algorithm was the first proof that a quantum computer gives an *exponential* query-complexity separation over any classical algorithm, and its period-finding structure directly inspired the quantum Fourier transform trick used in Shor's factoring algorithm.