Quantum computers are supposed to have abilities far beyond conventional ones, but verifying that they actually do is surprisingly difficult – because checking their results can itself require computations that become prohibitively difficult for classical machines.
This is the quantum verification problem, and a new experiment has found an ingenious workaround – a game that puts each type of system to the test.
The catch? There's a mathematically proven limit to how well any classical computer can perform.
And when a team led by computer scientists Marcello Benedetti and Harry Buhrman of Quantinuum in the UK ran it on a trapped-ion quantum system, it sailed right past the limit with ease.
And as the test became more difficult, the chasm between the quantum system's performance and the best possible classical performance yawned ever wider, according to their paper published in Nature Communications.
Quantum computers derive their unusual abilities from the strange physics that governs particles on the smallest scales.
Where the bits in a classical computer represent information as one of two states – a 1 or a 0 – quantum bits, or qubits, can exist in a superposition of both until they are measured. Measurement collapses that superposition, yielding just one definite outcome.
The mathematical nature of that superposition can be incredibly powerful from a computational standpoint, allowing a quantum computer to make short work of certain problems that are enormously difficult for a conventional computer.
It was the computational power of superposition that the researchers set out to test.
So, they devised a game based on a computational task called complement sampling.
Here's how it works. Imagine all the possible answers to a problem are secretly divided into two equal groups, A and B. You're given one randomly selected answer from group A, and challenged to return an answer from group B.
For a classical computer, that's not really enough to go on. It knows the answer it was given belongs to A, so it knows not to return that one. But it doesn't know which of all the other possible answers belong to A and which belong to B.
The more possible answers there are, the less useful that single piece of information becomes. In fact, the researchers were able to mathematically prove exactly how well the best possible classical strategy could perform.
A quantum computer, however, gets to play by very different rules.
Because a superposed qubit can be both of its states at once until it is measured, the quantum computer can receive a state containing the entire set A in superposition, rather than reducing the answer to a single sample.
And, crucially, it can manipulate that superposition before measuring it. Using what the researchers call a "swapper" circuit, the quantum computer transforms the state representing set A into one representing its complement, set B.
Only then does it measure the state, producing an answer from set B. In an ideal, error-free quantum system, this strategy wins every time.
For a classical computer, the task is exponentially more difficult. It needs to measure the incoming state to obtain one randomly selected answer from group A, then try to return an answer from group B.
This creates a huge gap between what the two types of systems are capable of.
While an ideal quantum system wins every round, the advantage available to even the best possible classical strategy shrinks exponentially as the number of bits – and therefore the number of possible answers – increases.
And that's not just because the researchers haven't found a sufficiently clever classical algorithm. The limit is mathematically proven, without relying on assumptions about how difficult the computation might be.
This gave the team something unusually valuable – a test whose answers are easy to verify, but whose classical performance has a hard ceiling. So they took it to a real quantum computer.
The researchers ran the complement sampling game on Quantinuum's H2 trapped-ion quantum computers, using thousands of different circuits and scaling their experiments up to 55 qubits.
The real machines weren't, of course, as perfect as the theory. As the experiments grew larger and required more quantum operations, hardware noise increasingly degraded their performance.
But the quantum system still consistently cleared the classical limit.
In every experiment, the quantum computer scored so well that its results were statistically inconsistent with what any classical strategy could have achieved.
Better yet, as the problem grew more difficult, the gap widened. The experimentally observed advantage increased exponentially with bit-string length, closely tracking, if not quite matching, the behavior expected of the optimal quantum strategy.
At the largest scale tested – 37-bit strings – the system didn't quite achieve the theoretical ideal performance, but the results still demonstrated an "exponentially large violation of classicality," the researchers note.
The experiment does have some limitations.
The "referee" that chooses the initial answer and the "player" that analyzes it and gives the complement were implemented on the same quantum computer, with quantum teleportation used to simulate the communication channel between them.
Related: Quantum Teleportation Was Achieved Over The Internet For The First Time
A more rigorous future test would put them on separate quantum computers connected by a genuine quantum communication channel.
But that's an obstacle that can be surmounted in the next round of experiments.
For now, the result provides a proof of concept, a new way to test quantum hardware that is efficient to verify, scalable, and – importantly – doesn't rest on unproven assumptions about what classical computers can and can't do.
"Our test," the researchers write, "demonstrates the power of quantum superposition in a manner that is oblivious to entanglement and non-locality."
The findings have been published in Nature Communications.
This article was fact-checked by Fiona MacDonald and edited by Fiona MacDonald. While we pride ourselves on our process, we are only human. If you spot a mistake, please let us know.