The Quest to Quantify Quantumness
How might we measure the computational power of a quantum system? Researchers have identified an assortment of physical properties that could do the trick.
Peter Greenwood for Quanta Magazine
Introduction
It’s been more than 40 years since the physicist Richard Feynman pointed out that building computing devices based on quantum principles could unlock powers far greater than those of “classical” computers. In a 1981 keynote speech often credited with launching the field of quantum computing, Feynman concluded with a now-famous quip:
“Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical.”
It’s been nearly 30 years since the mathematician Peter Shor came up with the first potentially transformative use for quantum computers. Much of the security of the digital world is built upon the assumption that factoring large numbers is a challenging and time-consuming task. Shor showed how to use qubits — quantum objects that can exist in mixtures of 0 and 1 — to do it in a heartbeat, at least relative to known classical methods.
Researchers feel quite confident (although not entirely certain) that Shor’s quantum algorithm beats all classical algorithms because — despite the tremendous incentives — no one has successfully broken modern encryption with a classical machine. But for tasks less glamorous than factoring, it’s hard to say for sure whether quantum methods are superior. Searching for further blockbuster applications has become something of a haphazard guessing game.
“This is a silly way to go about this,” said Crystal Noel, a physicist at Duke University.
Over the last 20 years, a loose confederation of mathematically inclined physicists and physically inclined mathematicians has endeavored to more clearly identify the power of the quantum realm. Their goal? To find a way to quantify quantumness. They dream of a number they can assign to an arrangement of qubits produced by some quantum calculation. If the number is low, then it would be easy to simulate that calculation on a laptop. If it’s high, the qubits represent the answer to a truly hard problem beyond the reach of any classical device.
In short, researchers are seeking the physical ingredient at the root of quantum devices’ potential power.
“That’s where quantumness begins in a super rigorous sense,” said Bill Fefferman, a quantum researcher at the University of Chicago.
Their quest has been fruitful — perhaps too fruitful. Instead of finding one metric, researchers have stumbled upon three, each a distinct way of separating the quantum and classical realms. Meanwhile, physicists have started to wonder whether the least concrete quantity of the three shows up outside quantum computers. Preliminary studies have found it does, and that it may offer a new way to get a handle on phases of quantum matter and the destructive nature of black holes.
For these reasons, both physicists and computer scientists have endeavored to map out the exact topography of this three-part quantum kingdom. This summer, a trio of research groups announced that they had formulated the best map yet of the least familiar of the three provinces, adding crucial details to the understanding of where the classical ends and the truly quantum begins.
It’s “quite fundamental to understand where this horizon is,” said Kamil Korzekwa of Jagiellonian University in Poland, one of the researchers behind the new works. “What is really quantum about quantum?”
Entanglement
In the 1990s, the physical ingredient that made quantum computers powerful seemed obvious. It had to be entanglement, the “spooky” quantum link between distant particles that Erwin Schrödinger himself identified as “the characteristic trait of quantum mechanics.”
“Entanglement was mentioned very quickly,” said Richard Jozsa, a mathematician at the University of Cambridge. “And everyone just assumed that was it.”
For a time, it seemed the search for that crucial quantum spice had ended before it even started.
Entanglement, the phenomenon in which two quantum particles form a shared state, encapsulated what was hard about doing quantum mechanics — and therefore what quantum computers could excel at. When particles are not entangled, you can keep track of them individually. But when particles become entangled, modifying or manipulating one particle in a system involves accounting for its links to other entangled particles. That task grows exponentially as you add more particles. To fully specify the state of n entangled qubits, you need something like 2n classical bits; to calculate the effect of tweaking one qubit, you need to perform around 2n classical operations. For three qubits that’s only eight steps. But for 10 qubits it’s 1,024 — the mathematical definition of things escalating quickly.
In 2002, Jozsa helped work out a simple process for using a classical computer to simulate a quantum “circuit,” which is a specific series of operations performed on qubits. If you gave the classical program some initial arrangement of qubits, it would predict their final arrangement, after they had been through the quantum circuit. Jozsa proved that, so long as his algorithm simulated a circuit that didn’t entangle qubits, it could handle larger and larger numbers of qubits without taking an exponentially longer time to run.
Two researchers at the Technical University of Munich, Robert König and Beatriz Dias, reformulated mathematical ways of measuring “magic” and defined a less familiar way of quantifying quantumness related to how intensely particles interact.
C. Hohmann Munich Center for Quantum Science and Technology
In other words, he showed that an entanglement-free quantum circuit was easy to simulate on a classical computer. In a computational sense, the circuit wasn’t intrinsically quantum. The collection of all such non-entangling circuits (or, equivalently, all arrangements of qubits that might come out of these non-entangling circuits) formed something of a classically simulable island in a vast quantum sea.
In this sea were the states resulting from truly quantum circuits, the ones for which a classical simulation might take billions of years. For this reason, researchers came to regard entanglement not just as a quantum property, but as a quantum resource: It was what you needed to reach the uncharted depths, where powerful quantum algorithms like Shor’s resided.
Today, entanglement is still the most studied quantum resource. “If you ask 99 out of 100 physicists [what makes quantum circuits powerful], the first thing that comes to mind is entanglement,” Fefferman said.
And active research into entanglement’s relationship with complexity continues. Fefferman and his collaborators, for instance, showed last year that for one particular class of quantum circuits, entanglement fully determines how hard the circuit is to classically simulate. “As soon as you get to a certain amount of entanglement,” Fefferman said, “you can actually prove hardness. There’s no [classical] algorithm that will work.”
But Fefferman’s proof holds for only one flavor of circuits. And even 20 years ago, researchers were already recognizing that entanglement alone failed to capture the richness of the quantum ocean.
“Despite the essential role of entanglement,” Jozsa and his collaborator wrote in their 2002 paper, “we argue that it is nevertheless misleading to view entanglement as a key resource for quantum computational power.”
The quest for quantumness, it turned out, was just beginning.
A Little Bit of Magic
Jozsa knew that entanglement was not the final word on quantumness, because four years before his work, the physicist Daniel Gottesman had shown otherwise. At a 1998 conference in Tasmania, Gottesman explained that, in a specific type of quantum circuit, the seemingly quintessential quantum quantity became a trifle for a classical computer to simulate.
In Gottesman’s method (which he discussed with the mathematician Emanuel Knill), the entangling operation cost essentially nothing. You could entangle as many qubits as you liked, and a classical computer could still keep up.
“This was one of the first surprises, the Gottesman-Knill theorem, in the ’90s,” Korzekwa said.
The ability to classically simulate entanglement seemed like a bit of a miracle, but there was a catch. The Gottesman-Knill algorithm couldn’t handle all quantum circuits, just those that stuck to the so-called Clifford gates. But if you added a “T gate,” a seemingly innocuous gadget that rotates a qubit in a particular way, their program would choke on it.
This T gate seemed to manufacture some sort of quantum resource — something intrinsically quantum that can’t be simulated on a classical computer. Before long, a pair of physicists would give the quantum essence produced by the forbidden T-gate rotation a catchy name: magic.
In 2004, Sergey Bravyi, then of the Landau Institute for Theoretical Physics in Russia, and Alexei Kitaev of the California Institute of Technology worked out two schemes for pulling off any quantum calculation: You could include T gates in the circuit itself. Or you could take a “magic state” of qubits that had been prepared with T gates by another circuit and feed it into a Clifford circuit. Either way, magic was essential for achieving full quantumness.
A decade later, Bravyi and David Gosset, a researcher at the University of Waterloo in Canada, worked out how to measure the amount of magic in a set of qubits. And in 2016, they developed a classical algorithm for simulating low-magic circuits. Their program took exponentially longer for every additional T gate, although the exponential growth isn’t quite as explosive as it is in other cases. They finally flexed the efficiency of their method by classically simulating a somewhat magical circuit with hundreds of Clifford gates and nearly 50 T gates.
The more “magic” an arrangement of qubits possesses, the harder it is for a classical computer to simulate that arrangement. In 2016, David Gosset, a researcher at the University of Waterloo, helped work out powerful ways of simulating systems with just a pinch of magic.
Perimeter Institute
Today, many researchers operate quantum computers in Clifford mode (or close to it), precisely because they can use a classical computer to check whether the buggy devices are working properly. The Clifford circuit “is so central to quantum computing it’s hard to overstate,” Gosset said.
A new quantum resource — magic — had entered the game. But unlike with entanglement, which started out as a familiar physical phenomenon, physicists weren’t sure if magic mattered much outside quantum computers. Recent results suggest it might.
In 2021, researchers identified certain phases of quantum matter that are guaranteed to have magic, much as many phases of matter have particular patterns of entanglement. “You need finer measures of computational complexity like magic to have a complete landscape of phases of matter,” said Timothy Hsieh, a physicist at the Perimeter Institute for Theoretical Physics who worked on the result. And Alioscia Hamma of the University of Naples, along with his colleagues, recently studied whether it would be possible — in theory — to reconstruct the pages of a diary swallowed by a black hole by observing solely the radiation it emits. The answer was yes, Hamma said, “if the black hole doesn’t have too much magic.”
For many physicists, Hamma included, the physical ingredients required to make a system extremely quantum seem clear. Some combination of entanglement and magic is likely necessary. Neither one alone is sufficient. If a state has a score of zero on either metric, you can simulate it on your laptop, with a bit of help either from Jozsa (if entanglement is zero) or from Bravyi and Gosset (if the magic is zero).
And yet the quantum quest continues, because computer scientists have long known that not even magic and entanglement together can really guarantee quantumness.
Fermionic Magic
The other quantum metric started to take shape nearly a quarter century ago. But until recently, it was the least developed of the three.
In 2001, the computer scientist Leslie Valiant discovered a way to simulate a third family of quantum tasks. Much as Jozsa’s technique focused on circuits without entangling gates, and the Bravyi-Gosset algorithm could cut through circuits without too many T gates, Valiant’s algorithm was restricted to circuits that lacked the “swap gate” — an operation that takes two qubits and exchanges their positions.
As long as you don’t exchange qubits, you can entangle them and infuse them with as much magic as you like, and you’ll still find yourself on yet another distinct classical island. But as soon as you start shuffling qubits around, you can work wonders beyond the ability of any classical computer.
It was “rather bizarre,” Jozsa said. “How can just swapping two qubits give you all that power?”
Within a matter of months, the theoretical physicists Barbara Terhal and David DiVincenzo had uncovered the source of that power. They showed that Valiant’s swap-gate-free circuits, which are known as “matchgate” circuits, were secretly simulating a well-known class of physics problems. Similar to how computers simulate growing galaxies or nuclear reactions (without actually being a galaxy or a nuclear reaction), matchgate circuits simulate a group of fermions, a family of elementary particles that contains electrons.
When swap gates are not used, the simulated fermions are noninteracting, or “free.” They never bump into one another. Problems involving free electrons are relatively easy for physicists to solve, sometimes even with pencil and paper. But when swap gates are used, the simulated fermions interact, crashing together and doing other complicated things. These problems are extremely hard, if not unsolvable.
Because matchgate circuits simulate the behavior of free, noninteracting fermions, they are easy to simulate classically.
But after the initial discovery, matchgate circuits went largely unexplored. They weren’t as relevant for mainstream quantum computing efforts, and they were much more difficult to analyze.
Sergii Strelchuk (top) and Joshua Cudby, mathematicians at the University of Cambridge, recently studied the mathematical properties of a new metric for quantumness.
Daniela Strelchuk (top); Theo Lewy
Sergii Strelchuk (left) and Joshua Cudby, mathematicians at the University of Cambridge, recently studied the mathematical properties of a new metric for quantumness.
Daniela Strelchuk (left); Theo Lewy
That changed over the past summer. Three groups of researchers independently brought the work of Bravyi, Gosset and their collaborators to bear on the problem — a serendipitous intersection of research that, at least in one case, was discovered when fermions came up over coffee (as they often do when physicists get together).
The teams coordinated the release of their findings in July.
All three groups essentially rejiggered the mathematical tools that the magic pioneers had developed to explore Clifford circuits and applied them to the realm of matchgate circuits. Sergii Strelchuk and Joshua Cudby of Cambridge focused on mathematically measuring the quantum resource that matchgate circuits lacked. Conceptually, this resource corresponds to “interactivity” — or how much the simulated fermions can sense each other. No interactivity is classically easy to simulate, and more interactivity makes simulations harder. But how much harder did an extra dollop of interactivity make the simulations? And were there any shortcuts?
“We had no intuition. We had to start from zero,” Strelchuk said.
The other two groups developed a way of breaking one harder-to-simulate state into a huge sum of easier-to-simulate states, all the while keeping track of where these easier states canceled out and where they added up.
The result was a sort of dictionary for porting classical simulation algorithms from the Clifford world to the matchgate world. “Basically everything they have for [Clifford] circuits can now be translated,” said Beatriz Dias, a physicist at the Technical University in Munich, “so we don’t have to reinvent all these algorithms.”
Now, faster algorithms can classically simulate circuits with a few swap gates. As with entanglement and magic, the algorithms take exponentially longer with the addition of each forbidden gate. But the algorithms represent a significant step forward.
Oliver Reardon-Smith, who worked with Korzekwa and Michał Oszmaniec of the Polish Academy of Sciences in Warsaw, estimates that their program can simulate a circuit with 10 costly swap gates 3 million times faster than earlier methods. Their algorithm allows classical computers to push a little deeper into the quantum sea, both bolstering our ability to confirm the performance of quantum computers and expanding the region where no killer quantum app can live.
“Simulating quantum computers is useful for many people,” Reardon-Smith said. “We want to do it as quickly and cheaply as we can.”
As for what to call the “interactivity” resource that swap gates produce, it still doesn’t have an official name; some simply call it magic, and others throw around impromptu terms like “nonfermionic stuff.” Strelchuk prefers “fermionic magic.”
Further Islands on the Horizon
Now researchers are growing comfortable quantifying quantumness using three metrics, each corresponding to one of three classical simulation methods. If a collection of qubits is largely unentangled, has little magic, or simulates a bunch of nearly free fermions, then researchers know they can reproduce its output on a classical laptop. Any quantum circuit with a low score on one of these three quantum metrics lies in the shallows just off the shores of a classical island, and certainly won’t be the next Shor’s algorithm.
“Ultimately, [studying classical simulation] does help us understand where quantum advantage can be found,” Gosset said.
Kamil Korzekwa (top) and Oliver Reardon-Smith recently developed a way to classically simulate a quantum simulation of (relatively) noninteracting particles that runs 3 million times faster than earlier methods.
Maria Stawska (top); Rosalyn Leaman
Kamil Korzekwa (left) and Oliver Reardon-Smith recently developed a way to classically simulate a quantum simulation of (relatively) noninteracting particles that runs 3 million times faster than earlier methods.
Maria Stawska (left); Rosalyn Leaman
But the more familiar researchers get with these three different ways of measuring how quantum a bunch of qubits can be, the more misguided the initial dream of finding a single number that captures all aspects of quantumness seems. In a strictly computational sense, any given circuit must have a single shortest time required to simulate it using the fastest of all possible algorithms. Yet entanglement, magic and fermionic magic are quite different from each other, so the prospect of unifying them under one grand quantum metric to calculate that absolute shortest run time seems remote.
“I don’t think that question makes any sense,” Jozsa said. “There’s no kind of single thing which if you shovel more of it in, you get more power.”
Rather, the three quantum resources seem to be artifacts of the mathematical languages used to cram the complexity of quantumness into simpler frameworks. Entanglement emerges as a resource when you practice quantum mechanics in the way Schrödinger outlined, which uses his eponymous equation to predict how a particle’s wave function will change in the future. This is the textbook version of quantum mechanics, but it isn’t the only version.
When Gottesman developed his method of simulating Clifford circuits, he based it on an older variety of quantum mechanics developed by Werner Heisenberg. In Heisenberg’s mathematical language, the state of the particles doesn’t change. Instead, it’s the “operators” — the mathematical objects you might use to predict the odds of some observation — that evolve. Restricting one’s view to free fermions involves viewing quantum mechanics through yet another mathematical lens.
Each mathematical language eloquently captures certain aspects of quantum states, but at the price of garbling some other quantum property. These clumsily expressed properties then become the quantum resource in that mathematical framework — the magic, the entanglement, the fermionic magic. Overcoming this limitation and identifying one quantum feature to rule them all, Jozsa speculates, would require learning all the possible mathematical languages for expressing quantum mechanics and looking for universal traits they all might share.
That’s not a particularly serious research proposal, but researchers are studying further quantum languages beyond the major three, and the corresponding quantum resources that come along with them. Hsieh, for instance, is interested in phases of quantum matter that produce nonsensical negative probabilities when analyzed in a standard way. This negativity, he has found, can define certain phases of matter just as magic can.
Decades ago, it seemed as if the answer to the question of what makes a system quantum was obvious. Today, researchers know better. After 20 years exploring the first few classical islands, many suspect their voyage may never come to a close. Even as they continue to refine their understanding of where quantum power is not, they know they may never be able to say precisely where it is.
