Not all "magic" is enough to make a quantum computer outperform a classical one.
A study published in Physical Review Letters shows that some quantum states previously thought to provide the "magic" needed for quantum computation can actually be simulated efficiently by classical computers. The findings redefine scientists’ understanding of the boundary between classical and quantum computing, and identify a more precise resource required for achieving a genuine quantum advantage.
Nicole Yunger Halpern, a Fellow in the University of Maryland's Joint Center for Quantum Information and Computer Science (QuICS), a theoretical physicist at the National Institute of Standards and Technology (NIST) and an adjunct faculty member in the University of Maryland Institute for Advanced Computer Studies (UMIACS), collaborated with researchers at the University of Cambridge and other institutions on the study.
The international research team found that a mathematical property known as Kirkwood-Dirac negativity can distinguish quantum states that can enable quantum speedups from those that cannot. While magic states remain necessary for universal quantum computation, the study shows they are not always sufficient.
"We're showing that magic is necessary but not sufficient to unlock a quantum computer's full power," said David Arvidsson-Shukur of the University of Cambridge's 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."
Quantum computers process information using quantum bits, or qubits, which can exist in multiple states simultaneously. To perform calculations beyond the reach of today's classical computers, qubits often must be prepared in special configurations known as magic states. The new study reveals that some of these states have "bound magic"—they possess magic but still fail to provide a computational advantage because their behavior can be efficiently reproduced by classical algorithms.
To distinguish useful magic states from ineffective ones, the researchers turned to the Kirkwood-Dirac quasiprobability distribution, a mathematical framework developed by physicist Paul Dirac in the 1940s. They showed that when the distribution remains at least zero throughout a quantum computation, a classical computer can efficiently simulate the calculation. Negative values, however, signal the potential for a genuine quantum advantage.
“We’re essentially bringing a new ingredient to the magic mix: the Kirkwood-Dirac negativity,” said J.J. Thio, lead author of the study and a physics Ph.D. student at the University of Cambridge. “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. That distribution provides a stricter, more precise framework for mapping which quantum states can be efficiently simulated by classical computers.”
By identifying a new class of "bound-magic" states, the team expanded the range of quantum computations known to be efficiently simulated on classical computers. The findings raise the benchmark quantum devices must exceed to demonstrate an advantage over conventional computers and provide a clearer picture of the resources needed to achieve that advantage.
"Some of us have conjectured for years that Kirkwood-Dirac negativity can assist with this goal, and I'm delighted that the group has finally answered affirmatively," Yunger Halpern said. “The better we can identify these useful magic states, the better we can produce and apply them.”
The work could also help guide the design of future quantum software and improve methods for producing high-quality magic states, one of the major engineering challenges in building large-scale quantum computers.
The paper, "Kirkwood-Dirac Nonpositivity Is Necessary for Quantum Computational Advantages," was published in Physical Review Letters on Tuesday, August 18.
—Story adapted from University of Cambridge article