Simon's algorithm

Simon’s problem (1994) is the first example of a problem where the quantum algorithm is exponentially faster than the best possible classical algorithm, even if the classical algorithm uses randomness. This was a huge deal at the time — Deutsch-Jozsa’s speedup depended on insisting on zero error, but Simon’s speedup doesn’t. It’s genuine.

And historically, Simon’s algorithm is the direct ancestor of Shor’s factoring algorithm. The core idea — using the quantum Fourier transform to extract hidden periodicity — is the same in both.

The problem

You’re given $f: \{0,1\}^n \to \{0,1\}^n$ with the promise that there exists a hidden period $s \in \{0,1\}^n$, $s \neq 0$, such that:

$f(x) = f(y) \iff x = y \text{ or } x = y \oplus s$

In words: $f$ is 2-to-1, and two inputs map to the same output if and only if they differ by $s$. Your job: find $s$.

The classical lower bound

Think about how you’d approach this classically. You need to find two distinct inputs $x, y$ such that $f(x) = f(y)$ — then $s = x \oplus y$. This is essentially a collision search.

By the birthday paradox, you expect to find a collision after about $\sqrt{2^n} = 2^{n/2}$ queries. That’s still exponential in $n$. And this is actually the best classical algorithm (with or without randomness): any classical algorithm needs exponentially many queries.

The quantum algorithm

Quantum algorithm: $O(n)$ queries. That’s polynomially many — an exponential speedup, no caveats.

The structure is, again, “Hadamard, oracle, Hadamard”:

1. Initialize $2n$ qubits: $n$ “input” and $n$ “output” registers, all in $|0\rangle$.
2. Apply $H$ to each input qubit: uniform superposition on the input register.
3. Apply the oracle: $|x\rangle|0\rangle \mapsto |x\rangle|f(x)\rangle$.
4. Measure the output register. This leaves the input register in a superposition of exactly two values: $|x\rangle + |x \oplus s\rangle$ for some random $x$.
5. Apply $H$ to each input qubit.
6. Measure the input register. The measurement outcome $y$ satisfies $y \cdot s = 0 \pmod 2$.

A single run yields one linear equation in $s$ (over $\mathbb{F}_2$). Repeat the algorithm $n - 1$ times to get $n - 1$ independent linear equations, and solve the resulting linear system to find $s$.

Why it works

After step 4, the input register holds an equal superposition of the two inputs that share the measured output value:

$\frac{1}{\sqrt{2}}(|x\rangle + |x \oplus s\rangle)$

Apply $H^{\otimes n}$:

$H^{\otimes n}|x\rangle + H^{\otimes n}|x \oplus s\rangle = \frac{1}{\sqrt{2^n}} \sum_y \big((-1)^{x \cdot y} + (-1)^{(x \oplus s) \cdot y}\big) |y\rangle$

Factor the phase:

$= \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y}\big(1 + (-1)^{s \cdot y}\big) |y\rangle$

The amplitude on $|y\rangle$ is zero unless $s \cdot y = 0 \pmod 2$. So measurement always yields a $y$ orthogonal (in $\mathbb{F}_2$) to $s$. Collect $n - 1$ such $y$s, and you can solve for $s$ up to the one-dimensional null space.

Why it matters

Simon’s algorithm is the template for Shor’s factoring algorithm. Shor’s insight was: factoring a number $N$ reduces to finding the period of the function $f(x) = a^x \mod N$ for a randomly chosen $a$. The quantum Fourier transform generalizes Simon’s Hadamard trick from the group $(\mathbb{Z}/2)^n$ to $\mathbb{Z}/M$, which is exactly what you need to extract periodic structure from modular exponentiation.

Simon’s isn’t the headline algorithm, but it’s the one that convinced Shor the approach would work on a deeper problem.

What’s next

Grover’s search is the other famous quantum algorithm. It’s not exponentially faster than classical, but it gives a quadratic speedup for an enormous class of problems: unstructured search. This is the algorithm you get to actually see running in the next lesson.