🔢 mathematics

Local minima in quantum systems

This paper demonstrates that while finding local energy minima in quantum systems is computationally hard for classical computers, it can be efficiently solved by quantum computers using a thermal gradient descent algorithm, thereby establishing a scenario where quantum computation outperforms classical computation even for tasks simpler than finding ground states.

Original authors: Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou

Published 2026-08-31

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the physical world, nature is a relentless optimizer. When a hot object cools down, it seeks the lowest possible energy state, a condition physicists call the ground state. This process is fundamental to how materials form, how chemical reactions occur, and how the universe settles into stability. For decades, scientists have tried to use computers to predict these lowest-energy states for complex systems made of many interacting particles, such as the electrons in a new material or the atoms in a protein. However, finding the absolute lowest point in these systems is notoriously difficult. It is a problem so hard that even the most powerful classical computers, the kind we use today, struggle to solve it for many interesting cases. Furthermore, theoretical work suggests that finding ground states is QMA-hard, meaning it is expected to be intractable even for quantum computers in some instances.

This difficulty arises because the landscape of possible energy states is often filled with traps. Imagine a mountain range where a hiker wants to reach the deepest valley. If the terrain is rugged, the hiker might get stuck in a small, shallow dip that looks like the bottom from a distance but is actually much higher than the true valley floor. In physics, these shallow dips are called local minima. When nature cools a system, it often gets stuck in these local minima rather than finding the true ground state. This is why some materials, like certain magnetic glasses, never reach their theoretical lowest energy, even after cooling for a long time. Instead, they settle into a state that is stable but not the best possible one.

A team of researchers at the California Institute of Technology, Google Quantum AI, and the Massachusetts Institute of Technology has now investigated this phenomenon of getting stuck in local minima. They asked a specific question: if nature cannot always find the perfect ground state, can a computer find a local minimum instead? And if so, is that task easier for a classical computer or a quantum one? Their work reveals a surprising twist in the story of quantum optimization. They found that while finding a local minimum is trivial for a classical computer under one set of rules, it becomes a task that is easy for a quantum computer but hard for a classical one under the rules that actually govern how nature cools things down.

To understand their discovery, one must first distinguish between two ways a system can be nudged or perturbed. The researchers considered the first type, which involves changing a system using reversible, mathematical operations known as local unitary perturbations. In this scenario, the energy landscape is filled with an overwhelming number of local minima. In fact, almost any random state of the system is a local minimum. Because there are so many of them, a classical computer can easily find one; it is like walking into a vast, flat plain where every step is a local minimum. The problem is so easy that it is essentially trivial, but it does not reflect how nature actually works, because nature cools systems through irreversible interactions with a heat bath, not through reversible mathematical tricks.

The researchers then turned to the second type of perturbation, which mimics the real physical process of cooling. They modeled a system interacting with a thermal bath, a reservoir of heat at a specific temperature. In this realistic setting, the system evolves irreversibly, losing energy to the environment. Here, the landscape changes dramatically. The researchers proved that for a quantum computer, finding a local minimum under these thermal conditions is efficient. They developed a method called quantum thermal gradient descent, which mimics the cooling process. By following the direction where the energy drops most steeply, a quantum computer can reliably find a local minimum in a reasonable amount of time, regardless of where it starts.

The most significant finding, however, concerns the difficulty for classical computers. The researchers constructed a specific family of two-dimensional quantum systems where the ground state encodes the result of a complex quantum calculation. They proved that for these specific systems, there are no "bad" local minima. Every local minimum is actually a global minimum, meaning the ground state. This creates a smooth, bowl-shaped energy landscape where the only place to get stuck is at the very bottom. Because finding the ground state for these systems is known to be a task that is easy for quantum computers but hard for classical ones (assuming quantum computation is more powerful than classical computation), the researchers concluded that finding a local minimum in this thermal setting is also hard for classical computers. If a classical computer could efficiently find a local minimum here, it would imply that classical computers could simulate any quantum calculation, a possibility that most experts believe is false.

This work establishes a clear separation between the capabilities of classical and quantum machines. It shows that while classical computers can easily find local minima in artificial, reversible scenarios, they hit a wall when faced with the irreversible, thermal processes that govern the real world. In contrast, quantum computers can navigate these thermal landscapes efficiently. The study suggests that the local minimum problem offers a new avenue for quantum advantage. Instead of trying to solve the notoriously difficult problem of finding the absolute ground state for every system, quantum computers can efficiently find the stable, low-energy states that nature actually produces. This provides a physically relevant problem where quantum machines can outperform classical ones, potentially helping scientists understand the behavior of materials and chemical systems that have so far remained out of reach.

The researchers also explored why some systems get stuck in suboptimal states while others do not. They analyzed a simple magnetic chain and found that without an external magnetic field, the system can get trapped in many different configurations with domain walls, acting as suboptimal local minima. However, when a strong external field is applied, these traps disappear, and the system flows smoothly to its true ground state. This mirrors the behavior of the complex systems they studied: the shape of the energy landscape determines whether a system can find its lowest energy state or if it remains stuck. Their findings suggest that many physical systems of interest might have "nice" energy landscapes with no suboptimal traps, making them ideal candidates for quantum optimization algorithms that mimic natural cooling.

Ultimately, this paper reframes the challenge of quantum optimization. It moves away from the abstract goal of finding the perfect ground state and focuses on the practical reality of finding the stable states that nature settles into. By proving that this task is classically hard (under standard complexity assumptions) but quantumly easy, the researchers have identified a concrete problem where quantum computers can demonstrate their superiority. This is not just a theoretical curiosity; it points toward a future where quantum machines can solve problems in physics and chemistry that are currently intractable, by following the same cooling principles that the universe has used since its beginning.

Technical Summary: Local Minima in Quantum Systems

Problem Statement
Finding the ground state (global minimum) of a quantum many-body system is a central problem in physics and chemistry, known to be QMA-hard for local Hamiltonians. Consequently, ground states are not always efficiently findable by classical or quantum computers, and natural cooling processes often fail to reach the ground state, settling instead into local minima. This work investigates the computational complexity of finding these local minima in quantum systems under two distinct definitions of perturbation: local unitary perturbations and thermal perturbations. The central question is whether finding a local minimum is computationally tractable for classical and quantum computers, and how the definition of the perturbation affects the energy landscape.

Methodology and Definitions
The authors define a local minimum in a quantum system as a state where the expectation value of the Hamiltonian $H$ does not decrease under small perturbations. They analyze two specific types of perturbations:

Local Unitary Perturbations: Modeled as short-time unitary evolutions generated by sums of few-body Hermitian operators (analogous to steps in variational quantum eigensolvers). The tangent space is defined by these unitary directions.
Thermal Perturbations: Modeled as the irreversible evolution of a system coupled to a low-temperature thermal bath. This is described by a master equation involving thermal Lindbladians $\mathcal{L}_{\beta, \tau, H}^a$ , which depend on the system Hamiltonian $H$ , inverse temperature $\beta$ , and a characteristic time scale $\tau$ . Crucially, these perturbations are irreversible ( $\alpha_a \geq 0$ ), reflecting thermodynamic cooling.

The complexity of finding an $\epsilon$ -approximate local minimum is defined as the task of outputting the expectation value of a local observable for any such local minimum.

Key Contributions and Results

1. Local Minima under Local Unitary Perturbations (Classically Easy)
The authors prove that finding a local minimum under local unitary perturbations is classically trivial.

Energy Landscape: They demonstrate that for any local Hamiltonian, the energy landscape under local unitary perturbations contains a "barren plateau." A random $n$ -qubit pure state is, with high probability, an approximate local minimum.
Complexity: Because the number of such local minima is doubly exponential and their local properties are exponentially close to the maximally mixed state, a classical algorithm can efficiently output the expectation value of a local observable for a local minimum (e.g., by simply outputting the trace of the observable divided by $2^n$ ). This renders the problem classically easy, despite the difficulty of finding the ground state.

2. Local Minima under Thermal Perturbations (Quantumly Easy, Classically Hard for Specific Families)
In stark contrast, the authors establish that finding a local minimum under thermal perturbations is a problem that is easy for quantum computers but hard for classical computers (assuming $\text{BPP} \neq \text{BQP}$ ), specifically for a certain class of Hamiltonians.

Quantum Algorithm (Thermal Gradient Descent): The authors propose a "Quantum Thermal Gradient Descent" algorithm. Mimicking Nature's cooling process, this algorithm iteratively applies thermal Lindbladian evolutions in directions where the energy gradient is negative. They prove that this algorithm converges to an $\epsilon$ -approximate local minimum in polynomial time, $poly(n, 1/\epsilon, \beta, \tau)$ , for any local Hamiltonian. The algorithm relies on efficient simulation of thermal Lindbladians and the estimation of energy gradients using block-encoding and quantum singular value transform (QSVT) techniques.
Classical Hardness via BQP-Hard Hamiltonians: To prove classical hardness, the authors construct a family of geometrically local 2D Hamiltonians ( $H_C$ ) based on a modified Kitaev circuit-to-Hamiltonian construction. In these Hamiltonians, the ground state encodes the output of an arbitrary quantum circuit $C$ .
- No Suboptimal Local Minima: The most technically significant result is a proof that for this specific family of 2D Hamiltonians, all approximate local minima under low-temperature thermal perturbations are approximate global minima (ground states). The energy landscape possesses a "nice bowl shape" where quantum gradient descent efficiently finds the ground state.
- Reduction: Since finding the ground state of these specific Hamiltonians is equivalent to simulating a quantum circuit (BQP-hard), and finding a local minimum is equivalent to finding the ground state for this specific family, finding a local minimum is universal for quantum computation for this class. Therefore, under the assumption that classical computers cannot efficiently simulate quantum circuits ( $\text{BPP} \neq \text{BQP}$ ), finding a local minimum under thermal perturbations is classically hard for these Hamiltonians. The authors note that for general local Hamiltonians (e.g., QMA-hard problems), the landscape may contain suboptimal local minima, and the algorithm may not reach the ground state efficiently.

Significance and Claims
The paper claims to identify a problem—finding local minima under thermal perturbations for specific Hamiltonian families—that offers a "quantumly tractable alternative" to the general ground state problem. While the general ground state problem is believed to be hard for both classical and quantum computers (QMA-hard), the local minimum problem under thermal perturbations is:

Quantumly Easy: Solvable efficiently by a proposed quantum algorithm that emulates natural cooling for any local Hamiltonian.
Classically Hard: Proven to be universal for quantum computation for a specific class of BQP-hard Hamiltonians (where all local minima are global), implying no efficient classical algorithm exists for these instances (assuming standard complexity conjectures).

The authors emphasize that this result is motivated by physical reality: natural systems in thermal baths routinely find local minima. The work suggests that the energy landscapes of certain physically relevant Hamiltonians (specifically those encoding quantum computations) may lack suboptimal local minima, allowing quantum thermal gradient descent to efficiently reach the ground state. This provides a physically motivated pathway for achieving superpolynomial quantum advantage, distinct from algorithms that rely on adiabatic paths or specific trial states.

The paper concludes by noting that while their proof applies to a specific family of BQP-hard Hamiltonians, the techniques developed (such as the negative gradient condition and perturbation analysis of energy gradients) may help characterize broader classes of Hamiltonians in physics and chemistry that exhibit similarly favorable energy landscapes.

More like this