Simon’s Algorithm

Overview

Simon’s algorithm is an early “period-finding” algorithm. It is historically important because it was one of the first clear examples where quantum algorithms can use interference + measurement to uncover hidden structure with dramatically fewer oracle queries than classical strategies (in the black-box model).

Problem setting:

You are given oracle access to a function

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

with the promise that there exists a secret string $s\neq 0^n$ such that:

• for every $x$, $$f(x)=f(x\oplus s),$$
• and these are the only collisions (so $f$ is 2-to-1).

Goal: find the hidden period $s$.

Intuition

The algorithm uses a very “quantum” style of information extraction:

1. Query the oracle in a superposition over all $x$.
2. Measure the output register. This doesn’t give $s$ directly, but it collapses the input into a superposition of two values that are paired by the hidden period: $$\tfrac{1}{\sqrt{2}}(|x\rangle+|x\oplus s\rangle).$$
3. Apply Hadamards to the input. This converts the “two-point structure” into a constraint on what you can measure.
4. Repeat to gather multiple constraints.
5. Solve for $s$ using classical reasoning.

The key idea: measurement gives you constraints that are consistent with $s$. After enough repeats, those constraints determine $s$.

This is entanglement and measurement used operationally:

• entanglement ties input and output,
• measuring output forces input into a structured superposition,
• interference reveals information about the hidden structure.

Algorithm Structure

High-level steps:

1. Prepare two $n$-qubit registers: input and output, starting at $|0^n\rangle|0^n\rangle$.
2. Apply $H^{\otimes n}$ to the input to create a uniform superposition over $x$.
3. Query the oracle once: $$|x\rangle|0\rangle \mapsto |x\rangle|f(x)\rangle.$$
4. Measure the output register. This collapses the input to a superposition of two inputs that share the same output.
5. Apply $H^{\otimes n}$ to the input register.
6. Measure the input register to get a bitstring $y$.
7. Repeat steps 1–6 to collect several different $y$ values.
8. Use classical post-processing to reconstruct $s$ from the collected constraints.

Formal Description

After step 2, the joint state is

$$\frac{1}{\sqrt{2^n}}\sum_x |x\rangle|0^n\rangle.$$

After the oracle:

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

Now measure the output register. Because $f$ is 2-to-1 with period $s$, observing some value $f(x_0)$ tells you the input must be either $x_0$ or $x_0\oplus s$. So the input collapses to

$$\tfrac{1}{\sqrt{2}}\big(|x_0\rangle + |x_0\oplus s\rangle\big).$$

Apply $H^{\otimes n}$. The result is a superposition where many measurement outcomes cancel. What survives are outcomes $y$ that satisfy a parity-like constraint with $s$.

A standard way to state this constraint is:

$$y\cdot s = 0 \;\;\text{(mod 2)}.$$

Interpretation (no heavy algebra):

• each measured $y$ is a bitstring that is “compatible” with the hidden period,
• collecting multiple such $y$ values gives enough information to determine $s$.

This is why Simon’s algorithm is a period-finding method: it turns a hidden XOR-period into measurable constraints.

Worked Example

Take $n=2$ and secret period $s=11$. Then the constraint $y\cdot s=0$ becomes:

$$y_1\oplus y_2 = 0,$$

meaning $y_1=y_2$. So the measured $y$ values can only be:

• $00$ or $11$.

A single run might produce $00$ (which is not very informative by itself), but repeated runs will also produce $11$. With enough samples, you can infer that the hidden period must be 11.

This example illustrates the workflow:

• each run gives a constraint-consistent sample,
• classical post-processing combines them into the secret.

Turtle Tip

Common Pitfalls

Quick Check

What’s Next

Simon’s algorithm is a bridge from simple interference tricks to deeper period-finding ideas. Next we turn to Grover-style search at a conceptual level: Grover’s algorithm uses amplitude amplification to bias measurement toward marked solutions.