But not all questions about quantum systems are easier to answer using quantum algorithms. Some are just as simple for classical algorithms that run on regular computers, while others are challenging for both classical and quantum computers.
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 fundamental behavior of arrays of interacting atoms. They can then ask themselves: What will a spin system do if you leave it alone at a given temperature? The state it settles into, called thermal equilibrium, determines many of its other properties, so researchers have long sought to develop algorithms for finding equilibrium states.
Whether these algorithms actually take advantage of the quantum nature of the spin system depends on the temperature of the spin system in question. At very high temperatures, familiar classical algorithms can easily do the job. The problem becomes more complex as the temperature drops and the quantum effects become stronger; in some systems, it becomes too complex even for quantum computers to solve in a reasonable amount of time. But the details of all this remain unclear.
“When do you go to a space where you need quantum, and when do you go to a space where quantum doesn’t even help you?” he said. Ewin Tangresearcher at the University of California, Berkeley, and one of the authors of the recent result. “Not much is known.”
In February, Tang and Moitra started working with two other computer scientists from MIT: a postdoctoral researcher named Ainesh Bakshi and Moitra’s student Allen LiuIn 2023, everyone collaborated on breakthrough quantum algorithm to another task related to spin systems and were looking for a recent challenge.
“When we work together, everything just flows,” Bakshi said. “It was amazing.”
Before their breakthrough in 2023, the three MIT researchers had never worked on quantum algorithms. Their backgrounds were in learning theory, a subfield of computer science that focuses on algorithms for statistical analysis. But like ambitious novices everywhere, they saw their relative naivety as an asset, a way to look at the problem with fresh eyes. “One of our strengths is that we don’t know much about 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 scientists suspected that swift quantum algorithms existed, although no one had been able to prove it. They soon found a way to adapt an aged technique from learning theory to a recent swift algorithm. However, while they were writing their paper, another team came up with similar result:proof that promising algorithm developed last year will work well at high temperatures. They were hollowed out.
Sudden death reborn
Slightly disappointed that they came in second, Tang and her colleagues began corresponding with each other Álvaro Alhambraphysicist at the Institute of Theoretical Physics in Madrid and one of the authors of a competing paper. They wanted to determine the differences between results they had independently achieved. But when Alhambra read the four researchers’ initial draft of the proof, he was surprised to discover that they had proven something different in an intermediate step: in any spin system in thermal equilibrium, entanglement completely disappears above a certain temperature. “I told them, ‘Oh, this is very, very important,’” Alhambra said.