Simon’s Problem

Setting the stage

Before quantum computers were expected to factor large numbers they were expected to do something more elementary: solve a hidden-structure problem in exponentially fewer queries than any classical computer. That is exactly what Simon's algorithm does, and the key to understanding it is first grasping the problem it solves.

The problem

You are given black-box (oracle) access to a function

$f : \{0,1\}^n \;\to\; \{0,1\}^n$

that satisfies a promise: there exists a secret string $s \in \{0,1\}^n$ such that for all $x, y \in \{0,1\}^n$ ,

$f(x) = f(y) \;\iff\; y = x \oplus s.$

Here $\oplus$ denotes bitwise XOR. Two cases cover every allowed $f$ :

$s = 0^n$ (the all-zeros string): $f$ is one-to-one (injective). Every input gives a distinct output.
$s \neq 0^n$ : $f$ is two-to-one. Exactly the pair $\{x,\; x \oplus s\}$ maps to the same output for every $x$ .

Goal: determine $s$ using as few queries to $f$ as possible.

Why it is hard classically

A classical algorithm must find two inputs $x \neq y$ with $f(x) = f(y)$ to identify a non-trivial $s$ , or it must check enough distinct outputs to certify that $f$ is injective. By a birthday-paradox argument, finding a collision requires $\Omega(\sqrt{2^n})$ queries in the worst case — exponential in $n$ . More carefully, any classical (even randomised) algorithm needs at least $\Omega(2^{n/2})$ queries to succeed with constant probability (de Wolf, Lecture Notes, Theorem 6.5).

Simon's promise as an HSP

Simon's problem is the simplest non-trivial instance of the Hidden Subgroup Problem (HSP). The group is $(\mathbb{Z}_2)^n$ (bit strings under XOR), and the hidden subgroup $H$ is

$H = \{0^n,\; s\} \subseteq (\mathbb{Z}_2)^n.$

When $s = 0^n$ the subgroup is trivial ( $H = \{0^n\}$ ); when $s \neq 0^n$ the subgroup has order 2. The function $f$ is constant on the cosets of $H$ and distinct across them — precisely the HSP promise applied to this abelian group.

Deutsch-Jozsa is the $n = 1$ special case: the "is $f$ constant or balanced?" question translates to "is $s = 0$ or $s = 1$ ?" Simon's problem generalises this to arbitrary $n$ , introducing the full collision structure that makes the exponential quantum speedup possible.

The quantum advantage — a preview

Simon's algorithm (covered in the next lesson) makes $O(n)$ quantum queries to $f$ and recovers $s$ with high probability. The circuit uses two $n$ -qubit registers:

Prepare the first register in a uniform superposition $\frac{1}{\sqrt{2^n}}\sum_x |x\rangle |0\rangle$ .
Query the oracle to entangle both registers: $\frac{1}{\sqrt{2^n}}\sum_x |x\rangle |f(x)\rangle$ .
Measure the second register. The post-measurement state of the first register collapses to the uniform superposition over the coset $\{x_0,\; x_0 \oplus s\}$ for some random $x_0$ .
Apply $n$ Hadamard gates to the first register. The amplitudes constructively interfere only on bit strings $y$ satisfying $y \cdot s \equiv 0 \pmod{2}$ (where $\cdot$ is the bitwise inner product). Measuring yields such a $y$ .

After $O(n)$ rounds the learner accumulates $n - 1$ linearly independent constraints $y \cdot s = 0$ over $\mathbb{F}_2$ , from which $s$ is recovered by Gaussian elimination. The total query count is $O(n)$ — exponentially fewer than the classical lower bound of $\Omega(2^{n/2})$ .

Formalising the promise

To be precise: an oracle for Simon's problem is any function $f$ satisfying the two-to-one (or injective) condition above. A quantum algorithm is allowed to call the quantum oracle $O_f : |x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$ in superposition. Classical algorithms may only evaluate $f$ on one input at a time.

The remarkable fact Simon proved in 1994 (published 1997) is that this exponential query separation is unconditional — it holds in the black-box model regardless of computational complexity assumptions. This was the first unconditional, non-trivial exponential quantum speedup and directly inspired Shor to look for an exponential speedup in the non-black-box (structured) setting, leading to the factoring algorithm.