Simon’s Algorithm

Simon's algorithm solves a structured search problem exponentially faster on a quantum computer than on any classical one. It was the first clear evidence of an exponential quantum speedup (Simon, 1994) and directly inspired Shor's factoring algorithm.

The problem

You are given a black-box function $f : \{0,1\}^n \to \{0,1\}^n$ that is either one-to-one or two-to-one. In the two-to-one case there is a hidden nonzero string $s \in \{0,1\}^n$ such that

$f(x) = f(y) \iff y = x \oplus s,$

where $\oplus$ denotes bitwise XOR. Your task is to find $s$ .

Classically you need $\Omega(2^{n/2})$ queries on average. Simon's quantum algorithm uses only $O(n)$ queries.

The circuit

The circuit uses $2n$ qubits: $n$ input qubits (register A) and $n$ ancilla qubits (register B).

Uniform superposition. Apply $H^{\otimes n}$ to register A.
Query the oracle. Apply $U_f$ so that $|x\rangle|0\rangle \mapsto |x\rangle|f(x)\rangle$ .
Hadamard again. Apply $H^{\otimes n}$ to register A.
Measure register A.

After step 1 the state is

$\frac{1}{2^{n/2}} \sum_{x \in \{0,1\}^n} |x\rangle|0\rangle.$

After step 2:

$\frac{1}{2^{n/2}} \sum_{x} |x\rangle|f(x)\rangle.$

Because $f$ is two-to-one with period $s$ , each output value $v$ appears for exactly the pair $x_0$ and $x_0 \oplus s$ . After the second $H^{\otimes n}$ on register A, interference ensures that every measurement outcome $y$ satisfies

$y \cdot s = 0 \pmod{2}.$

Running the circuit $O(n)$ times yields $n-1$ independent linear equations over $\mathbb{F}_2$ ; Gaussian elimination then recovers $s$ .

A concrete 2-qubit example

Take $n = 2$ and $s = 11_2$ . We need $f(x) = f(x \oplus 11)$ for all $x$ :

| $x$ | $x \oplus 11$ | $f(x)$ | |-----|---------------|--------| | 00 | 11 | 0 | | 01 | 10 | 1 | | 10 | 01 | 1 | | 11 | 00 | 0 |

A simple oracle realizing this is $f(x_1 x_0) = x_1 \oplus x_0$ . In circuit language: CNOT(0, 2) copies qubit 0 into qubit 2, then CNOT(1, 2) XORs qubit 1 into qubit 2, leaving $x_1 \oplus x_0$ in qubit 2.

After the full circuit the allowed measurement outcomes for qubits 0 and 1 must satisfy $y_1 \oplus y_0 = 0 \pmod{2}$ , i.e. only $y = 00$ and $y = 11$ can appear. Working through the algebra: the four-qubit state just before measurement is

$\frac{1}{2}\bigl(|0000\rangle + |0010\rangle + |1100\rangle - |1110\rangle\bigr),$

so each of these four basis states has probability $\tfrac{1}{4}$ .

Try it

Complete the oracle in the starter code. The grader checks the full probability distribution over all 4 qubits; the correct circuit places equal probability on $|0000\rangle$ , $|0010\rangle$ , $|1100\rangle$ , and $|1110\rangle$ (and zero everywhere else).

Run your code to see the quantum state.