Quantum computers have finally achieved unconditional supremacy

What can quantum computers do that their traditional counterparts absolutely cannot? This is one of the biggest questions facing the fast-growing industry, and now we finally have an unassailable answer.

Instead of classical bits, quantum computers use qubits, which can exist in more states than “0” or “1”, theoretically giving them a computational advantage. But whether a quantum computer can do something impossible or impractical for even the best traditional computers – a feat of quantum supremacy – has proven to be a difficult and contentious question to answer. This is because a true example of quantum supremacy must be a computational task that is practical, so it can be tested on realistic quantum hardware, and provable, so all the mathematical and algorithmic tricks that could help a classical computer eventually catch up must be rigorously ruled out.

William Kretschmer at the University of Texas at Austin and his colleagues have now completed an experiment that satisfies both criteria. Unlike several past claims of quantum supremacy, where classical computers ultimately closed the performance gap between them and their quantum rivals, the researchers now say that “our result is provable and permanent: no future development in classical algorithms can close this gap”.

The team used 12 qubits made from ions controlled by lasers, which were built by the quantum computing company Quantinuum, to perform an experiment with roots in the mathematics of communication complexity. The goal is to find the most efficient ways for two hypothetical experimenters, called Alice and Bob, to complete a computation through messaging each other.

One part of the quantum computer, acting as Alice, prepares a particular quantum state and sends it to another part of the machine, Bob, which then has to decide how to measure Alice’s state in order to learn its properties and produce an output. By repeating this process, the pair can build up a way to predict what Bob’s output will be before Alice reveals her state. 

The researchers repeated the procedure 10,000 times and optimised the way Alice and Bob carried out their parts of the process. Their analysis of all these trials, combined with a rigorous mathematical investigation of the protocol itself, showed that no classical algorithm with fewer than 62 bits could match the 12-qubit quantum computer’s performance on this task. The smallest case where they could prove that a classical algorithm could achieve the same performance required 330 bits – an almost 30-fold difference in necessary computing power.

“This is a remarkable scientific result that shows that the landscape of ‘quantum advantages’ is broader than some might think,” says Ashley Montanaro at the University of Bristol in the UK. “Unlike most quantum advantage or quantum supremacy demonstrations, there is no hope that a better classical algorithm can be found – it’s impossible.”

Ronald de Wolf at the Research Institute for Mathematics and Computer Science in the Netherlands says that the experiment effectively leverages recent rapid improvements in existing quantum computers and builds on ideas from communication complexity theory that have been explored for several decades.

“It has been known that communication complexity is a source of separations between quantum and classical that are both provable and realistic. The difference is that they actually could implement the model now for the first time, thanks to the progress in hardware,” he says. “And they came up with a new communication complexity problem with a bigger gap between classical and quantum, and therefore the gap already exhibits itself even when you just use 12 qubits.”

While the new result stands out from many past demonstrations of quantum supremacy, it does share one important trait with them: it isn’t clear that it can be immediately useful. Examples of quantum advantage that could have big real-world repercussions, like Shor’s algorithm that could radically change cryptography, are still lacking confirmation in terms of provability.

Going forward, the team could strengthen its result by, for instance, making Alice and Bob two separate computers, which would prevent the possibility of unaccounted-for interactions between the two affecting the quantum computer’s result, but the utility of quantum supremacy is the more important question, says de Wolf.

“Beyond [quantum] supremacy should be the step towards useful [quantum] supremacy and a quantum computer doing something much better than classical for a problem that is actually of interest, like some chemistry calculation or some logistics optimisation,” he says.