But not all questions about quantum systems are easy to answer using quantum algorithms. Some are equally simple for classical algorithms, which work on ordinary computers, while others are difficult for both classical and quantum.
To understand where quantum algorithms and computers can provide an advantage, researchers often analyze mathematical models called spin systems, which capture the fundamental behavior of arrays of interacting atoms. They might ask: What will a spin system do if you leave it alone at a given temperature? The state it lives in, called its thermal equilibrium state, determines many of its other properties, so researchers have long sought to develop algorithms for finding equilibrium conditions.
Whether those algorithms actually benefit from being quantum in nature depends on the temperature of the spin system in question. At very high temperatures, well-known algorithms can easily do the job. The problem becomes more difficult as the temperature decreases and the quantum phenomena increase in intensity; in some systems it is too difficult for even quantum computers to solve in any sufficient time. But the details of all this remain sketchy.
“When do you go to a place where you need a quantum, and when do you go to a place where a quantum is useless?” said Ewin Tang, a researcher at the University of California, Berkeley, and one of the authors of the new result. “Not much is known about that.”
In February, Tang and Moitra began thinking about the thermal scaling problem along with two other MIT computer scientists: postdoctoral researcher Ainesh Bakshi and Moitra’s student Allen Liu. In 2023, they were all going to collaborate on a basic quantum algorithm for a different task involving quantum systems, and they were looking for a new challenge.
“When we work together, things go well,” said Bakshi. “It’s been great.”
Before that 2023 breakthrough, the three MIT researchers had never worked on quantum algorithms. Their background was in artificial intelligence, a subfield of computer science that focuses on algorithms for statistical analysis. But like ambitious developers everywhere, they see their relative naïveté as an advantage, a way to see a problem with fresh eyes. “One thing that strengthens us is that we don’t know many quanta,” said Moitra. “The only quantum we know is the quantum Ewin taught us.”
The team decided to focus on very high temperatures, where the researchers suspected that the fastest quantum algorithms would exist, although no one has been able to prove it. Soon enough, they found a way to adapt the old method from learning theory to a new, faster algorithm. But as they were writing their paper, another team came up with the same result: proof that a promising algorithm developed last year would work well at high temperatures. They have been fired.
Sudden Death Reborn
Surprised that they would come in second, Tang and his 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 make a difference between the results they had achieved independently. But when Alhambra read the first draft of the evidence of the four researchers, he was surprised to find that they proved something else in the middle step: In any system of circulation in thermal equilibrium, the adhesion disappears above a certain temperature. “I told them, ‘Oh, this is very important,'” Alhambra said.