Quantinuum’s Complement-Sampling Test Shows an Exponential Quantum–Classical Gap

Quantinuum’s complement-sampling experiment is evidence of a sharply defined kind of quantum advantage: a quantum device produced statistics beyond a rigorously derived classical bound in a game designed to preserve and test quantum superposition. For Bernstein–Vazirani-based instances, the ideal quantum-to-classical violation ratio scales as 2^(n−1), reaching more than 137 billion to one for 37-bit strings. 4

That result is important, but its scope matters. It is not a general-purpose benchmark, a claim that quantum hardware is 137 billion times faster, or an immediate commercial advantage. It is a source-backed demonstration of an exponential separation for one carefully constructed sampling task.

The complement-sampling game in plain English

A referee selects a hidden subset S containing half of all possible n-bit strings and prepares a quantum state that is an equal superposition over the strings in that subset. The player’s job is to return a string from the complement, written S̄—a string that was not in the hidden subset. 34

For a classical player given only a conventional sample from S, the input reveals very little about the rest of the subset. It can exclude the particular string it received, but it does not provide a usable description of which of the enormous number of remaining strings belong to S and which belong to S̄. The classical strategy is therefore constrained by a formal bound. 47

A quantum player receives the coherent subset state rather than an already-measured sample. For the specially structured instances used in the experiment, a quantum transformation maps the state associated with S to one supported on its complement. In the ideal noiseless case, measuring the transformed state returns a valid complementary string with certainty. 34

The resource under test is coherence: the ability to transform a superposition containing information about many possible strings without first collapsing it to one classical observation. This is not a Bell test or a demonstration of spatial nonlocality.

Why the gap grows exponentially

The relevant comparison is not simply raw success probability. The paper defines a game-specific violation measure above the classical baseline; for the Bernstein–Vazirani-derived family, the ideal quantum-to-classical ratio is 2^(n−1). 4

At n = 37, that is:

2^36 = 68,719,476,736

The reported comparison is described as exceeding 137 billion to one because of the experiment’s stated violation convention. In either framing, the central point is the scaling: the ideal quantum signal remains perfect while the permitted classical advantage shrinks exponentially as the string length grows. 4

This does not mean an H2 processor solved a commercially useful workload 137 billion times faster than a classical computer. It means the ideal strategies separate by that amount under the rules and metric of this particular game.

What Quantinuum ran on H2 hardware

The team executed thousands of circuits on Quantinuum trapped-ion H2 processors, using up to 55 physical qubits and testing strings up to 37 bits long. 48

Real hardware is noisy, so the observed quantum performance was below the ideal perfect-success behavior, with larger circuits more affected by errors. Even so, the reported outcomes remained statistically above the applicable classical threshold, supporting the claim that the devices implemented the quantum strategy well enough to violate the classical bound. 4

That distinction is essential: the experiment does not show that a classical machine is unable to print the same finite bit strings. It shows that, in the specified input model, the measured distribution of answers surpassed what the allowed classical strategy can achieve. 4

Why this benchmark differs from earlier quantum-advantage tests

Many earlier quantum-sampling demonstrations rely on complexity-theoretic assumptions to argue that classical simulation should be difficult. Complement sampling was designed to avoid that particular dependency: its classical limitation is derived for the game itself rather than inferred from an unproven hardness conjecture. 34

It also offers straightforward verification. The referee knows how the hidden subset was constructed and can check whether an output lies in the complement. The underlying work contrasts this with random-circuit sampling, where verification at scale can require either expensive classical simulation or a large number of samples. 34

Those features make complement sampling useful as a foundational benchmark for near-term hardware: it is engineered to reveal a clean quantum–classical separation while remaining verifiable with classical computation.

The limitations behind the headline

It is a specialized sampling task

The game was constructed to expose a quantum advantage in sample-based information processing. It does not establish a practical speedup for chemistry, optimization, cryptography, AI, or general-purpose computing. 4

“Unconditional” does not mean device-independent

The classical bound is unconditional within the mathematical game, but the laboratory protocol still requires trust in the referee’s state preparation. That is different from a fully device-independent test in which conclusions can be drawn without trusting key elements of the apparatus. 4

The referee and player were not separate quantum computers

Because a true quantum communication channel between quantum computers was not available, the implementation embedded the referee’s and player’s registers in one quantum processor and used teleportation to simulate the quantum channel. 4

A stronger future demonstration would use independently controlled systems connected by a genuine quantum link, ideally on fault-tolerant hardware. Building such distributed systems is itself challenging: transferring quantum states and maintaining coherence can become bottlenecks. 14

Exponential is not necessarily the final word

This result establishes an exponential separation for this game family. It does not prove that exponential separation is the greatest possible quantum–classical gap, nor does it demonstrate a super-exponential separation. Whether efficiently verifiable, physically meaningful tasks can show stronger separations remains open based on the evidence provided.

What the experiment actually establishes

Quantinuum’s result is best understood as a precise experimental milestone: current trapped-ion hardware crossed a rigorous classical boundary in an efficiently checkable complement-sampling game, and the ideal separation grows exponentially with problem size. 34

It is a stronger claim than a vague assertion of “quantum supremacy,” because the task, metric, verification method, and trust assumptions can all be stated explicitly. But those same details also define its limits. The experiment is compelling evidence that quantum superposition can deliver an exponential advantage in this tailored setting—not evidence that quantum computers have already surpassed classical systems across useful real-world workloads.