Local minima in quantum systems

Abstract

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.

9+80 pages, 4 figures

References in corpus (7)

• The density-matrix renormalization group in the age of matrix product states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Quantum Computation as Geometry
• Restricted-Boltzmann-Machine Learning for Solving Strongly Correlated Quantum Systems
• Single-ancilla ground state preparation via Lindbladians
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition

Cited by in corpus (7)

• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Generalized Gibbs ensembles in weakly interacting dissipative systems and digital quantum computers
• Consensus-based qubit configuration optimization for variational algorithms on neutral atom quantum systems
• Trajectory-independent speed limits for controlled open quantum systems
• Learning Variational Quantum Circuit Parameters with Classical Artificial Intelligence for Quantum Phase Transition Detection
• Diffusion in quantum state preparation: From passive cooling to system-bath engineering