Quantinuum Demonstrates Provable Quantum Advantage on 55 Qubits: A 137 Billion-to-1 Gap Written in a Theorem

On September 8, 2026, the Quantinuum team published a Nature Communications paper, Unconditional and exponentially large violation of classicality. On their H2 trapped-ion processor, they played a game called complement sampling at sizes from n = 5 to n = 37, with the largest circuit using 55 qubits and roughly 228 native two-qubit gates. The theoretical gap grows exponentially with size, reaching 137 billion to one at n = 37 — and it is measured against a classical bound that is rigorously proven mathematically, not "assumed hard for classical algorithms." Every quantum advantage experiment of the past decade — Google Sycamore's random circuit sampling, USTC's Jiuzhang and Zuchongzhi Gaussian boson sampling — has faced the objection that "a smarter classical algorithm may appear in the future." This one does not.

A game whose classical ceiling is sealed by mathematics

Complement sampling has one core rule: a referee secretly splits the full set of n-bit strings into halves A and B, gives the player one string from A, and asks the player to return a string from B.

• A classical player holding one string from A can only exclude that single string. The internal composition of A and B is a black box; among the remaining \(2^n - 1\) strings, it cannot tell which belong to A or B. As n grows, the optimal classical success rate converges exponentially toward 1/2.
• A quantum player receives not one string from A but the entire set A in quantum superposition. Using a "swapper" circuit (built from Grover diffusion and Bernstein–Vazirani-style structure), it coherently maps the superposition of A into B, then measures — ideally always returning a string from B.

The classical bound follows directly from information theory — no computational complexity assumptions needed.

Placed alongside the past decade of quantum advantage experiments, the difference is fundamental:

| Experiment | Basis of advantage | Relies on unproven complexity assumptions? | |---|---|---| | Google Sycamore random circuit sampling | "Simulating the output distribution is computationally hard" | Yes (complexity conjectures) | | USTC Jiuzhang / Zuchongzhi boson sampling | "Approximating matrix permanents is hard" | Yes | | Quantinuum complement sampling (9/8) | Classical bound proven by information theory | No |

The Quantinuum team is careful in the paper: this does not mean quantum computers are 137 billion times faster for any commercial task; rather, "within this small mathematically bounded game, the gap between quantum and classical grows exponentially with scale."

Results on hardware

Device: the Quantinuum System Model H2 trapped-ion processor — 56 qubits, ytterbium-171 hyperfine qubits, barium ions for sympathetic cooling. All qubits are fully connected, requiring no SWAP gates; two-qubit gate fidelity is consistently above 99.8%.

Experimental protocol:

• Complement sampling instances measured for n = 5 through n = 37;
• Thousands of distinct circuits run at each n;
• Most n used 200 rounds (half scoring, half input-state quality verification);
• n = 37 ran 1000 rounds;
• The classical bound was violated at the 1% significance level;
• The advantage grows exponentially with n, matching theory exactly.

Where the 137-billion-to-one number comes from

• For the Bernstein–Vazirani-derived instance family, the ideal-quantum-to-best-classical ratio is \(2^{n-1}\);
• At n = 37, \(2^{36} = 68{,}719{,}476{,}736\);
• The paper's "137 billion" figure arises from the specific violation convention used (different normalization of numerator and denominator), but the core fact is the exponential growth with n.

In other words, this is not "a quantum computer 137 billion times faster", but "the theoretical boundary of quantum advantage in this mathematically defined game expands exponentially with scale." And once published, future classical algorithms cannot erase this advantage — because the classical bound is proven, not guessed.

What it solves — and what it doesn't

Solved:

• Whether the classical upper bound on quantum advantage can be mathematically proven;
• Whether quantum advantage can be verified efficiently by a classical machine — complement sampling outputs are classically checkable;
• Whether the advantage persists at scale — the measured gap grows exponentially with n.

Not solved:

• Trustworthy state preparation: referee and player share the same processor; a fully convincing version would use two physically separated quantum machines connected by a quantum channel;
• Hardware noise: at n = 37, two-qubit gate errors accumulate; the measured score is slightly below the theoretical bound, though still far above the classical limit;
• Quantum error correction: none was used; scaling further requires higher gate fidelity or error correction;
• Practical value: complement sampling computes nothing anyone wants. It is a test of non-classicality, closer to a Bell inequality violation than to factoring or molecular simulation.

The paper concludes that the game "can serve as a scalable benchmark for quantum hardware," with violations growing exponentially with input size.

Significance: quantum benchmarks move from "guessing" to "proving"

The most persistent criticism of quantum advantage claims has been reliance on believed-but-unproven complexity conjectures, forcing the boundary to be renegotiated each time classical algorithms improve. Complement sampling turns this from an empirical claim into a theorem:

• The classical bound comes from information theory, independent of complexity conjectures;
• Outputs are efficiently verifiable classically — no need to re-simulate the quantum process;
• The advantage grows exponentially with scale — larger systems make the demonstration *easier*, contrary to past intuition;
• The team's next step is two physically separated machines plus a quantum channel, moving from single-device self-demonstration to network verification.

Threads worth tracking:

• Separated-machine verification: when Quantinuum deploys referee and player on two physically separate H-series machines;
• Benchmark extensions: can complement sampling be adapted toward practical tasks, e.g. encoding molecular simulation or constraint-satisfaction problems into the A/B split;
• Porting to other platforms: can superconducting, photonic, or neutral-atom hardware show equal advantage;
• QOBLIB in parallel: IBM's September 1 expansion added 1200+ instances and 500+ optimally solved problems — optimization and advantage benchmarking are maturing side by side.

References

1. Nature Communications: *Unconditional and exponentially large violation of classicality*, Benedetti et al., DOI: 10.1038/s41467-026-77413-3, 2026-09-08 2. arXiv preprint: 2511.11008 (2025-11-14) 3. Quantum Brief: Quantinuum's 55-qubit experiment beats the best classical score by 137 billion to one, 2026-09-09 4. The Quantum Insider: Game On — Quantinuum Demonstrates Exponential Edge Over Classical Strategies, 2026-09-08 5. Phys.org: A new game demonstrates quantum advantage with provable classical limits, 2026-09 6. Quantinuum Blog: Unlocking Quantum Advantage with Complement Sampling, 2026-09-08 7. IBM QOBLIB (Quantum Optimization Benchmarking Library) September 1 expansion update