Game On: Quantinuum Demonstrates Exponential Edge Over Classical Strategies

Insider BriefA Quantinuum-led research team has demonstrated an exponentially widening gap between quantum and classical strategies in a test designed to verify quantum behavior without relying on unproven assumptions about computational difficulty.The study, published in Nature Communications, describes a game that asks a computer to produce an answer excluded from a hidden set of possible answers. Quantinuum’s trapped-ion quantum computer consistently outperformed the best possible classical strategy across experiments using as many as 55 physical qubits.The researchers reported evidence that the quantum advantage grew exponentially as they increased the size of the problem. They tested thousands of distinct circuits on Quantinuum’s System Model H2 computers, including experiments based on bit strings as long as 37 bits.The test addresses a concern surrounding many demonstrations of quantum computational advantage. Those experiments often rely on the belief that a classical computer cannot efficiently reproduce a quantum device’s results. Although there is evidence that supports this, the underlying claims generally depend on mathematical assumptions that have not been proved.In the new test, the gap between the quantum and classical strategies is established mathematically and does not depend on such a complexity-theory assumption, according to the study. The answers can also be checked efficiently using a classical computer.That combination could make the approach useful as quantum systems grow larger and become harder to simulate directly. Rather than asking a classical supercomputer to reproduce every detail of a quantum calculation, an evaluator can check whether the device’s answers exceed a mathematically defined classical limit.The researchers called the test the “complement sampling game.” It centers on the quantum property of superposition, which allows a quantum system to represent a combination of multiple possible states.The game has a referee and a player, but these are not people. Instead, they are roles assigned to different parts of the experimental system. Now, back to our game. In each round, a referee selects a set containing exactly half of all possible bit strings of a specified length. The referee prepares a quantum state representing a uniform superposition of the strings in that set and sends it to a player. The player must return a string from the other half, known as the complement. A correct answer earns one point, while an answer from the original set loses one point.A classical player can measure the state and learn one string contained in the original set. The player can then submit a different string, but that provides little help because nearly all information about the set remains hidden. As the strings become longer, the classical player’s advantage over a random guess falls exponentially.A quantum player can instead apply an operation known as Grover diffusion. This operation rearranges the state’s amplitudes, which are the values determining the probability of each possible measurement result. For the specially constructed sets used in the game, it converts the superposition of strings inside the set into a superposition of strings outside it.An ideal quantum system would therefore return a correct answer in every round.The team constructed the sets using a structure related to the Bernstein-Vazirani problem, an early example used to illustrate how quantum computers can discover hidden information more efficiently than classical machines. Using this structure, the referee can prepare the quantum states and verify the returned answers without performing an exponentially difficult computation.The quantum advantage actually grew with each additional bit. For the largest 37-bit problem, the theoretical gap between the ideal quantum and best classical strategies exceeded 137 billion to one.Careful to note here that that ratio does not mean the quantum computer completed a useful commercial calculation 137 billion times faster. It measures the difference between quantum and classical scores in this particular game. The result is still important because the separation grows exponentially and follows from a mathematical proof rather than a conjecture about the limits of classical algorithms.The researchers ran the game on Quantinuum System Model H2 trapped-ion processors. The 56-qubit machines use electrically charged ytterbium atoms as qubits and barium ions for cooling. The ions move around a racetrack-shaped trap and are brought into dedicated zones where lasers perform quantum operations.That design provides flexible connections among the qubits, as well as measurements and classically controlled operations while a circuit is still running. All of this was needed as the researchers attempted the most complete version of the game.The researchers tested instances with bit-string lengths ranging from five to 37. Their largest circuit used 55 qubits and averaged about 228 native two-qubit gates.For experiments through 15 bits, the team used quantum teleportation to imitate a communication channel between the referee and the player. Quantum teleportation transfers the state of a qubit using shared entanglement, measurements and ordinary classical information. It does not transport matter or allow information to travel faster than light.The simulated channel required additional qubits, limiting those tests to 16-bit problems or fewer. To reach larger sizes, the researchers removed the teleportation stage and placed the state preparation and player operations more directly on the same processor.Most problem sizes were tested through 200 rounds, divided equally between evaluating the player and checking state preparation. The researchers used 1,000 rounds for the largest 37-bit experiment. Because every round involved a newly selected hidden set, each required a different circuit and produced a single sample.The random values used to construct the sets came from Quantinuum’s Quantum Origin system. It combined a local source of randomness with results from a Bell test performed on a separate Quantinuum H1-1 computer. Bell tests examine correlations that cannot be explained by certain classical models.Across the tested sizes, the observed scores remained above the best possible classical score at the study’s chosen statistical significance level. The researchers rejected the hypothesis that the results came from a classical strategy with a significance threshold of 1%.The observed violation of the classical limit grew exponentially with the problem size and remained close to the pattern expected from the optimal quantum strategy. Noise caused a more visible departure from ideal performance in the 37-bit experiment, which had the largest number of two-qubit gates.The approach differs from random circuit sampling, a method used in several prominent quantum-advantage experiments. Random circuit sampling asks a quantum processor to execute complicated, largely random operations and produce samples from the resulting probability distribution.Verifying those results can become prohibitively expensive because a classical computer may need to simulate the quantum circuits. Alternative verification methods can require an enormous number of samples. The claims can also depend on assumptions that no classical algorithm has found an efficient way to perform the task.The complement sampling game produces results that a classical referee can check efficiently. Its theoretical quantum-classical separation also does not depend on the existence of hard-to-reverse mathematical functions or related assumptions commonly used in complexity theory and cryptography.“Unconditional,” however, does not mean the experiment was free of trust requirements or possible loopholes.The main demonstration assumed that the referee’s state-preparation process could be trusted. Under that condition, a score above the classical limit provides evidence that the player used a nonclassical strategy. The researchers also developed a reversed version in which a trusted player can evaluate the quality of the referee’s state preparation.If neither device can be trusted, the test is inconclusive. The referee and player could coordinate and reproduce a perfect score without using a quantum strategy, the researchers found.The experiment also placed the referee and player on the same H2 processor. Although teleportation simulated a quantum communication link in some tests, the state was not sent between two separate quantum computers. In the future researchers could implement a more rigorous version that would generate the random numbers and subset states on the referee’s computer, then transmit the state to an independent machine controlled by the player.Hardware noise imposes another limit as errors accumulate as circuits use more two-qubit gates, eventually making the quantum signal indistinguishable from the classical score. The researchers could not apply common error-mitigation techniques because those methods generally require repeated copies of an output state, while the game uses a different randomly selected state in each round.It’s also important to note that the results also do not establish a general-purpose quantum advantage or demonstrate an immediate commercial application. The game was constructed to test a specific prediction of quantum mechanics and to separate quantum superposition from classical sampling under controlled conditions.Incremental improvements in gate accuracy could allow the game to reach somewhat larger problem sizes on near-term processors, according to the study. Substantial scaling will probably require fault-tolerant quantum computers that detect and correct errors while calculations are running.The circuits used to prepare the hidden-set states rely on somewhat simple operations that can be implemented efficiently in some error-correcting codes. The operation used by the player is more demanding. It is related to a multiqubit Toffoli gate and would require expensive error-corrected operations known as T gates.The researchers pointed to recent proposals for approximating large Toffoli gates while keeping the required number of T gates from growing with the number of qubits. Such methods could provide a route to running the game on future error-corrected machines.Additional work is also needed to determine how imperfect randomness would affect the test. The researchers said they did not establish whether nonuniform sampling of the hidden sets and referee decisions would have negligible or material effects.Despite those qualifications, the experiment offers a potentially scalable way to test whether increasingly complex quantum hardware is behaving in a manner that classical systems cannot match. It complements measures such as quantum volume, application benchmarks and Bell tests by focusing directly on the computational power of quantum superposition.The researchers left open whether a related game could produce an even larger, super-exponential separation between quantum and classical strategies.The research team included Marcello Benedetti, Gabriel Marin-Sanchez, Jordi Weggemans, Matthias Rosenkranz and Harry Buhrman, all from Quantinuum in London. Buhrman is also affiliated with the University of Amsterdam and QuSoft in Amsterdam.TopicsShare Get the latest research, company news, and market intelligence every week. MENTIONED IN THE ARTICLEQuantinuum is a quantum computing company advancing the aerospace sector through the development of algorithms for aerodynamic modeling, composite materials optimization, and sustainable aviation fuel cell engineering. Founded in 2021 through the merger of Cambridge Quantum and Honeywell Quantum Solutions, the firm provides high fidelity trapped ion hardware and software to accelerate industrial applications.The University of Amsterdam (UvA) is a key player in quantum research, focusing on areas like quantum matter, quantum information, and quantum computing through initiatives such as the Quantum Matter & Quantum Information research area and the QuSoft research center. UvA also emphasizes quantum computing education, practical applications in collaboration with industry, and the legal implications of quantum technologies through its Institute for Information Law.QuSoft was founded in 2015 as a collaboration between the University of Amsterdam (UvA) and Centrum Wiskunde & Informatica (CWI). QuSoft is part of Quantum Delta NL, and in that capacity the research institute is tasked with exploring quantum software and applications.More in Research