A supercomputer takes days to complete a calculation; a quantum chip finishes it in seconds. Whenever such claims have been reported over the past several years, the computer science community has responded with skepticism. This is because a sophisticated classical algorithm devised after the fact can reproduce the same result on a classical computer, quickly overturning any advantage demonstrated experimentally. This difficult problem, known as the quantum verification problem, exposes a fundamental contradiction: how can a less capable classical verifier confirm that a result which is computationally intractable for classical machines is actually valid? As long as the verification process itself requires enormous computation time or relies on unproven assumptions in computational complexity theory, it remains impossible to definitively establish a machine's true advantage.
On September 5, 2026, a research team led by Marcello Benedetti, Gabriel Marin-Sanchez, Jordi Weggemans, Matthias Rosenkranz, and Harry Buhrman at Quantinuum published a paper in the journal Nature Communications that breaks this deadlock (DOI: 10.1038/s41467-026-77413-3). The preprint is available on arXiv (arXiv:2511.11008). The approach they adopted models a specific task called complement sampling as a competitive game. For this game, a mathematical upper bound on performance—one that no classical algorithm, however sophisticated, can ever exceed—has been rigorously proven. In experiments run on Quantinuum's ion-trap quantum hardware, scores consistently exceeded this classical upper bound as the problem size increased.
Prior demonstrations of non-classical behavior were constrained by three limitations: dependence on assumptions in computational complexity theory, vulnerability to hardware noise, and inefficient verification procedures. What makes this achievement stand out is that it unconditionally breaks the limits of information processing based on classical physics, while still allowing verification in polynomial time.
A Game That Binds Classical Machines Not by Computational Difficulty, but by the Physical Laws of Information
The rules of the complement sampling game are remarkably straightforward. Two parties take part: a referee and a player. For a given integer $n$, the space of all bit strings of length $n$ contains $2^n$ possible candidates. The referee randomly selects exactly half of them—a subset $S$ with $2^{n-1}$ elements. The referee generates a quantum state $|S\rangle$ representing this subset $S$ and sends it to the player. The player's task is to select one bit string $y$ that is not included in the subset $S$—that is, from its complement—and send it back to the referee.
The referee awards $+1$ point if the returned bit string $y$ truly belongs to the complement, and $-1$ point if it turns out to be inside the subset $S$. This trial is repeated many times, and the cumulative score is used to statistically determine whether the player employed a quantum strategy or remained confined to a classical one.
When a classical computer attempts to play this game, it collides with a fundamental barrier. A classical device cannot hold and process a superposition of quantum states as such. It is only permitted to measure the incoming quantum state and extract a single bit string chosen at random from within the subset $S$. The only information a classical player can obtain is the fact that "this one value belongs to $S$"—with no clue whatsoever as to which of the remaining vast number of candidates belong to $S$ and which belong to its complement.
As the length $n$ of the bit string grows, the information carried by a single sample becomes increasingly diluted across the whole space. The research team mathematically derived the highest success probability achievable by any classical algorithm whatsoever. This success probability decays exponentially as the number of bits increases, rapidly converging to $1/2$—the probability of a random guess. Crucially, this bound is not conditional on "assuming some unresolved mathematical conjecture is true"; it is an absolute limit proven through information theory.
An ideal quantum computer, by contrast, processes the problem according to an entirely different physical principle. A quantum player who receives the state —an equal superposition of all elements in the subset $S$—without destroying it applies a "swapper circuit" before performing any measurement. The unitary transformation used here is known as the Grover diffusion operator: . Because the subset contains exactly half of the total space, $2^{n-1}$ elements, this operator swaps the superposition state of subset $S$ into the superposition state of its exact complement, without the slightest error. If measurement is performed only after this transformation, the resulting bit string is guaranteed to be an element of the complement. The theoretical success probability is $1$—meaning victory is assured every single round.
| Comparison Point | Quantum Player (This Method) | Classical Player (Theoretical Limit) |
|---|---|---|
| Handling of input information | Operates while preserving the superposition state | Estimation/guessing after excluding one obtained element |
| Operational mechanism | Inversion to the complement via the Grover diffusion operator | Estimation and guessing after excluding the single obtained element |
| Win rate as bit length $n$ increases | Ideally always 1 (maintains significant advantage even in noisy environments) | Decays exponentially, rapidly approaching $1/2$ |
| Logical basis of the bound | Linearity of quantum unitary transformations and controllability of superposition | Unconditional mathematical bound derived from information theory |
| Dependence on external complexity assumptions | Not required (verification is also directly possible in polynomial time) | Not required (no room for improvement through clever algorithms) |
The underlying concept of complement sampling itself was proposed in prior work (arXiv:2502.08721), where it was theoretically shown that sample complexity separates between constant and linear when the subset size equals half of the total space. What is novel in this research is that it elevated this theory into a competitive game verifiable on real hardware, by introducing a concrete circuit architecture inspired by the Bernstein–Vazirani problem.
Shuttled Trapped Ions Run a Large-Scale 55-Qubit Circuit
To confirm the theory's consistency, the research team went beyond simulation and prepared physical hardware. The device used was Quantinuum's "System Model H2 (H2-2)" ion-trap quantum computer.
H2-2 stands out among ion-trap quantum computers for its exceptional integration density and control precision. Within a vacuum chamber, a racetrack-shaped trap electrode captures 56 ytterbium-171 ions (\text{^{171}Yb^+}), which serve as qubits. Barium-138 ions (\text{^{138}Ba^+}) are placed between the ions as coolant, and laser cooling suppresses the overall thermal vibration of the system. The structural strength of this architecture lies in its "Quantum Charge-Coupled Device (QCCD)" method, in which trapped ions can be physically moved freely within the trap through voltage control. Because any pair of qubits, regardless of physical distance, can be brought close together to interact, the system offers all-to-all connectivity, unconstrained by the planar lattice proximity limitations seen in superconducting architectures.
The experiments were carried out while progressively increasing both the number of qubits and the circuit scale. The lengths of bit strings tested ranged widely, from $n = 5$ to $n = 37$. The total number of qubits used reached as many as 55, and thousands of distinct circuits were executed.
A rigorous protocol was also established to guarantee statistical significance. For experiments with bit string length , the number of trials was set to $r = 100$ rounds; for the largest-scale experiment at $n = 37$, $r = 500$ rounds were used. The significance level was fixed at (99% confidence) across all verifications.
In each round, the referee program randomly selected a new subset and assembled a different circuit configuration on the fly for execution. In the largest experiment, at $n = 37$, a total of 1,200 distinct circuits were run on the actual hardware. These circuits executed the hardware's native two-qubit gates an average of approximately 227.61 times (standard deviation 3.11). Despite the demand for deep circuit depths and a large number of entangling operations, the all-to-all connected ion-trap circuits continued to operate without failure.
データを表で見る
| 回路あたりの平均ゲート数 (ゲート数（平均値）) | |
|---|---|
| n = 5 | 29.56 |
| n = 10 | 72.16 |
| n = 20 | 117.46 |
| n = 37 | 227.61 |
As the circuit scale expanded, the computational load that the hardware had to process grew correspondingly. In smaller configurations ($n = 5, 10, 15$), a state-transfer protocol using quantum teleportation was implemented within the same chip to simulate communication between the referee and the player. The superposition state prepared by the referee qubits was transferred to the player qubits through measurement, classical communication, and feed-forward operations, after which the swapper operation was applied.
Experimental Data That Kept Breaking the Classical Ceiling Even as Noise Took Its Toll
Real hardware does not behave in perfect accordance with textbook equations. This is because qubits lose their phase coherence through decoherence—interaction with minute surrounding electromagnetic noise—and gate operation errors accumulate due to imperfections in laser irradiation. As circuits grow deeper and the number of qubits used increases, the actual hardware output diverges further from theoretical values.
However, the experimental results obtained demonstrated that the quantum advantage remained unmistakably intact even in the presence of noise-induced degradation.
Across every experimental scale the research team conducted, the scores recorded by Quantinuum H2 reached a region that is statistically incompatible with any achievable classical strategy's upper bound. In the most demanding experiment—$n = 37$, using 55 qubits, with 500 trial rounds—the upper bound on the p-value (), indicating the probability that the observed data arose from classical chance or strategy, was . This extraordinarily small probability, falling below one in ten thousand, stands as strong evidence that the results obtained decisively depart from the framework of classical physics.
In the paper's abstract, the authors explicitly state that the observed scores "can only be explained by the systematic use of quantum strategies." Confidence intervals were estimated using the statistically robust bias-corrected and accelerated bootstrap method (using SciPy, with 9,999 resamplings, at a 99% confidence level). Even after rigorously accounting for fluctuations in the measured data, the classical wall remained far below.
Analyzing the relationship between the observed experimental scores and the bit string length $n$ reveals that the advantage achieved by the actual hardware grew exponentially as the problem size expanded. Although it fell slightly short of the ideal curve drawn by the theoretically optimal quantum strategy, its behavior faithfully tracked the theoretical prediction curve. Even as hardware noise pushed the score downward, the classical upper bound plunged toward zero at an even steeper rate, meaning that the physical gap between the two widened further as the scale increased.
The mathematical basis for why this experimental system is so robust against noise is also well established. Theoretical calculations show that, over a polynomial number of rounds, as long as the player achieves success with a probability of at least , the strategy can be definitively judged non-classical. Even if hardware imperfections significantly reduce the success rate below the ideal value of $1.0$, the proof of quantumness remains solid as long as a significant gap remains from the classical bound of $1/2$. At the largest scale, $n = 37$, the actual hardware did not achieve the theoretically perfect score. But what was demonstrated there was an "exponentially enormous violation of classicality" that holds even after fully accounting for the presence of noise.
From an Isolated Single Machine to True Distributed Network Verification: What Remains to Be Done
To accurately grasp the contours of this achievement, it is necessary to soberly distinguish what has been proven from what has not. This result does not mean that quantum computers have surpassed classical machines in practical cryptanalysis or materials computation. The task in question is an artificial setting—the complement sampling game—devised specifically to rigorously test the physical behavior of hardware.
The greatest physical constraint is that the referee and the player were physically housed within the same quantum computer chassis. Although state transfer via quantum teleportation was incorporated in the smaller-scale experiments, what mediated between the two was trapped ions and internal control lasers moving within the same vacuum chamber. Complete physical isolation—guaranteeing that information the referee is supposed to keep secret from the player has not unintentionally leaked through internal hardware crosstalk or shared control systems—cannot, strictly speaking, be fully assured given the structure of a single chip.
The research team itself acknowledges that, in order to achieve more rigorous verification, an experiment is essential in which two physically separate, independent quantum computers are prepared and connected via an actual quantum communication fiber or optical network. Only by exposing the communication channel externally and establishing the same game in a spatially isolated environment can verification that fully closes the locality loophole be completed.
Careful understanding is also required regarding the nature of the physical behavior demonstrated in this study. The authors state in the paper that "our test demonstrates the power of quantum superposition in a manner independent of quantum entanglement or non-locality." While discussions of quantum supremacy often center on violations of Bell inequalities or verification of macroscopic entangled states, what this complement sampling game targets is a far more basic information-processing capability of quantum mechanics itself: manipulating a pure superposition state with a unitary transformation without measuring it.
The fact that proving the classical limit required no reliance on unresolved problems in computational complexity theory has the power to fundamentally change the reliability of hardware verification. In conventional random circuit sampling, there was always a risk that estimates of the computational cost of classical simulation could be overturned by the emergence of a new algorithm. This complement sampling approach, by contrast, is structured so that no matter how clever a programmer might be in devising a classical algorithm, the sheer amount of information provided is fundamentally insufficient—making it physically impossible to ever exceed the bound.
As quantum technology moves beyond its early developmental stage—advancing from noisy intermediate-scale quantum (NISQ) devices toward large-scale, error-corrected systems—measurement protocols that can conclusively confirm whether a constructed machine truly operates according to genuine quantum physics will become increasingly important. This testing method, which withstands hardware noise and can render a verdict in polynomial time, should serve as a trustworthy yardstick for next-generation hardware developers seeking to prove the authenticity of their machines.
The question that remains is clear: crossing beyond the walls of a single vacuum chamber, and connecting two independent cryostats or ion traps via photons flying between them, how far can this quantum advantage be sustained? And how can the mathematical structure that produces this unconditional separation be extended to the verification of practical computational tasks? The effort to mathematically bind the limits of classical computation while physically laying bare quantum behavior has, at last, secured its first solid foothold.