22. Simon's Algorithm

22.1The hidden-period problem

Simon (1994) defined the problem that finally made exponential separation concrete. Given a black box f: {0,1}ⁿ → {0,1}ⁿ promised to be 2-to-1 with a hidden period s ≠ 0 — meaning f(x) = f(y) if and only if y = x ⊕ s — find s. There is no promise of linearity, balance, or anything else; the entire input space is paired up by XOR with s. Classically this looks hard: to find s you essentially need to find a collision, two inputs mapping to the same value.

22.2Why the problem matters

Three reasons. The separation is exponential against bounded-error classical algorithms: finding a collision among 2ⁿ values needs Θ(2^{n/2}) queries by the birthday bound, and matching lower bounds hold — versus O(n) quantum queries. The historical trigger: Simon's preprint reached Peter Shor in 1994 and directly became the template for factoring; without Simon there is a good chance Shor's algorithm is discovered a decade later. The template: Simon is the first instance of the hidden subgroup problem — recover the subgroup H from a function constant and distinct on cosets of H — and its solution pattern (superposition, oracle, Fourier sampling, classical algebra) is exactly Shor's pattern.

22.3Quantum interference

Prepare the uniform superposition, query the oracle, and the input register entangles into pairs: (1/√2ⁿ)·Σ_x |x⟩|f(x)⟩ = (1/√2ⁿ)·Σ_c (|c⟩ + |c⊕s⟩)|f(c)⟩. Apply H^{⊗n} to the input register. The amplitude of outcome y carries the factor 1 + (−1)^{s·y} — the two terms of each pair interfere constructively when s·y = 0 (mod 2) and cancel completely otherwise. So the measurement distribution is uniform over the subspace {y : y·s = 0}, a set of size 2^{n−1}, and zero outside it. One query has converted the hidden period into a system of linear equations over GF(2) — each sampled y is one equation s·y = 0.

22.4Linear algebra extraction

Collect outcomes y₁, …, y_k; each satisfies s·yᵢ = 0 (mod 2). Stack them into a k×n bit matrix and solve for the kernel by Gaussian elimination over GF(2) — XOR swaps and row XORs, arithmetic mod 2. When the collected equations have rank n−1, the kernel is exactly {0, s} and s is recovered. Drawing n−1 samples gives full rank with probability Π_{j=1}^{n−1}(1−2^{−j}) ≈ 0.29; drawing a few extra samples pushes it near 1, so batch-and-repeat is the standard strategy. Total: O(n) oracle queries, O(n³) classical post-processing — against Θ(2^{n/2}) classical queries. The post-processing is the part you should implement carefully; it is where most homemade Simon implementations fail.

22.5Implementation

The full quantum step, honestly simulated for n = 3 (a 6-qubit state vector, 64 amplitudes):

import numpy as np
from functools import reduce
rng = np.random.default_rng(7)
n, s = 3, 0b101                              # hidden string s = 101
lab = rng.permutation(2 ** n)                # random value per pair {x, x^s}
f = np.array([lab[min(x, x ^ s)] for x in range(2 ** n)])
H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)
Hn = reduce(np.kron, [H] * n)                # H on the input register
psi = np.zeros(2 ** (2 * n), dtype=complex)
for x in range(2 ** n):
    psi[(x << n) | f[x]] = 1                 # |x>|f(x)> after the oracle
psi = np.kron(Hn, np.eye(2 ** n)) @ psi      # final H on the input register
p = (np.abs(psi.reshape(2 ** n, 2 ** n)) ** 2).sum(axis=1)
sup = np.where(p > 1e-12)[0]
print("support:", sup)
print("all satisfy y·s = 0:",
      all(bin(y & s).count("1") % 2 == 0 for y in sup))

Run it: the support is {0, 2, 5, 7} and every element satisfies y·s = 0 — the interference claim of 22.3, verified numerically rather than trusted.

import numpy as np
Y = np.array([[0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 1, 1]])  # sampled y's (y·s = 0)
n = 3
M, piv, r = Y.copy() % 2, [], 0
for c in range(n):
    pr = next((i for i in range(r, len(M)) if M[i, c]), None)
    if pr is None:
        continue
    M[[r, pr]] = M[[pr, r]]
    for i in range(len(M)):
        if i != r and M[i, c]:
            M[i] = (M[i] + M[r]) % 2
    piv.append(c); r += 1
basis = []
for c in range(n):
    if c not in piv:                          # free column -> kernel vector
        v = np.zeros(n, dtype=int); v[c] = 1
        for i, pc in enumerate(piv):
            if M[i, c]:
                v[pc] = 1
        basis.append(v)
print(basis)    # [array([1, 0, 1])]  ->  s = 101

22.6Connection to Shor

Frame both algorithms as the hidden subgroup problem: given f constant and distinct on cosets of a hidden subgroup H, find H. Simon solves it for H = {0, s} in the group (Z₂)ⁿ; Fourier sampling over (Z₂)ⁿ is Hadamard sampling, and the classical step is linear algebra. Shor solves it for H = rZ (multiples of the order r) in the group of integers — Fourier sampling is the QFT over a cyclic group, and the classical step is continued fractions. Same skeleton: superposition, one oracle family, Fourier sampling, algebra. Simon's algorithm appeared in October 1994; Shor's, built on its spine, weeks later.