However, not all questions about quantum systems can be easily answered using quantum algorithms: some questions are equally easy with classical algorithms running on ordinary computers, and some questions are difficult with both classical and quantum algorithms.
To understand where quantum algorithms and the computers that can run them might excel, researchers often analyze mathematical models called spin systems, which capture the fundamental behavior of arrangements of interacting atoms. A question then arises: What happens if you leave a spin system at a particular temperature? The state that a spin system settles into is called thermal equilibrium, and it determines many of its other properties. So researchers have long been working on developing algorithms to find the equilibrium state.
Whether these algorithms truly benefit from their quantum nature depends on the temperature of the spin system in question. At very high temperatures, they can be easily handled by known classical algorithms. As the temperature decreases and quantum phenomena become stronger, the problems become harder. For some systems, even quantum computers will have difficulty solving them in a reasonable time. But all these details remain unclear.
“When are the areas where quantum is needed, and when are the areas where quantum doesn’t work,” said Ewin Tan, a researcher at the University of California, Berkeley and one of the authors of the new study. “We don’t really know.”
In February, Tan and Moitra began thinking about the thermal equilibrium problem with two other MIT computer scientists, postdoctoral researcher Ainesh Bakshi and Moitra’s graduate student Allen Liu. In 2023, they were all collaborating on a breakthrough quantum algorithm for a different task involving spin systems and were looking for a new challenge.
“When we work together, things run smoothly,” Bakshi says. “It’s great.”
Until their 2023 breakthrough, the three MIT researchers had never worked on a quantum algorithm. Their backgrounds are in learning theory, a subfield of computer science that focuses on algorithms for statistical analysis. But like any ambitious startup, they saw their relative ignorance as an advantage — a way to look at problems with fresh eyes. “One of our strengths is that we don’t know much about quantum,” Moitra says. “The only quantum we know is the quantum that Eowyn taught us.”
The team decided to focus on relatively high temperatures. The researchers had suspected that fast quantum algorithms existed, even though no one had been able to prove it. Soon, they found a way to apply old techniques from learning theory to their new, faster algorithms. But as they were writing their paper, another team published similar results, proving that a promising algorithm developed the previous year also worked well at high temperatures. They’d been beaten to it.
Sudden death revives
Somewhat disappointed by their second place finish, Tang and his collaborators began contacting Álvaro Alhambra, a physicist at the Madrid Institute of Theoretical Physics and one of the authors of the rival paper. They wanted to clarify the differences in their own results. But when Alhambra looked over the four researchers’ draft proof, he was surprised to see that at an intermediate stage they had proven something else: that in any spin system in thermal equilibrium, entanglement completely disappears above a certain temperature. “I told them, ‘This is very, very important,'” Alhambra says.
