Facebook
Twitter
Pocket
Reddit
Email
A striking new proof in quantum computational complexity might best be understood with a playful thought experiment. Run a bath, then dump a bunch of floating bar magnets into the water. Each magnet will flip its orientation back and forth, trying to align with its neighbors. It will push and pull on the other magnets and get pushed and pulled in return. Now try to answer this: What will be the system’s final arrangement?
This problem and others like it, it turns out, are impossibly complicated. With anything more than a few hundred magnets, computer simulations would take a preposterous amount of time to spit out the answer.
Now make those magnets quantum—individual atoms subject to the byzantine rules of the quantum world. As you might guess, the problem gets even harder. “The interactions become more complicated,” said Henry Yuen of Columbia University. “There’s a more complicated constraint on when two neighboring ‘quantum magnets’ are happy.”
These simple-seeming systems have provided exceptional insights into the limits of computation, in both the classical and quantum versions. In the case of classical or non-quantum systems, a landmark theorem from computer science takes us further. Called the PCP theorem (for “probabilistically checkable proof”), it says that not only is the final state of the magnets (or aspects related to it) incredibly difficult to compute, but so are many of the steps leading up to it. The complexity of the situation is even more drastic, in other words, with the final state surrounded by a zone of mysteriousness.
Another version of the PCP theorem, not yet proved, specifically deals with the quantum case. Computer scientists suspect that the quantum PCP conjecture is true, and proving it would change our understanding of the complexity of quantum problems. It’s considered arguably the most important open problem in quantum computational complexity theory. But so far, it’s remained unreachable.
Nine years ago, two researchers identified an intermediate goal to help us get there. They came up with a simpler hypothesis, known as the “no low-energy trivial state” (NLTS) conjecture, which would have to be true if the quantum PCP conjecture is true. Proving it wouldn’t necessarily make it any easier to prove the quantum PCP conjecture, but it would resolve some of its most intriguing questions.
Then in June of 2022, in a paper posted to the scientific preprint site arxiv.org, three computer scientists proved the NLTS conjecture. The result has striking implications for computer science and quantum physics.
“It’s very exciting,” said Dorit Aharonov of the Hebrew University of Jerusalem. “It will encourage people to look into the harder problem of the quantum PCP conjecture.”
To understand the new result, start by picturing a quantum system such as a set of atoms. Each atom has a property, called spin, that is somewhat similar to the alignment of a magnet, in that it points along an axis. But unlike a magnet’s alignment, an atom’s spin can be in a state that’s a simultaneous mixture of different directions, a phenomenon known as superposition. Further, it may be impossible to describe the spin of one atom without taking into account the spins of other atoms from distant regions. When this happens, those interrelated atoms are said to be in a state of quantum entanglement. Entanglement is remarkable, but also fragile and easily disrupted by thermal interactions. The more heat in a system, the harder it is to entangle it.
Now imagine cooling down a bunch of atoms until they approach absolute zero. As the system gets cooler and the patterns of entanglement become more stable, its energy decreases. The lowest possible energy, or “ground energy,” provides a concise description of the complicated final state of the entire system. Or at least it would, if it could be computed.
Beginning in the late 1990s, researchers discovered that for certain systems, this ground energy could never be computed in any reasonable time frame.
However, physicists thought that an energy level close to the ground energy (but not quite there) should be easier to compute, as the system would be warmer and less entangled, and therefore simpler.
Computer scientists disagreed. According to the classical PCP theorem, energies close to the final state are just as difficult to compute as the final energy itself. And so the quantum version of the PCP theorem, if true, would say that the precursor energies to the ground energy would be just as hard to calculate as the ground energy. Since the classical PCP theorem is true, many researchers think the quantum version should be true too. “Surely, a quantum version must be true,” said Yuen.
The physical implications of such a theorem would be profound. It would mean that there are quantum systems that retain their entanglement at higher temperatures—totally contradicting physicists’ expectations. But no one could prove that any such systems exist.
In 2013, Michael Freedman and Matthew Hastings, both working at Microsoft Research’s Station Q in Santa Barbara, California, narrowed down the problem. They decided to look for systems whose lowest and nearly lowest energies are hard to calculate according to just one metric: the amount of circuitry it would take for a computer to simulate them. These quantum systems, if they could find them, would have to retain rich patterns of entanglement at all of their lowest energies. The existence of such systems wouldn’t prove the quantum PCP conjecture—there might be other hardness metrics to consider—but it would count as progress.
Computer scientists didn’t know of any such systems, but they knew where to go looking for them: in the area of study called quantum error correction, where researchers create recipes of entanglement that are designed to protect atoms from disturbance. Each recipe is known as a code, and there are many codes of both greater and lesser stature.
At the end of 2021, computer scientists made a major breakthrough in creating quantum error-correcting codes of an essentially ideal nature. Over the ensuing months, several other groups of researchers built on those results to create different versions.
The three authors of the paper, who had been collaborating on related projects over the past two years, came together to prove that one of the new codes had all the properties needed to make a quantum system of the sort that Freedman and Hastings had hypothesized. In so doing, they proved the NLTS conjecture.
Their result demonstrates that entanglement is not necessarily as fragile and sensitive to temperature as physicists thought. And it supports the quantum PCP conjecture, suggesting that even away from the ground energy, a quantum system’s energy can remain virtually impossible to calculate.
“It tells us that the thing that seemed unlikely to be true is true,” said Isaac Kim of the University of California, Davis. “Albeit in some very weird system.”
Researchers believe that different technical tools will be needed to prove the full quantum PCP conjecture. However, they see reasons to be optimistic that the current result will bring them closer.
They are perhaps most intrigued by whether the newly discovered NLTS quantum systems—though possible in theory—can actually be created in nature, and what they would look like. According to the current result, they would require complex patterns of long-range entanglement that have never been produced in the laboratory, and which could only be built using astronomical numbers of atoms.
“These are highly engineered objects,” said Chinmay Nirkhe, a computer scientist at the University of California, Berkeley, and a co-author of the paper along with Anurag Anshu of Harvard University and Nikolas Breuckmann of University College London.
“If you have the ability to couple really faraway qubits, I believe you could realize the system,” said Anshu. “But there’s another journey to take to really go to the low-energy spectrum.” Added Breuckmann, “Maybe there is some part of the universe which is NLTS. I don’t know.”
Lead image: Kristina Armitage for Quanta Magazine.
This article was originally published on the Quanta Abstractions blog.
Get the Nautilus newsletter
Cutting-edge science, unraveled by the very brightest living thinkers.
