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.

arXiv comment9+80 pages, 4 figures

References in corpus (39)

• The density-matrix renormalization group in the age of matrix product states
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• An adaptive variational algorithm for exact molecular simulations on a quantum computer
• Stochastic series expansion method with operator-loop update
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Concepts and methods in the theory of open quantum systems
• Quantum Computation as Geometry
• Studying Two Dimensional Systems With the Density Matrix Renormalization Group
• Restricted-Boltzmann-Machine Learning for Solving Strongly Correlated Quantum Systems
• Quantum Metropolis Sampling
• Machine Learning Topological States
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Symmetries and many-body excited states with neural-network quantum states
• Fermionic neural-network states for ab-initio electronic structure
• OrbNet: Deep Learning for Quantum Chemistry Using Symmetry-Adapted Atomic-Orbital Features
• Provably efficient machine learning for quantum many-body problems
• Variational optimization with infinite projected entangled-pair states
• Universal Lindblad equation for open quantum systems
• Gradient methods for variational optimization of projected entangled-pair states
• The problem of equilibration and the computation of correlation functions on a quantum computer
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Isometric Tensor Network States in Two Dimensions
• Completely positive master equation for arbitrary driving and small level spacing
• Restricted Boltzmann Machines for Quantum States with Nonabelian or Anyonic Symmetries
• Universal Quantum Hamiltonians
• Neural Gutzwiller-projected variational wave functions
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Single-ancilla ground state preparation via Lindbladians
• Gauge Invariant and Anyonic Symmetric Transformer and RNN Quantum States for Quantum Lattice Models
• Thermal State Preparation via Rounding Promises
• Randomness induced spin-liquid-like phase in the spin-$1/2$ $J_1-J_2$ triangular Heisenberg model
• Conversion of projected entangled pair states into a canonical form
• Improved machine learning algorithm for predicting ground state properties
• U(1) symmetric recurrent neural networks for quantum state reconstruction
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• On the complexity of finding a local minimizer of a quadratic function over a polytope

Cited by in corpus (8)

• 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
• Describing Trotterized Time Evolutions on Noisy Quantum Computers via Static Effective Lindbladians
• Consensus-based qubit configuration optimization for variational algorithms on neutral atom 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
• Trajectory-independent speed limits for controlled open quantum systems