Deutsch–Jozsa gave us a clean win, but a slightly unfair one: a clever random classical algorithm can also settle constant-vs-balanced in a couple of tries, so the exponential gap only holds against players who demand certainty. Simon's algorithm is where the gloves come off. It solves a problem that stays exponentially hard even for a randomised classical computer allowed to guess — and the quantum machine cracks it with only about n queries. This was the first proof that a quantum computer can be exponentially faster than any classical strategy, and its recipe — use interference to expose a hidden period, then finish with ordinary linear algebra — is the exact blueprint Shor would later turn on the security of the internet.

The promise: a function with a hidden XOR-mask

You are handed an oracle for a function f:\{0,1\}^n \to \{0,1\}^n together with a promise: there is a secret nonzero string s \in \{0,1\}^n such that

In words, f is two-to-one: every output is produced by exactly two inputs, and those two inputs always differ by the same hidden mask s. The mask acts like a period under XOR — walk from any x to x \oplus s and the value repeats. Your job: find s, using the oracle as few times as possible.

Classically: waiting for a collision

You never see s directly; the only way to learn anything about it is to find a collision — two inputs x \ne y with f(x)=f(y) — because then s = x \oplus y falls out immediately. But collisions are rare. You query fresh inputs and watch for a repeated output, exactly the birthday problem: among 2^n possible outputs you expect to wait until you have made about

queries before two of them coincide. That is exponential in n — and crucially, guessing at random does not help, because there is simply no structure a classical machine can see until a collision actually happens. This is what makes Simon's separation so much stronger than Deutsch–Jozsa's: it beats randomness itself.

The quantum move: sampling vectors orthogonal to s

Simon's circuit is short. Prepare two n-qubit registers in |0\rangle, Hadamard the first into a uniform superposition, query the bit oracle U_f|x\rangle|0\rangle = |x\rangle|f(x)\rangle once, then measure and interfere. Step through it:

Here is the payoff. After the oracle and the bottom-register measurement, the top register sits in the two-input state \tfrac{1}{\sqrt2}\big(|z\rangle + |z\oplus s\rangle\big) for some random z. Apply H^{\otimes n} and measure. The two terms interfere, and a short amplitude calculation shows the outcome y appears with nonzero probability only when

So each run costs one oracle query and hands you a uniformly random string y that is orthogonal to s over \mathrm{GF}(2). The quantum computer cannot tell you s — but it can cheaply throw you random linear constraints on it.

Finishing with linear algebra

Collect the sampled strings y^{(1)}, y^{(2)}, \dots Each is one linear equation y^{(i)} \cdot s = 0 in the unknown bits of s, over the two-element field \mathrm{GF}(2) (where arithmetic is just XOR). Once you have gathered n-1 that are linearly independent, the system

pins s down to exactly two solutions: the all-zeros string (excluded, since s \ne 0) and the true mask. Solve it with Gaussian elimination (the same system-solving you know, run mod 2), read off the nonzero solution, and you have s. The quantum part sampled; classical linear algebra finished the job.

Worked example 1: n=2, hidden s = 11

Take s = 11_2 = (1,1), so f(x) = f(x \oplus 11) — e.g. f(00)=f(11) and f(01)=f(10). Which strings y can a run produce? Only those with y \cdot s = y_1 + y_2 = 0 \pmod 2, namely

The all-zeros y=00 is a useless equation (0=0), so you keep running until you get the informative one, y = 11. With n=2 you need just n-1 = 1 independent equation:

The only nonzero solution is s_1 = s_2 = 1, i.e. s = 11. Recovered in a couple of queries — and notice the measurement could never have handed you y=01 or y=10, because those are not orthogonal to s.

Worked example 2: n=3, hidden s = 101

Now s = 101_2 = (1,0,1), so an allowed outcome must satisfy y \cdot s = y_1 \oplus y_3 = 0 \pmod 2. Suppose two successful runs return

(Check: 111 \cdot 101 = 1\oplus 1 = 0 and 010 \cdot 101 = 0 \oplus 0 = 0 — both legal.) They are linearly independent over \mathrm{GF}(2), and n-1 = 2 of them is exactly what we need. Read off the equations:

The second gives s_2 = 0; substitute into the first to get s_1 \oplus s_3 = 0, i.e. s_1 = s_3. The only nonzero solution is s = (1,0,1) = 101. Two queries' worth of constraints, one round of elimination, done.

Counting the queries

The quantum machine needs about n runs to gather n-1 independent equations (plus a handful of retries for the occasional dependent or all-zero sample). The classical machine is stuck waiting for a birthday collision. Put the two side by side:

The quantum column grows linearly; the classical one exponentially — and, unlike Deutsch–Jozsa, no amount of classical randomness closes the gap. That is the headline: a genuine, provable, exponential separation against every classical algorithm.