Simon's Algorithm

Simon’s algorithm, published by Daniel Simon in 1994, solves the following problem: given a function $f: \{0,1\}^n \to \{0,1\}^n$ with the promise that there exists a secret string $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x = y$ or $x = y \oplus s$, find $s$. The algorithm uses $O(n)$ quantum queries to the function, while any classical algorithm requires $\Omega(2^{n/2})$ queries. This was the first example of an exponential quantum speedup over classical computation for a concrete (if contrived) problem.

The algorithm

1. Initialize two $n$-qubit registers to $|0^n\rangle|0^n\rangle$
2. Apply Hadamard gates to the first register: $\frac{1}{\sqrt{2^n}}\sum_x |x\rangle|0^n\rangle$
3. Apply the oracle $U_f$: $\frac{1}{\sqrt{2^n}}\sum_x |x\rangle|f(x)\rangle$
4. Measure the second register (obtaining some value $f(z)$), collapsing the first register to $\frac{1}{\sqrt{2}}(|z\rangle + |z \oplus s\rangle)$
5. Apply Hadamard gates to the first register
6. Measure the first register to obtain a string $y$

After step 5, the amplitude of $|y\rangle$ is:

$\frac{1}{\sqrt{2}} \cdot \frac{1}{\sqrt{2^n}} \left[(-1)^{y \cdot z} + (-1)^{y \cdot (z \oplus s)}\right]$

This is nonzero only when $y \cdot s = 0 \pmod{2}$, meaning the measurement always yields a string $y$ orthogonal to $s$ (in the binary inner product sense).

Repeating this procedure $O(n)$ times gives $n$ linearly independent equations $y_i \cdot s = 0$, from which $s$ can be determined by Gaussian elimination over $\text{GF}(2)$.

Complexity analysis

Approach	Query complexity
Classical deterministic	$\Theta(2^{n/2})$ (birthday bound)
Classical randomized	$\Theta(2^{n/2})$
Quantum (Simon’s)	$O(n)$

The exponential separation is in the query complexity model. The classical lower bound comes from a birthday-type argument: any classical algorithm must query enough inputs to find a collision $f(x) = f(y)$ with $x \neq y$, which requires $\Omega(2^{n/2})$ queries by the birthday paradox.

Historical significance

Simon’s algorithm is historically pivotal for two reasons:

1. It provided the first exponential quantum speedup, predating Shor’s algorithm by about a year. The speedup is proven unconditionally in the query model (no complexity-theoretic assumptions needed).

2. It directly inspired Shor’s algorithm. Shor recognized that the hidden subgroup structure in Simon’s problem had an analogue in the integers: finding the period of a function $f(x) = a^x \bmod N$ is a hidden subgroup problem over $\mathbb{Z}$, solvable using the quantum Fourier transform instead of Hadamard transforms.

This conceptual connection, from Simon’s problem over $\mathbb{Z}_2^n$ to the period-finding problem over $\mathbb{Z}$, is one of the most important intellectual threads in quantum algorithm design.

Why it matters for learners

Simon’s algorithm is the clearest demonstration of exponential quantum speedup in a setting simple enough to fully understand. It introduces the hidden subgroup problem framework, which unifies many quantum algorithms, and it shows the power of combining superposition, interference, and classical post-processing. If you understand Simon’s algorithm well, you have the conceptual foundation for understanding Shor’s algorithm.

See also

• Shor’s Algorithm
• Quantum Fourier Transform
• Deutsch-Jozsa Algorithm
• Quantum Oracle
• Quantum Speedup