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.