Physicists have mathematically rigorously demonstrated that a quantum computer can solve a particular problem in a way that a classical computer is fundamentally incapable of matching. The result does not rely on unproven assumptions about the limits of classical computation. The work is published in Nature Communications.

The Challenge

Proving "quantum supremacy" is typically difficult. Most such claims are based on the assumption that classical computers have no fast way to solve a given problem. Strictly speaking, this is generally not proven. Researchers therefore sought a formulation in which the quantum advantage could be confirmed without such assumptions.

The Task They Devised

A team led by Marcello Benedetti and Harry Burman from the British company Quantinuum developed a game based on so‑called complementary sampling. In this scheme, the quantum computer, through superposition, operates on the entire set of possible answers at once before performing a measurement. A classical machine can only work with individual samples.

The experiments were conducted on a quantum processor, with complexity gradually increased: up to 55 qubits and strings up to 37 bits long. As the problem size grew, the gap between the quantum and classical systems widened exponentially. The scientists recorded an "exponentially large violation of classicality."

Why This Matters

The key value of the work is that it offers an efficient and scalable way to test quantum supremacy without relying on unproven assertions about the capabilities of classical computers. According to the authors, this is a notable step towards practical confirmation that quantum devices can indeed do what classical ones cannot.

Such a test is particularly useful as technology develops: it can be used to evaluate new processors as they become more complex and to distinguish real advantages from errors or malfunctions.

That said, the problem in question is a specially constructed one, designed specifically to demonstrate supremacy. Practical everyday applications—for example, in chemistry or cryptography—remain a distant prospect for quantum computers.

In Brief

Scientists at Quantinuum have mathematically rigorously proven the advantage of a quantum computer on a complementary sampling task. In experiments with a processor of up to 55 qubits, the gap from classical methods grew exponentially. The new approach allows quantum supremacy to be verified without unproven assumptions about the limits of classical computation, though it still involves a specially chosen demonstration problem rather than applied real‑world use.