But not all questions about quantum systems are easier to answer using quantum algorithms. Some are equally easy for classical algorithms, which run on ordinary computers, while others are hard for both classical and quantum ones.
To understand where quantum algorithms and the computers that can run them might offer an advantage, researchers often analyze mathematical models called spin systems, which capture the basic behavior of arrays of interacting atoms. They then might ask: What will a spin system do when you leave it alone at a given temperature? The state it settles into, called its thermal equilibrium state, determines many of its other properties, so researchers have long sought to develop algorithms for finding equilibrium states.
Whether those algorithms really benefit from being quantum in nature depends on the temperature of the spin system in question. At very high temperatures, known classical algorithms can do the job easily. The problem gets harder as temperature decreases and quantum phenomena grow stronger; in some systems it gets too hard for even quantum computers to solve in any reasonable amount of time. But the details of all this remain murky.
“When do you go to the space where you need quantum, and when do you go to the space where quantum doesn’t even help you?” said Ewin Tang, a researcher at the University of California, Berkeley, and one of the authors of the new result. “Not that much is known.”
In February, Tang and Moitra began thinking about the thermal equilibrium problem together with two other MIT computer scientists: a postdoctoral researcher named Ainesh Bakshi and Moitra’s graduate student Allen Liu. In 2023, they’d all collaborated on a groundbreaking quantum algorithm for a different task involving spin systems, and they were looking for a new challenge.
“When we work together, things just flow,” Bakshi said. “It’s been awesome.”
Before that 2023 breakthrough, the three MIT researchers had never worked on quantum algorithms. Their background was in learning theory, a subfield of computer science that focuses on algorithms for statistical analysis. But like ambitious upstarts everywhere, they viewed their relative naïveté as an advantage, a way to see a problem with fresh eyes. “One of our strengths is that we don’t know much quantum,” Moitra said. “The only quantum we know is the quantum that Ewin taught us.”
The team decided to focus on relatively high temperatures, where researchers suspected that fast quantum algorithms would exist, even though nobody had been able to prove it. Soon enough, they found a way to adapt an old technique from learning theory into a new fast algorithm. But as they were writing up their paper, another team came out with a similar result: a proof that a promising algorithm developed the previous year would work well at high temperatures. They’d been scooped.
Sudden Death Reborn
A bit bummed that they’d come in second, Tang and her collaborators began corresponding with Álvaro Alhambra, a physicist at the Institute for Theoretical Physics in Madrid and one of the authors of the rival paper. They wanted to work out the differences between the results they’d achieved independently. But when Alhambra read through a preliminary draft of the four researchers’ proof, he was surprised to discover that they’d proved something else in an intermediate step: In any spin system in thermal equilibrium, entanglement vanishes completely above a certain temperature. “I told them, ‘Oh, this is very, very important,’” Alhambra said.