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 difficult for both classical and quantum algorithms.
To understand where quantum algorithms and the computers that can run them might offer an advantage, researchers often look at mathematical models called spin systems, which capture the basic behavior of interacting sets of atoms. They can then ask: What will a spin system do when left alone at a given temperature? The state it settles into, called a thermal equilibrium state, determines many of its other properties, so researchers have long sought to develop algorithms to find equilibrium states.
Whether such algorithms are actually useful because of their quantum nature depends on the temperature of the spin system in question. At very high temperatures, known classical algorithms can easily do the job. The problem gets more complicated as the temperature drops and quantum phenomena get stronger; in some systems it becomes too difficult even for quantum computers to solve in a reasonable time. But the details of all this remain murky.
“When do you go into the space where you need quantum and when do you go into the 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 new result. “Not much is known.”
In February, Tang and Moitra began thinking about the thermal equilibrium problem with two other MIT computer scientists: a postdoctoral researcher named Ainesh Bakshi and Moitra’s graduate student Allen LiuBy 2023, everyone had collaborated on An innovative 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 fantastic.”
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 newbies everywhere, they saw their relative naivety as an advantage — a way to look at a 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 researchers suspected fast quantum algorithms might exist, although no one had been able to prove it. They soon found a way to adapt an old technique from learning theory to a new, fast algorithm. But while they were writing their paper, another team came up with a new, fast quantum algorithm. similar result:a proof that a promising algorithm developed the previous year would work well at high temperatures. They had been discovered.
Sudden death reborn
A little disappointed at having come in second, Tang and his collaborators began to communicate with Alvaro Alhambraphysicist at the Institute of Theoretical Physics in Madrid and one of the authors of the rival paper. They wanted to determine the differences between the results they had obtained independently. But when Alhambra read a preliminary draft of the four researchers’ proof, he was surprised to find that they had shown something else in an intermediate step: In any spin system in thermal equilibrium, entanglement disappears completely above a certain temperature. “I told them, ‘Oh, this is very, very important,’” Alhambra said.