From drug discovery to cybersecurity, quantum computers hold great promise for the future. Yet figuring out what would give them their edge over everyday ‘classical’ computers is a problem for scientists.
Now a new theoretical study led by researchers at the University of Cambridge shows that quantum computers are harder to make powerful than previously assumed, while offering the clearest picture yet of what makes them work.
The research, published in Physical Review Letters, helps identify the precise quantum states that are genuinely useful for quantum computation. It also increases the set of quantum calculations known to be easy for classical computers to compute, meaning quantum devices face a higher bar to demonstrate an advantage.
“The idea builds on probabilities – for example, the odds of obtaining a heads-up upon flipping a coin – but coming with a twist: they may be negative. And those negative ‘probabilities’ are needed for the quantum computer to outperform its classical counterpart as well,” said St John’s PhD student JJ Thio, lead author of the study and a researcher in Professor Crispin Barnes’ group at the Cavendish Laboratory.
At the heart of quantum computing is a kind of ‘magic’. Quantum computers typically work with quantum bits, or qubits – particles such as electrons or atoms that can exist in two states at once. To run algorithms that outperform any classical computer, those qubits must be prepared in special starting configurations known as ‘magic states’. These states act as the computational fuel – without them, a quantum computer is no better than a conventional machine.
But Thio and his colleagues have discovered not all magic states are equal. Many that appear ‘magic’ and were previously assumed to be useful turn out to offer no quantum advantage.
By identifying this class of useless magic states, the team redraws the boundary between calculations that need a quantum computer and those that can still be handled classically.
“We’re showing that magic is necessary but not sufficient to unlock quantum computer’s full power,” said Dr David Arvidsson-Shukur, from the Hitachi Laboratory at the Cavendish Laboratory. “If a quantum state is not magic, you can’t get a quantum advantage. But having magic alone doesn’t guarantee you have one either. The picture is more nuanced and much more interesting than that.”
To identify which quantum states have ‘useful’ magic, and which have the ‘useless’ kind, the researchers turned to a mathematical framework developed at St John’s in 1945 by Paul Dirac, the Nobel Prize-winning physicist behind the relativistic quantum equation that predicted anti-matter. Dirac independently established a distribution similar to one introduced a decade earlier by MIT’s John Kirkwood, and extended the idea by building the mathematical framework in which to use it.
Known as the Kirkwood-Dirac distribution, it involves a concept that sounds paradoxical – negative probabilities – which the team used to phrase the task of quantum computation. Just as Dirac once argued that a negative solution to an equation should be taken seriously (a theory that led to the discovery of anti-matter), the team shows that the appearance of negative values in the Kirkwood-Dirac distribution is a meaningful signal.
When that distribution stays entirely positive (or zero) throughout a computation for a given input quantum state, a classical computer can simulate the quantum computation with ease. When it goes negative, classical simulation becomes exponentially harder and a genuine quantum advantage may exist.
“We’re essentially bringing a new ingredient to the magic mix: the Kirkwood-Dirac negativity,” said Thio. “That distribution provides a stricter, more precise framework for mapping which quantum states can be efficiently simulated by classical computers.”
To demonstrate their theory, he worked with a fellow student to complete a classical simulation programme that runs on a standard laptop, performing computations previously thought to require a quantum computer. The result is a direct demonstration that the classical frontier is larger than previously thought.
Their work brings the field a step closer to a complete understanding of what gives quantum computers their potential. They hope the results will guide both the design of quantum software and the production of magic states, which remains one of the major engineering challenges in building large-scale quantum computers.
Reference
Jonathan J Thio, Songqinghao Yang, Nicole Yunger Halpern, Stephan De Bièvre, Crispin HW Barnes and David RM Arvidsson-Shukur, ‘Kirkwood-Dirac Nonpositivity Is a Necessary Resource for Quantum Computing.’ Physical Review Letters (2026). DOI: 10.1103/x819-898d
