However, not all questions about quantum systems are easy to answer using quantum algorithms. Some questions are equally easy for classical algorithms running on a regular computer, while others are difficult for both classical and quantum algorithms.
To understand what quantum algorithms and the computers that can run them can do, researchers often analyze mathematical models called spin systems, which capture the fundamental behavior of an array of interacting atoms. They can then ask: What happens to the spin system if it is left at a given temperature? Because the stable state, called thermal equilibrium, determines many other properties, researchers have long sought to develop algorithms to find the equilibrium state.
Whether these algorithms actually benefit from quantum properties depends on the temperature of the spin system in question. At very high temperatures, known classical algorithms can easily do the job. As the temperature decreases and quantum phenomena become stronger, the problem becomes more difficult. In some systems, it is too difficult even for a quantum computer to solve in a reasonable amount of time. But the details of all this are still unclear.
“When do we go to a space where quantum is needed, and when do we go to a space where quantum is not helpful at all?” he said. Ewin Tang“Not much is known,” says a researcher at the University of California, Berkeley, and one of the authors of the new results.
In February, Tang and Moitra, along with two other MIT computer scientists and postdocs, began thinking about the heat equilibrium problem. Ainesh Boxi And Moitra’s graduate students Alan Liu. In 2023, they all cooperated. Groundbreaking quantum algorithm They had taken on other tasks related to spin systems and were looking for a new challenge.
“When we work together, everything just flows naturally,” Park said. “It’s really great.”
Before the 2023 breakthrough, the three MIT researchers had never studied quantum algorithms. Their background was in learning theory, a subfield of computer science that focuses on statistical analysis algorithms. But like ambitious newcomers everywhere, they saw their relative naivety as an advantage, a way of looking at problems from a new perspective. “One of our strengths is that we don’t know much about quantum,” Moitra says. “The only quantum we know is what Ewin taught us.”
The team decided to focus on relatively high temperatures, as the researchers suspected that fast quantum algorithms might exist, although no one had proven it. Soon after, they found a way to apply an old technique in learning theory to a new fast algorithm. But while they were writing their paper, another team came up with something like this: Similar results: Evidence of ~ Promising algorithm What was developed last year will work well at high temperatures. They came to mind.
Sudden death reborn
Somewhat disappointed at coming in second place, Tang and her collaborators began exchanging letters like this: Alvaro AlhambraPhysicists at the Madrid Institute of Theoretical Physics and one of the authors of the competing paper. They wanted to find out the difference between the results they had independently achieved. But when Alhambra read the draft proofs of the four researchers, he was surprised to find that they had proven something else in the middle. In all spin systems in thermal equilibrium, entanglement completely disappears above a certain temperature. “I said to them, ‘Oh, this is really, really important,’” Alhambra said.
