Case Study 2: The Half of Simon's Algorithm Nobody Implements

The tutorial version

Simon's algorithm, as it usually appears:

circuit = build_simon_circuit(n, oracle)
counts = run(circuit, shots=n - 1)          # n-1 equations
equations = list(counts.keys())
s = solve_linear_system(equations)

Run it $n-1$ times, collect $n-1$ equations, solve. Clean, matches the complexity claim ($O(n)$ queries), and it is what most implementations do.

It fails intermittently, and the failure looks like the algorithm being wrong.

The failure

A team implements this, tests it on $n = 3$ and $n = 4$, and it works. They scale to $n = 8$ and it starts returning wrong periods — not always, maybe one run in four. The circuit is unchanged. The oracle is unchanged. The same code that worked at $n = 4$ produces garbage at $n = 8$, sometimes.

Their debugging follows the obvious path. Is it noise? They are on a simulator, so no. Is the oracle wrong? They verify it exhaustively at small $n$: correct. Is the circuit wrong? They check the state vector: correct. Is the linear solver wrong? They test it on hand-constructed systems: correct.

Every component is correct and the algorithm intermittently fails.

What is actually happening

Each measurement returns a uniformly random $y$ from the $2^{n-1}$ strings satisfying $y \cdot s = 0 \pmod 2$.

Verified, at $n = 4$ with $s = 1011$:

   measured 8 distinct outcomes (expected 2^(n-1) = 8)
   every y satisfies y.s = 0 (mod 2)?  True
   sample: ['1001', '0000', '0111', '1010', '0100', '0011']

Two problems with taking the first $n-1$ of these.

0000 is always a valid measurement and always useless. It satisfies $y \cdot s = 0$ for every $s$, contributes the equation $0 = 0$, and consumes one of your $n-1$ slots. It appears in the sample above.

Random vectors are not automatically independent. Drawing $n-1$ random vectors from an $(n-1)$-dimensional space gives a spanning set only sometimes. The probability that $n-1$ uniform draws from $\mathbb{F}_2^{n-1}$ are linearly independent is

$$\prod_{k=1}^{n-1}\left(1 - 2^{-k}\right) \approx 0.2888 \quad \text{for large } n$$

Roughly 29%. So a fixed-shot implementation succeeds about a quarter to a third of the time at larger $n$ — which is exactly the intermittent failure they saw, and exactly why it did not show up at $n = 3$ where there are only two equations to get right.

Why the debugging failed

Because every component was correct. The circuit, the oracle, the solver, the measurement — all verified individually, all fine.

The bug was in the protocol, not in any component: how many shots to take, and which ones to keep. That is a piece of logic living between the components, and it is exactly the piece that appears in no tutorial and gets no test.

This book has now hit this pattern repeatedly: Chapter 8's parameter sort, Chapter 10's optimization level, Chapter 13's DD placement, Chapter 14's insertion strategy, Chapter 18's serialization pipeline. Every part correct, the composition wrong.

What is different here is that the composition failure is probabilistic, so it presents as flakiness — the single hardest failure mode to diagnose, because it defeats the reflex of running it again to see.

The fix

Collect until the rank is $n-1$, not until the shot count is $n-1$.

equations, rank = [], 0
for y in measurements:
    if y == "0" * n:
        continue                             # always valid, always useless
    equations.append(y)
    solution, new_rank = solve_f2(equations, n)
    if new_rank == rank:
        equations.pop()                      # linearly dependent -- discard
    else:
        rank = new_rank
    if rank == n - 1:
        break

The expected number of shots is $n - 1 + O(1)$, so the $O(n)$ complexity claim survives intact. The change is not to the complexity; it is to the stopping condition.

vqelab/algorithms.py implements this and reports what it used:

   n=3, s=110:  used 3 outcomes to reach rank 2 (need 2)
   n=4, s=1011: used 4 outcomes to reach rank 3 (need 3)

Note the counts exceed $n-1$ in both cases — one redundant shot each, which is the phenomenon the fixed-count version cannot survive.

And the result object carries redundant_shots, because a number that is usually small and occasionally large is exactly the kind of thing you want visible rather than inferred.

The wider point about post-processing

Simon's algorithm is roughly half classical, and the classical half is where this failure lived.

That is not a quirk of Simon's. It is the structure of essentially every quantum algorithm with a proven speedup:

The quantum subroutine produces constraints. Classical computation turns constraints into answers.

Tutorials foreground the quantum half because it is the novel half. The classical half is where the bugs are, because it is the half everyone assumes is easy — and it usually is easy, right up until the point where it is a rank computation that someone replaced with a shot count.

The lessons

Check the rank, not the count. When measurements are random and you need independent ones, "collect $k$ samples" and "collect until rank $k$" are different algorithms, and only one of them works.

Probabilistic protocol bugs present as flakiness. They survive component-level testing because no component is broken, and they defeat the reflex of re-running because re-running sometimes works. If a quantum algorithm fails intermittently on a simulator, suspect the protocol before the physics.

Zero is always a valid measurement and never a useful one. Any algorithm sampling from a null space will draw it, and it must be discarded explicitly rather than counted.

The classical half is half the algorithm. Simon's is not "a quantum algorithm with some post-processing"; it is a quantum sampler plus a linear solver, and it is incomplete without either. The same is true of Shor's, VQE, and QAOA — which is most of what anyone actually runs.

And report what the protocol consumed. shots_consumed, redundant_shots, and rank are three numbers that cost nothing to return and would have made this bug obvious on the first failing run.

Reproduce it: code/example-02-bernstein-vazirani-and-simon.py runs the rank-based collection and prints how many outcomes it needed; simon() in code/project-checkpoint.py reports the redundant count.