Skip to content

Lesson 15: Simon's Algorithm

15.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State Simon's problem and prove the classical lower bound \(\Omega(2^{n/2})\) via the birthday argument.
  2. Derive the quantum subroutine and prove that each run yields a uniformly random \(y\) with \(y\cdot s = 0\).
  3. Assemble the full hybrid algorithm, including the classical linear solve over \(\mathbb{F}_2\).
  4. Analyse the expected number of repetitions needed to obtain \(n-1\) independent equations.
  5. Explain Simon's role as the direct inspiration for Shor's algorithm (the hidden subgroup problem).

15.2 Simon's Problem

Setup. An oracle computes \(f:\{0,1\}^n \to \{0,1\}^n\) with the promise that there exists a hidden string \(s\in\{0,1\}^n\), \(s\ne 0^n\), such that

\[ f(x) = f(z) \iff z = x \ \text{ or } \ z = x\oplus s . \]

That is, \(f\) is two-to-one and periodic with period \(s\) under XOR. (If \(s = 0^n\) the function is one-to-one; the standard version promises \(s\ne0\), and the general version asks you to determine which case holds.)

Goal. Find \(s\).

Example (\(n=3\), \(s=110\)).

\(x\) \(x\oplus s\) \(f(x)\)
000 110 101
001 111 010
010 100 000
011 101 110
100 010 000
101 011 110
110 000 101
111 001 010

Note the pairing: \(f(000)=f(110)\), \(f(001)=f(111)\), \(f(010)=f(100)\), \(f(011)=f(101)\). Each output value appears exactly twice.

15.3 The Classical Lower Bound

Strategy. The only way to learn anything about \(s\) classically is to find a collision — a pair \(x\ne z\) with \(f(x)=f(z)\) — which immediately gives \(s = x\oplus z\).

Birthday analysis. After \(k\) queries you have \(\binom{k}{2} \approx k^2/2\) pairs. Each pair collides with probability roughly \(\frac{1}{2^n - 1}\approx 2^{-n}\) (for a random \(s\)). Expected collisions:

\[ E[\text{collisions}] \approx \frac{k^2}{2}\cdot 2^{-n} . \]

For this to reach 1 we need

\[ k \approx \sqrt{2\cdot 2^{n}} = \Theta\!\left(2^{n/2}\right) . \]

Theorem (Simon, 1994). Any classical randomised algorithm solving Simon's problem with bounded error requires \(\Omega(2^{n/2})\) queries.

\[ \boxed{\ \text{Classical: } \Theta(2^{n/2}) \text{ queries — exponential, even with randomness}\ } \]

Quantum: \(O(n)\) queries.

\[ \boxed{\ \text{This is the first \emph{exponential} separation against randomised classical computation.}\ } \]

Deutsch–Jozsa's exponential gap evaporated against randomised algorithms; Simon's does not. This is precisely why Simon's algorithm — not Deutsch–Jozsa — is the true ancestor of Shor's algorithm. Peter Shor has said that reading Simon's preprint is what led him to the factoring algorithm within weeks.

15.4 The Quantum Subroutine

Circuit

Two \(n\)-qubit registers.

input  (n) : --[H]^n-------.------[H]^n----[M]^n--> y
                           |
                       [  U_f  ]
                           |
output (n) : --------------'------[M]^n---- (may be discarded)

Note: no \(|-\rangle\) ancilla here. The output register is \(n\) qubits and holds \(f(x)\), not a phase. The interference comes from the collision structure instead.

Derivation

Step 1.

\[ |\psi_1\rangle = \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle\,|0^n\rangle \]

Step 2 — query.

\[ |\psi_2\rangle = \frac{1}{\sqrt{2^n}}\sum_{x}|x\rangle\,|f(x)\rangle \]

Step 3 — measure the output register (or simply imagine measuring it; by the principle of deferred measurement the analysis is identical if we never measure it).

Suppose the outcome is some value \(f_0\). Exactly two inputs map to it: \(x_0\) and \(x_0\oplus s\). The input register collapses to

\[ |\psi_3\rangle = \frac{1}{\sqrt2}\Big(|x_0\rangle + |x_0\oplus s\rangle\Big) . \]

This two-term superposition holds the answer — but measuring now gives \(x_0\) or \(x_0\oplus s\) uniformly, and \(x_0\) is a random unknown. Individually they say nothing about \(s\). We need interference.

Step 4 — Hadamard the input register.

\[ H^{\otimes n}|\psi_3\rangle = \frac{1}{\sqrt2}\cdot\frac{1}{\sqrt{2^n}} \sum_{y}\Big[(-1)^{x_0\cdot y} + (-1)^{(x_0\oplus s)\cdot y}\Big]|y\rangle \]

Since \((x_0\oplus s)\cdot y = x_0\cdot y \oplus s\cdot y\), factor out \((-1)^{x_0\cdot y}\):

\[ = \frac{1}{\sqrt{2^{n+1}}}\sum_y (-1)^{x_0\cdot y}\Big[1 + (-1)^{s\cdot y}\Big]|y\rangle \]

Step 5 — read the interference. The bracket is

\[ 1 + (-1)^{s\cdot y} = \begin{cases} 2 & \text{if } s\cdot y = 0 \\ 0 & \text{if } s\cdot y = 1\end{cases} \]

Every \(y\) with \(s\cdot y = 1\) is destroyed by destructive interference. The surviving state is

\[ |\psi_4\rangle = \frac{1}{\sqrt{2^{n-1}}}\sum_{y \,:\, s\cdot y = 0}|y\rangle , \]

a uniform superposition over the \(2^{n-1}\) strings orthogonal to \(s\) (in the \(\mathbb{F}_2\) inner product).

Measurement therefore returns a uniformly random \(y\) satisfying

\[ \boxed{\ y \cdot s = y_1s_1\oplus y_2s_2\oplus\cdots\oplus y_ns_n = 0 \pmod 2\ } \]

Note that the unknown \(x_0\) appears only in the phase \((-1)^{x_0\cdot y}\), which does not affect probabilities. This is why the algorithm works despite \(x_0\) being random.

15.5 The Classical Post-Processing

Each quantum run gives one linear equation over \(\mathbb{F}_2\) in the unknowns \(s_1,\dots,s_n\). Collect \(n-1\) linearly independent equations and solve.

Algorithm.

1. equations = []
2. repeat:
     y = run_quantum_subroutine()
     if y is linearly independent of equations:
         append y to equations
   until len(equations) == n-1
3. Solve the homogeneous system  Y s = 0  over GF(2)  by Gaussian elimination.
4. The solution space is 2-dimensional: {0^n, s}.  Output the non-zero solution.
5. Verify: check f(0) == f(s).  If not, the promise was violated (or s = 0).

Why exactly \(n-1\) equations? The set \(\{y : y\cdot s = 0\}\) is an \((n-1)\)-dimensional subspace of \(\mathbb{F}_2^n\). With \(n-1\) independent constraints, the null space has dimension \(n - (n-1) = 1\), containing exactly two vectors: \(0^n\) and \(s\). The non-zero one is the answer.

How many runs are needed?

Theorem. The probability that \(n-1\) random vectors drawn uniformly from the \((n-1)\)-dimensional space \(s^\perp\) are linearly independent is

\[ P = \prod_{k=1}^{n-1}\left(1 - 2^{-k}\right) . \]

Why: the \(k\)-th vector must avoid the span of the previous \(k-1\), which occupies a fraction \(2^{k-1}/2^{n-1}\)... more directly, drawing the \(j\)-th vector, it must lie outside a subspace of size \(2^{j-1}\) inside a space of size \(2^{n-1}\); taking the product over \(j\) and re-indexing gives the formula above.

Numerically:

\(n\) \(P\) (all independent on the first try)
3 0.375
5 0.308
10 0.289
\(\infty\) 0.2888 (the Erdős constant)

\(P \to 0.2888\ldots\), which is bounded away from 0 — so a constant expected number of extra runs suffices. Standard analysis gives an expected total of about

\[ O(n) \ \text{queries; concretely } \approx n + 3 \text{ runs give success probability} > 3/4 . \]

Total complexity: \(O(n)\) oracle queries + \(O(n^3)\) classical time for Gaussian elimination.

15.6 Simon and the Hidden Subgroup Problem

Simon's problem is the special case \(G = (\mathbb{Z}_2)^n\) of the Hidden Subgroup Problem (HSP):

Given \(f: G\to S\) constant on cosets of an unknown subgroup \(H\le G\) and distinct on different cosets, find \(H\).

Problem Group \(G\) Hidden subgroup \(H\)
Simon \((\mathbb{Z}_2)^n\) \(\{0, s\}\)
Period finding / Shor \(\mathbb{Z}_N\) \(r\mathbb{Z}_N\)
Discrete logarithm \(\mathbb{Z}_p\times\mathbb{Z}_p\) generated by \((1,-\ell)\)
Graph isomorphism symmetric group \(S_n\) (non-abelian — still open)

All abelian HSPs are solved efficiently by the same recipe: superpose over \(G\), query \(f\), apply the Fourier transform over \(G\), measure. For Simon, the Fourier transform over \((\mathbb{Z}_2)^n\) is \(H^{\otimes n}\). For Shor, it is the QFT over \(\mathbb{Z}_N\) (L18).

Simon's algorithm and Shor's algorithm are the same algorithm over different groups. This is the single most important structural insight of Unit II.

15.7 Solved Problems

Problem 1 — Simulating the subroutine for n=3, s=110

Using the truth table in §1, suppose the output register measures \(f_0 = 000\). Write the collapsed input state, apply \(H^{\otimes3}\), and list the possible measurement outcomes.

Solution. From the table, \(f(x) = 000\) for \(x \in \{010, 100\}\). Check: \(010\oplus100 = 110 = s\) ✓.

Collapsed state: \(|\psi_3\rangle = \frac{1}{\sqrt2}\big(|010\rangle + |100\rangle\big)\).

Possible outcomes are the \(y\) with \(y\cdot s = 0\), i.e. \(y\cdot 110 = y_1\oplus y_2 = 0\), i.e. \(y_1 = y_2\):

\[ \{000,\ 001,\ 110,\ 111\} \]

Each with probability \(\frac{1}{4}\) (there are \(2^{n-1} = 4\) of them).

Verify one directly. Amplitude of \(y=110\):

\[ A_{110} \propto (-1)^{010\cdot110} + (-1)^{100\cdot110} = (-1)^{1} + (-1)^{1} = -2 \ne 0 \ \checkmark \]

Amplitude of \(y = 100\) (which should vanish, since \(100\cdot110 = 1\)):

\[ A_{100} \propto (-1)^{010\cdot100} + (-1)^{100\cdot100} = (-1)^0 + (-1)^1 = 1 - 1 = 0 \ \checkmark \]

Problem 2 — Solving the linear system

For \(n=4\), three runs return \(y^{(1)} = 1010\), \(y^{(2)} = 0110\), \(y^{(3)} = 1100\). Find \(s\).

Solution. The equations \(y^{(i)}\cdot s = 0\) over \(\mathbb{F}_2\) are:

\[ \begin{aligned} (1)&: \ s_1 \oplus s_3 = 0\\ (2)&: \ s_2 \oplus s_3 = 0\\ (3)&: \ s_1 \oplus s_2 = 0 \end{aligned} \]

Check independence. Adding (1) and (2) gives \(s_1\oplus s_2 = 0\), which is exactly (3). So \(y^{(3)} = y^{(1)}\oplus y^{(2)}\) — the three vectors are dependent; we have only 2 independent equations, not the 3 required for \(n=4\).

Consequence. The solution space is \(4 - 2 = 2\)-dimensional, containing four vectors. From (1) and (2): \(s_1 = s_2 = s_3\), with \(s_4\) free.

\[ \{0000,\ 0001,\ 1110,\ 1111\} \]

We must run the subroutine again. Suppose the next run gives \(y^{(4)} = 0001\), i.e. \(s_4 = 0\). Now the solution space is \(\{0000, 1110\}\), and since \(s\ne 0\):

\[ \boxed{s = 1110} \]

Lesson. Always check linear independence before stopping. This is why the expected number of runs exceeds \(n-1\).

Problem 3 — Classical versus quantum query counts

For \(n = 60\): (a) expected classical queries; (b) expected quantum queries; (c) if each query is 1 µs, compare wall-clock times.

Solution.

(a) \(\approx \sqrt{2\cdot2^{60}} = 2^{30.5} \approx 1.52\times10^{9}\) queries.

(b) \(\approx 60 + \text{a few} \approx 65\) queries.

(c)

\[ t_c = 1.52\times10^{9}\times10^{-6}\ \mathrm{s} = 1520\ \mathrm{s} \approx \mathbf{25\ minutes} \]
\[ t_q = 65\times10^{-6}\ \mathrm{s} = \mathbf{65\ \mu s} \]

Speed-up factor \(\approx 2.3\times10^{7}\).

Also note the memory. The classical birthday attack must store \(\sim10^9\) function values to detect collisions — about 8 GB at 8 bytes each. The quantum algorithm stores \(n-1 = 59\) vectors of 60 bits: under 500 bytes. The quantum advantage here is in space as well as time.

Problem 4 — Detecting the one-to-one case

Modify the algorithm to distinguish "\(f\) is 2-to-1 with hidden \(s\ne0\)" from "\(f\) is one-to-one" (\(s = 0^n\)).

Solution. Redo Step 4 for the case \(s = 0^n\). Now \(f\) is injective, so measuring the output register collapses the input to a single term \(|x_0\rangle\), and

\[ H^{\otimes n}|x_0\rangle = \frac{1}{\sqrt{2^n}}\sum_y (-1)^{x_0\cdot y}|y\rangle . \]

Every \(y\) occurs, each with probability \(2^{-n}\) — consistent with the constraint \(y\cdot 0 = 0\), which is vacuous.

Distinguishing procedure. Run the subroutine \(n+k\) times and collect the \(y\)'s.

  • If \(s\ne0\): all \(y\)'s lie in the \((n-1)\)-dimensional subspace \(s^\perp\), so their rank is at most \(n-1\), no matter how many runs.
  • If \(s=0\): the \(y\)'s are uniform over all of \(\mathbb{F}_2^n\), so after a few extra runs they span the full \(n\)-dimensional space with high probability.

Decision rule: compute the rank of the collected vectors.

\[ \text{rank} = n \Rightarrow s = 0^n \ (\text{one-to-one}); \qquad \text{rank} = n-1 \Rightarrow \text{recover } s \text{ from the null space}. \]

Failure probability after \(n+k\) runs is at most \(2^{-k}\).

Problem 5 — Simon's algorithm as a cryptanalytic tool

The Even–Mansour cipher is \(E_k(m) = P(m \oplus k_1)\oplus k_2\) where \(P\) is a public permutation. Show how Simon's algorithm recovers \(k_1\) in \(O(n)\) quantum queries, versus \(\Theta(2^{n/2})\) classically.

Solution. Define

\[ g(x) = E_k(x)\oplus P(x) = P(x\oplus k_1)\oplus k_2 \oplus P(x) . \]

Both \(E_k\) (as a quantum oracle) and \(P\) (public, so we can build its circuit) are available, so \(g\) is computable.

Check the Simon promise.

\[ g(x\oplus k_1) = P(x\oplus k_1\oplus k_1)\oplus k_2\oplus P(x\oplus k_1) = P(x)\oplus k_2\oplus P(x\oplus k_1) = g(x) \ \checkmark \]

So \(g\) is periodic with hidden period \(s = k_1\) under XOR. (For a random permutation \(P\), \(g\) is 2-to-1 with overwhelming probability.)

Run Simon's algorithm on \(g\): recover \(s = k_1\) in \(O(n)\) quantum queries. Then \(k_2 = E_k(0)\oplus P(k_1)\) follows from one more query.

Classical cost: the best known attack needs \(\Theta(2^{n/2})\) queries (Daemen's slide attack / birthday bound).

Why this matters. Even–Mansour has a provable \(2^{n/2}\) classical security bound, yet it is completely broken in polynomial time by a quantum adversary with superposition query access. Similar Simon-based attacks break CBC-MAC, PMAC, GMAC, OCB and 3-round Feistel networks.

This is why "just double the key length" is not always sufficient advice. Grover's quadratic speed-up motivates doubling key sizes (L23), but Simon-based attacks are exponential and defeat some symmetric constructions outright — a much more serious concern, though it requires the strong assumption of quantum superposition access to the encryption oracle.

15.8 Practice Problems

  1. For \(n=3\), \(s=011\), list all \(y\) with \(y\cdot s = 0\). [Ans: 000, 100, 011, 111]
  2. Given \(y^{(1)}=101\), \(y^{(2)}=011\) for \(n=3\), solve for \(s\). [Ans: \(s = 111\)]
  3. Verify that \(\{y : y\cdot s = 0\}\) is a subspace of dimension \(n-1\) for any \(s\ne0\).
  4. Compute the expected number of classical queries for \(n=40\). [Ans: \(\approx 1.5\times10^6\)]
  5. Explain why the phase \((-1)^{x_0\cdot y}\) does not affect the measurement statistics.
  6. Show that if \(y^{(1)},\dots,y^{(n-1)}\) are independent, the null space contains exactly 2 vectors.
  7. Why is Simon's separation "stronger" than Deutsch–Jozsa's? Answer in two sentences.

15.9 Summary

  • Simon's problem: find the hidden XOR-period \(s\) of a 2-to-1 function.
  • Classical: \(\Theta(2^{n/2})\) queries (birthday bound), even randomised. Quantum: \(O(n)\).
  • The first exponential separation against randomised classical computation — and the direct inspiration for Shor.
  • Each quantum run collapses to \(\frac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)\); the final Hadamards kill every \(y\) with \(s\cdot y = 1\), yielding a uniformly random \(y \perp s\).
  • Collect \(n-1\) independent equations (expected \(O(n)\) runs, since \(P \to 0.2888\)) and solve \(Ys = 0\) over \(\mathbb{F}_2\).
  • Simon = the Hidden Subgroup Problem over \((\mathbb{Z}_2)^n\); Shor = HSP over \(\mathbb{Z}_N\). Same algorithm, different Fourier transform.
  • Real cryptanalytic bite: Simon-based attacks break Even–Mansour, CBC-MAC and several other symmetric constructions in polynomial time.

Next lesson: L16 — Number theory recap and the RSA cryptosystem.

Practise now: unit2-algorithms-lab.html → Simon tab: set a hidden \(s\), run the subroutine repeatedly, watch the equations accumulate, and see the Gaussian elimination recover \(s\).