Gate G23 · Quantum search
Simon's problem on Selene, decoded two ways
Simon's algorithm is the cleanest exponential separation in the textbook, and structurally it is the coset-state machinery already built in G1 and G2: prepare a uniform superposition, entangle through a two-to-one oracle, interfere, and read vectors orthogonal to the hidden mask. The interesting part is not the circuit. It is what happens to the post-processing once the shots are noisy.
The problem and the circuit
f(x) = f(x XOR s), s != 0
The oracle is built to be all-Clifford: copy the input register onto the output with CNOTs, then conditionally XOR the secret in, controlled on the lowest set bit of s. Every instance is checked against the two-to-one promise and brute-force collision search before a single shot is spent, so the emulator is never the only witness.
- Register widths
- 6, 8, 10 qubits
- Shots per cell
- 256
- Backend
- Quest via Selene
- Seed
- 11
1 — Every cell
| n | secret | noise | p(y·s = 0) | rounds | exact GF(2) | max-likelihood |
|---|---|---|---|---|---|---|
| 3 | 001 | ideal | 1.000 | 5 | pass | pass 1.00 |
| 3 | 001 | h2_1x | 0.996 | 2 | fail | pass 1.00 |
| 3 | 001 | h2_10x | 0.980 | 3 | fail | pass 0.98 |
| 3 | 101 | ideal | 1.000 | 6 | pass | pass 1.00 |
| 3 | 101 | h2_1x | 0.992 | 2 | fail | pass 0.99 |
| 3 | 101 | h2_10x | 0.934 | 2 | fail | pass 0.93 |
| 3 | 111 | ideal | 1.000 | 6 | pass | pass 1.00 |
| 3 | 111 | h2_1x | 0.996 | 6 | fail | pass 1.00 |
| 3 | 111 | h2_10x | 0.898 | 3 | fail | pass 0.90 |
| 4 | 0001 | ideal | 1.000 | 6 | pass | pass 1.00 |
| 4 | 0001 | h2_1x | 0.996 | 3 | fail | pass 1.00 |
| 4 | 0001 | h2_10x | 0.969 | 4 | fail | pass 0.97 |
| 4 | 1001 | ideal | 1.000 | 5 | pass | pass 1.00 |
| 4 | 1001 | h2_1x | 0.992 | 8 | fail | pass 0.99 |
| 4 | 1001 | h2_10x | 0.945 | 8 | fail | pass 0.95 |
| 4 | 1111 | ideal | 1.000 | 3 | pass | pass 1.00 |
| 4 | 1111 | h2_1x | 0.980 | 6 | fail | pass 0.98 |
| 4 | 1111 | h2_10x | 0.914 | 3 | fail | pass 0.91 |
| 5 | 00001 | ideal | 1.000 | 7 | pass | pass 1.00 |
| 5 | 00001 | h2_1x | 0.996 | 4 | fail | pass 1.00 |
| 5 | 00001 | h2_10x | 0.941 | — | fail | pass 0.94 |
| 5 | 10001 | ideal | 1.000 | 5 | pass | pass 1.00 |
| 5 | 10001 | h2_1x | 0.988 | 6 | fail | pass 0.99 |
| 5 | 10001 | h2_10x | 0.930 | — | fail | pass 0.93 |
| 5 | 11111 | ideal | 1.000 | 6 | pass | pass 1.00 |
| 5 | 11111 | h2_1x | 0.988 | 9 | fail | pass 0.99 |
| 5 | 11111 | h2_10x | 0.906 | — | fail | pass 0.91 |
Noise levels: ideal, h2_1x, h2_10x. The H2 baseline is p₁q = 3.0e-5, p₂q = 1.29e-3, p_meas = 1.35e-3, the published Quantinuum figures also used in G17 and G20.
2 — The decoder is the fragile part, not the circuit
Exact GF(2) solve
Unique non-zero s orthogonal to every measured vector. Correct with zero noise; a single corrupted shot makes it fail.
9/27 cells — all of them ideal.
Maximum likelihood
Score every candidate s by the fraction of shots it is orthogonal to and take the best. Survives H2-class noise.
27/27 cells, worst orthogonality fraction 0.898.
At ten times the H2 baseline roughly one shot in ten lands off the orthogonal subspace. That is enough to break the textbook linear-algebra solve outright, because it admits no contradictory vector — and not nearly enough to break a scoring decoder that treats the shots as evidence rather than as constraints. The quantum part degrades gracefully; the classical part did not, until it was rewritten to.
3 — Against the classical baseline
| n | classical queries (birthday bound) | Simon, ~n − 1 outcomes |
|---|---|---|
| 3 | 2.5 | 2 |
| 4 | 3.5 | 3 |
| 5 | 5.0 | 4 |
| 20 | 907.5 | 19 |
| 40 | 9.29e+5 | 39 |
A classical algorithm must find a collision, so it needs ~sqrt(pi/4 * 2^n) queries (birthday bound). Simon needs about n-1 independent measurement outcomes.
Honest limits: at n = 5 the classical search costs five queries, so nothing here is a speedup. The separation is asymptotic and the instances are small enough to brute force, which is precisely why they make a good test — the ground truth is known for every cell. What this gate contributes is the harness: a verified oracle, a noise ladder, and a decoder that survives it.