Importance of the spectral gap in estimating ground-state energies
arXiv:2007.11582 · doi:10.1103/PRXQuantum.3.040327
Abstract
The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the LocalHamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the LocalHamiltonian is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics. In the setting of inverse-exponential precision, there is a surprising result that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space. We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.
arXiv comment32 pages, 4 figures. Comments welcome. v2: close to published version
References in corpus (47)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A variational eigenvalue solver on a quantum processor
- Quantum Computing
- An Area Law for One Dimensional Quantum Systems
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Schrieffer-Wolff transformation for quantum many-body systems
- Quantum Algorithms for Quantum Field Theories
- A Theory of Trotter Error
- Circuit complexity in quantum field theory
- Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
- The computational complexity of PEPS
- Undecidability of the Spectral Gap (short version)
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Variational quantum algorithms for discovering Hamiltonian spectra
- The power of quantum systems on a line
- Approximating Gibbs states of local Hamiltonians efficiently with PEPS
- Quantum Hamiltonian Complexity
- Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
- Quantum NP - A Survey
- Universal Quantum Hamiltonians
- Conformal field theories are magical
- Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
- Locality and digital quantum simulation of power-law interactions
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
- Error estimates for extrapolations with matrix-product states
- The computational difficulty of finding MPS ground states
- Toy Models of Holographic Duality between local Hamiltonians
- The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
- Size-Driven Quantum Phase Transitions
- Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- An Efficient Algorithm for approximating 1D Ground States
- Analysis and limitations of modified circuit-to-Hamiltonian constructions
- Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
- Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap
- The complexity of simulating local measurements on quantum systems
- Quantum Merlin Arthur with Exponentially Small Gap
- Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- History-state Hamiltonians are critical
- Quantum advantage from energy measurements of many-body quantum systems
- Translationally-Invariant Universal Quantum Hamiltonians in 1D
- Detailed Analysis of Circuit-to-Hamiltonian Mappings
- Simulating quantum circuits by adiabatic computation: improved spectral gap bounds
- Oracle complexity classes and local measurements on physical Hamiltonians
- Towards a quantum-inspired proof for IP = PSPACE
Cited by in corpus (8)
- Hunting for quantum-classical crossover in condensed matter problems
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- General conditions for universality of Quantum Hamiltonians
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- Universal noise-precision relations in variational quantum algorithms
- Efficient Quantum Cooling Algorithm for Fermionic Systems
- Towards a quantum-inspired proof for IP = PSPACE
- The Complexity of Approximating Critical Points of Quantum Phase Transitions