  Finding ground states of quantum many-body systems is known to be hard for
both classical and quantum computers. As a result, when Nature cools a quantum
system in a low-temperature thermal bath, the ground state cannot always be
found efficiently. Instead, Nature finds a local minimum of the energy. In this
work, we study the problem of finding local minima in quantum systems under
thermal perturbations. While local minima are much easier to find than ground
states, we show that finding a local minimum is computationally hard for
classical computers, even when the task is to output a single-qubit observable
at any local minimum. In contrast, we prove that a quantum computer can always
find a local minimum efficiently using a thermal gradient descent algorithm
that mimics the cooling process in Nature. To establish the classical hardness
of finding local minima, we consider a family of two-dimensional Hamiltonians
such that any problem solvable by polynomial-time quantum algorithms can be
reduced to finding ground states of these Hamiltonians. We prove that for such
Hamiltonians, all local minima are global minima. Therefore, assuming quantum
computation is more powerful than classical computation, finding local minima
is classically hard and quantumly easy.
