Quantum algorithm excels at finding local minima of many-body systems

Many physicists and engineers have recently been trying to demonstrate the potential of quantum computers for tackling some problems that are particularly demanding and are difficult to solve for classical computers. A task that has been found to be challenging for both quantum and classical computers is finding the ground state (i.e., lowest possible energy state) of systems with multiple interacting quantum particles, called quantum many-body systems.

When one of these systems is placed in a thermal bath (i.e., an environment with a fixed temperature that interacts with the systems), it is known to cool down without always reaching its ground state. In some instances, a quantum system can get trapped at a so-called local minimum; a state in which its energy is lower than other neighboring states but not at the lowest possible level.

Researchers at California Institute of Technology and the AWS Center for Quantum Computing recently showed that while finding the local minimum for a system is difficult for classical computers, it could be far easier for quantum computers.

Their paper, published in Nature Physics, introduces a new quantum algorithm that simulates natural cooling processes, which was successfully used to predict the local minima of quantum many-body systems.

"This paper emerged from a fundamental question: should quantum theorists focus solely on ground states when they're often physically unrealizable due to the inherent computational hardness in finding them?" Hsin-Yuan (Robert) Huang, co-first author of the paper, told Phys.org.

"In machine learning, local minima—not global minima—are what practical algorithms find and use successfully. This sparked our curiosity about local minima in quantum systems."

The recent work by Huang and his colleagues combines approaches from three different areas of physics research. These include the study of local minima and their physical relevance, the ongoing quest to demonstrate the advantages of quantum computers in optimization problems and recent insights from the field of quantum thermodynamics.

"This convergence enabled us to define quantum local minima through thermal perturbations—a physically meaningful approach that mirrors what happens when nature cools a physical system," said Huang. "Our objective was to determine if finding local minima could provide a provable quantum advantage while maintaining direct connections to natural physical processes."

To tackle the problem of finding a local minimum, the researchers first formalized the natural cooling process of quantum systems. Instead of seeking ground states, which are global energy minima, they focused on local minima, states in which small perturbations no longer decrease the energy of a system in a thermal bath.

"Our analysis proceeded to show that the problem of cooling to local minima is classically hard and quantumly easy," said Leo Zhou.

"To establish classical hardness, we provide explicit construction of quantum systems where any local minima can be used to encode universal quantum computation, a task widely believed to be classically intractable.

"We then developed a quantum thermal gradient descent algorithm, which enables a quantum computer to efficiently find a local minimum by mimicking natural cooling processes."

The greatest technical challenge that the researchers had to overcome for this study was proving that some classically hard Hamiltonians have no suboptimal local minima, or that, in other words, their energy landscapes have a perfect bowl-like shape.

To achieve this, they employed clever constructions from quantum complexity theory and sophisticated mathematical tools for analyzing the effects of thermal perturbations on energy landscapes.

"We found that cooling physical systems to local minima is universal for quantum computation," said Huang.

"In other words, quantum computers can efficiently find local minima while classical computers cannot, assuming that quantum computers are more powerful than classical ones. This result is compelling because it has a clear physical interpretation: when nature cools a quantum system, it effectively solves the problem of finding local minima under thermal perturbations."

"Furthermore, our result points to a new approach to characterize quantum many-body systems that challenges conventional wisdom," said Zhou.

"Instead of focusing solely on ground states, we can study their local minima and overall energy landscape. Optimizing over the energy landscape can even lead to discovery of new physics—for example, by finding an anomalous local minimum with unexpected physical properties."

The new quantum algorithms developed by Huang and his colleagues were found to formalize and replicate the natural cooling of quantum systems. Using this algorithm, the researchers showed that quantum computers could significantly enhance energy optimization, outperforming classical computers by a large margin.

"After classical algorithms reach their 'best' solution, our quantum algorithm could find even lower energy states—potentially transforming computational approaches in materials science, chemistry, and physics," explained Huang.

The results attained by this team of researchers highlight the potential of quantum computing systems for finding the local minima of quantum systems. In their next studies, Huang and his colleagues plan to build on their recent work by further testing their algorithm and applying it to a broader range of scenarios.

"First, we aim to characterize physically relevant quantum systems with favorable energy landscapes where our approach could provide practical quantum advantages," said Huang. "Second, we're investigating whether these techniques could yield quantum advantages for classical optimization problems—potentially expanding the impact beyond quantum systems."

As part of their next studies, the researchers are planning to carry out experimental demonstrations of their proposed method using near-term quantum devices. In addition, they will try to engineer synthetic quantum processes that could outperform the natural cooling capabilities of quantum systems.

"Our ultimate goal is not only to bridge the gap between theoretical quantum advantage and practical applications but also to pioneer new ways of understanding and controlling quantum many-body systems," added Huang and Zhou.

© 2025 Science X Network