Simon's Algorithm

Simon's problem. Fix $n \geq 1$. You are given oracle (black-box) access to a function

(for some $m \geq n$) with the promise that there exists a secret string $s \in \{0,1\}^n$, $s \neq 0^n$, such that for all $x, y$,

Equivalently, $f$ is exactly two-to-one, and its only collisions are pairs $\{x, x \oplus s\}$. The goal is to determine $s$ using as few queries to $f$ as possible. (The case $s = 0^n$ is sometimes folded in as "$f$ is injective," but the standard promise problem assumes $s \neq 0$.)

Why this is hard classically. A classical algorithm can only learn about $f$ by evaluating it at chosen points and comparing outputs. To find $s$, you essentially need to find a collision: two distinct inputs $x, y$ with $f(x) = f(y)$. Because $f$ is otherwise injective, the "collision density" is exactly what a birthday-paradox argument controls: if you query $k$ points, the number of pairs is $\binom{k}{2}$, and each pair collides only if it happens to differ by $s$ — a $1$-in-$(2^n - 1)$ chance for uniformly random points. To get a constant probability of finding a collision, you need $k = \Theta(2^{n/2})$ queries. This is not merely a weakness of one algorithm; it is a provable information-theoretic lower bound (a standard hybrid/adversary argument shows any classical algorithm, randomized included, needs $\Omega(2^{n/2})$ queries with high probability of failure below that).

The quantum idea in one sentence. Query $f$ on a uniform superposition of all $x$, then use interference (via Hadamards) so that, upon measurement, you obtain a uniformly random $y$ satisfying the linear constraint $y \cdot s \equiv 0 \pmod 2$, where $y \cdot s = \bigoplus_i y_i s_i$ is the mod-2 inner product. This uses the same phase-kickback/Hadamard-oracle machinery that powers The Bernstein-Vazirani Algorithm, but here the function itself is unknown and structured rather than a known linear form — the quantum step reveals a constraint, not the answer. Collect roughly $n$ such constraints $y^{(1)}, \dots, y^{(n)}$ (each of the form $y^{(i)} \cdot s = 0$), treat them as a homogeneous linear system over the field $\mathrm{GF}(2)$, and solve for $s$ by Gaussian elimination. This is where linear algebra over GF(2) becomes essential: solving linear systems over the two-element field is exactly the same algorithmic exercise as over the reals, just with all arithmetic done mod 2.

The circuit

Simon's algorithm uses $n$ "input" qubits and $m$ "output" qubits (workspace for the oracle), all initialized to $|0\rangle$. The oracle is a unitary

which computes $f$ reversibly by XOR-ing the result into an ancilla register. One round of the algorithm: 1. Prepare $|0\rangle^{\otimes n} |0\rangle^{\otimes m}$. 2. Apply Hadamard $H^{\otimes n}$ to the first register, giving

3. Apply the oracle $U_f$:

4. Measure the second register. This is the crucial "collapse" step; you get some outcome $z = f(x_0)$ for the $x_0$ that produced it — but because $f$ is two-to-one, two values of $x$ map to $z$: namely $x_0$ and $x_0 \oplus s$. The first register collapses to

(You never actually need to know $z$ or $x_0$; measuring the second register is a bookkeeping step that can even be omitted, since discarding an unmeasured register that is entangled but never touched again has the same effect on the reduced state of the first register.) 5. Apply $H^{\otimes n}$ to the first register. Using the identity $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_y (-1)^{x \cdot y} |y\rangle$, the state becomes

The bracket $1 + (-1)^{s\cdot y}$ equals $2$ if $s \cdot y = 0$ and $0$ if $s \cdot y = 1$. So the amplitude survives only for $y$ with $y \cdot s \equiv 0 \pmod 2$, and the surviving amplitudes all have magnitude $\frac{1}{\sqrt{2^{n-1}}}$, i.e. the state is

6. Measure the first register in the standard basis. The outcome $y$ is uniformly random over the $2^{n-1}$-element subspace $\{y : y \cdot s = 0\}$ (the orthogonal complement of $s$ under the GF(2) inner product). Each run of steps 1–6 yields one linear equation $y \cdot s = 0$ on the unknown $s$. Run the circuit repeatedly (each time is an independent fresh query to $f$), collect equations, and solve.

Full algorithm with classical post-processing

``` Algorithm SIMON(oracle f over {0,1}^n, promise: 2-to-1 with hidden shift s or injective) equations := empty list # each entry is a bit vector in GF(2)^n repeat until equations span an (n-1)-dimensional space:

# --- quantum subroutine, one query to f --- prepare |0>^n tensor |0>^m apply H^{⊗n} to first register apply U_f : |x>|0> -> |x>|f(x)> measure second register (result discarded) apply H^{⊗n} to first register measure first register -> outcome y in {0,1}^n

# --------------------------------------------- if y != 0^n: add y to equations # constraint: y . s = 0 (mod 2)

# classical post-processing: solve the homogeneous linear system

# { y . s = 0 (mod 2) for each y in equations }

# over GF(2), using Gaussian elimination. solve for the 1-dimensional solution space of s (excluding s = 0) let s_candidate := the nonzero solution found

# verification (classical, 2 extra queries) if f(0^n) == f(s_candidate) and s_candidate != 0^n: return s_candidate # confirmed hidden shift else: return "f is injective (s = 0)" # promise resolved the other way ``` Two points deserve emphasis. First, the quantum subroutine never touches $s$ directly — it only ever hands you a random hyperplane constraint. Second, the linear system might, with some probability, fail to have full rank after $n$ rounds if the sampled $y$'s happen to be linearly dependent; the fix is simply to keep sampling until you have $n - 1$ linearly independent nonzero vectors, then solve. A short classical check ($f(0) \overset{?}{=} f(s)$) confirms the answer, since a wrong guess would fail this test with the correct $f$.

Query complexity. Each round of the quantum subroutine makes exactly one query to $U_f$. The expected number of rounds needed to accumulate $n-1$ linearly independent vectors in $\mathrm{GF}(2)^n$ (each round contributes a fresh uniformly random vector in the hyperplane $s^\perp$, which has dimension $n-1$) is $O(n)$ in expectation — this follows the same coupon-collector-style argument used for random linear codes: the probability that a new uniformly random vector in an $(n-1)$-dimensional space lands inside the span of $k < n-1$ previously collected independent vectors is at most $2^{k - (n-1)} \le 1/2$, so the expected number of "wasted" draws is bounded by a constant multiple of $n$. Hence:

Classical post-processing (Gaussian elimination on an $n \times n$ system over $\mathrm{GF}(2)$) costs $O(n^3)$ bit operations (or $O(n^{2.373})$ with fast matrix multiplication, though this is rarely the bottleneck). The total algorithm therefore runs in expected time $O(n \cdot T_f + n^3)$, using $O(n)$ oracle queries — an exponential improvement over the classical $\Omega(2^{n/2})$ query lower bound.

Classical lower bound (why the gap is real, not an artifact). Consider a classical (even randomized) algorithm that queries $f$ at points $x_1, \dots, x_k$ adaptively. As long as no two queried points collide (i.e., no $x_i \oplus x_j = s$), every observed output looks exactly like it would for an injective function — the algorithm gets zero information distinguishing "there is a hidden $s$" from "there is no collision yet." Since $s$ is unknown and effectively uniformly random over $2^n - 1$ nonzero strings (from the algorithm's point of view), the chance that any particular pair of queried points collides is about $1/(2^n-1)$, and by a union bound over the $\binom{k}{2}$ pairs, the probability of finding any collision after $k$ queries is $O(k^2 / 2^n)$. For this to be a constant, you need $k = \Omega(2^{n/2})$. This is the same birthday-bound argument that underlies collision-finding lower bounds throughout cryptography.

Correctness proof sketch (the quantum part). The key algebraic fact, proven in step 5 above, is:

This is a direct consequence of expanding both Hadamard transforms and using

which vanishes unless $s \cdot y \equiv 0$. The resulting distribution over $y$ (ignoring the irrelevant global phase $(-1)^{x_0\cdot y}$, which disappears upon computing measurement probabilities $|amplitude|^2$) is exactly uniform over the $2^{n-1}$ elements of the subspace $s^\perp = \{y : y \cdot s = 0\}$. This uniformity is essential: it guarantees that repeated independent runs behave like independent uniform draws from $s^\perp$, which is what makes the "collect $n-1$ independent vectors" argument work cleanly, rather than some biased sampling that might get stuck.

Correctness of the classical step. The set of solutions to a consistent homogeneous linear system $\{y^{(i)} \cdot s = 0\}$ over $\mathrm{GF}(2)$ forms a subspace of $\mathrm{GF}(2)^n$. If the $y^{(i)}$ span all of $s^\perp$ (dimension $n-1$), the solution space of the system has dimension exactly $n - (n-1) = 1$, so it consists of exactly $\{0^n, s\}$ — pinning $s$ down uniquely (up to knowing it's the nonzero one). This is why we insist on collecting $n-1$ linearly independent vectors: fewer than that leaves a solution space of dimension $\geq 2$, i.e. more than one nonzero candidate, and the algorithm would need to disambiguate with extra oracle calls (checking $f(0)$ vs.\ $f(\text{candidate})$ for each candidate) — still efficient, but this is why the standard analysis targets full rank $n-1$ directly.

Honesty about tradeoffs.

• The algorithm is a promise problem solver: it assumes $f$ truly has the two-to-one structure. Without that structural promise, there is no known way to beat classical brute force for generic Boolean functions — the speedup is not "quantum computers search faster in general," it is "quantum computers exploit hidden algebraic structure."
• The expected number of rounds is $O(n)$, but this is a randomized (Las Vegas–style) guarantee, not a worst-case fixed bound; a small number of "wasted" rounds (where $y$ is linearly dependent on previous ones, or $y = 0$) is expected and simply discarded.
• The oracle model hides the cost of implementing $f$ as a reversible circuit; in any real problem you must additionally show that $U_f$ itself is efficiently constructible, exactly as in the reductions used to derive Shor's algorithm from a hidden-subgroup oracle.

Take $n = 2$, so inputs and $s$ are 2-bit strings. Suppose the hidden shift is $s = 11$ and $f$ is defined (one valid choice satisfying the promise) as:

Check the promise: $f(00) = f(11) = 01$ and $00 \oplus 11 = 11 = s$ ✓. $f(01) = f(10) = 10$ and $01 \oplus 10 = 11 = s$ ✓. Good — exactly two-to-one with shift $s = 11$.

Round 1. Start with $|00\rangle|00\rangle$. Apply $H^{\otimes 2}$:

Apply $U_f$:

Measure the second register. Say the outcome is $10$. The surviving terms are those with $f(x) = 10$: $x = 01$ and $x = 10$. The first register collapses (up to normalization) to

Apply $H^{\otimes 2}$ to this state. Using $H^{\otimes 2}|x\rangle = \frac12\sum_y (-1)^{x\cdot y}|y\rangle$:

Summing and renormalizing ($\frac{1}{\sqrt2}$ times the sum, then dividing by $\frac{1}{2}\cdot\sqrt2$ overall):

Normalizing: $\frac{1}{\sqrt2}\big(|00\rangle - |11\rangle\big)$. Measuring gives $y = 00$ or $y = 11$, each with probability $1/2$. Check the theory: the surviving $y$'s should satisfy $y \cdot s = 0$ with $s = 11$. Indeed $00\cdot 11 = 0$ and $11 \cdot 11 = 1 \oplus 1 = 0$ (mod 2) — both survive, matching the two nonzero amplitudes above. ($01 \cdot 11 = 1$ and $10\cdot 11 = 1$ are correctly annihilated.) Suppose we measure $y = 11$. This gives equation: $y \cdot s = 0 \Rightarrow s_1 \oplus s_2 = 0$.

Round 2. Repeat the whole circuit independently. Suppose this time we measure $y = 00$ — this is the trivial "all-zero" outcome, which gives the equation $0 = 0$, uninformative. We discard it (it happens with probability $1/2^{n-1}$ times something — here $1/2$, since $s^\perp$ has only 2 elements when $n=2$, and $y=0$ is always one of them). We must query again.

Round 3. Independent repeat. Suppose we measure $y = 11$ again. Same equation as round 1: $s_1 \oplus s_2 = 0$. No new information — but for $n = 2$ we only need $n - 1 = 1$ independent equation, and we already had it from round 1.

Post-processing. We have the single independent equation $s_1 \oplus s_2 = 0$, i.e. $s_1 = s_2$. Over $\mathrm{GF}(2)^2$ excluding the zero vector, the solutions with $s_1 = s_2$ are $\{00, 11\}$; discarding $s = 00$ (excluded by promise), the unique candidate is

Verification. Check $f(00) \stackrel{?}{=} f(11)$: both equal $01$. ✓ Confirmed: $s = 11$, matching the planted secret. This trace shows all the moving parts: the informative equation ($y=11$), the useless equation ($y=00$, which must be filtered out and does occur with nontrivial probability), and the classical linear-algebra step that turns one bit equation into the final answer.

Simon's algorithm is rarely deployed "as is" in industry, since real-world problems seldom present a black-box function with an exact two-to-one XOR-shift promise handed to you. Its importance is structural and pedagogical: it is the cleanest demonstration that quantum query complexity can be exponentially smaller than classical query complexity, and it is the direct conceptual ancestor of Shor's algorithm. The pattern — put a register in superposition, query an oracle, use Hadamards (more generally the The Quantum Fourier Transform) to convert entanglement into interference, measure to extract linear or periodic constraints, then finish with classical number theory or linear algebra — recurs throughout the hidden subgroup problem framework that unifies factoring, discrete logarithm, and related cryptanalytic quantum algorithms. Concretely, this matters for post-quantum cryptography: RSA and Diffie–Hellman security rest on the classical hardness of factoring and discrete log, both instances of hidden subgroup problems that succumb to Simon-style quantum Fourier sampling (via Shor's algorithm). Understanding Simon's algorithm is the standard on-ramp used in quantum algorithms courses (and in NIST's own explanatory materials on post-quantum cryptography) to explain why certain cryptosystems are considered quantum-vulnerable while others (lattice-based schemes, hash-based signatures) are believed to resist this style of attack — because they lack the clean abelian hidden-shift/hidden-subgroup structure that Simon's mechanism exploits. It is also a staple benchmark for early fault-tolerant and NISQ-era quantum hardware demonstrations of "quantum advantage on a structured promise problem," precisely because its circuit is shallow and its correctness condition is easy to verify classically.

Ask the tutor: How does the hidden subgroup problem framework generalize Simon's linear-shift structure to the periodic structure Shor's algorithm exploits for factoring?