Quantum Hamiltonian Complexity

Abstract

Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a "Quantum Cook-Levin Theorem" to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi's polynomial time algorithm for Quantum 2-SAT.

v4: published version, 127 pages, introduction expanded to include brief introduction to quantum information, brief list of some recent developments added, minor changes throughout

References in corpus (30)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• A class of quantum many-body states that can be efficiently simulated
• Continuous variable quantum information: Gaussian states and beyond
• Matrix product states represent ground states faithfully
• Area laws in quantum systems: mutual information and correlations
• DMRG and periodic boundary conditions: a quantum information perspective
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Entropy scaling and simulability by Matrix Product States
• The power of quantum systems on a line
• N-representability is QMA-complete
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Approximating Gibbs states of local Hamiltonians efficiently with PEPS
• Stochastic Error Cancellation in Analog Quantum Simulation
• A new construction for a QMA complete 3-local Hamiltonian
• The computational difficulty of finding MPS ground states
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• Merlin-Arthur Games and Stoquastic Complexity
• Local tests of global entanglement and a counterexample to the generalized area law
• Entanglement area law from specific heat capacity
• Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
• Ground state connectivity of local Hamiltonians
• Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
• Local Hamiltonians in Quantum Computation
• Efficient algorithm for a quantum analogue of 2-SAT
• The Local Hamiltonian problem on a line with eight states is QMA-complete
• Monte Carlo simulation of stoquastic Hamiltonians
• On complexity of the quantum Ising model
• A linear time algorithm for quantum 2-SAT
• Area laws and efficient descriptions of quantum many-body states
• Approximation, Proof Systems, and Correlations in a Quantum World

Cited by in corpus (80)

• Adiabatic Quantum Computing
• Quantum Chemistry in the Age of Quantum Computing
• Quantum information processing with superconducting circuits: a review
• Circuit complexity in quantum field theory
• Quantum Entanglement in Neural Network States
• Comments on Holographic Complexity
• Machine Learning Topological States
• Liouville Action as Path-Integral Complexity: From Continuous Tensor Networks to AdS/CFT
• Complexity of Formation in Holography
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• Complexity Growth for AdS Black Holes
• Circuit complexity for free fermions
• Strategies for solving the Fermi-Hubbard model on near-term quantum computers
• Circuit complexity in interacting QFTs and RG flows
• Time Evolution of Complexity: A Critique of Three Methods
• Quantum Algorithmic Measurement
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Quantum Expander Codes
• Complexity of quantum impurity problems
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Holographic subregion complexity under a thermal quench
• Neural network representation of tensor network and chiral states
• Universal eigenstate entanglement of chaotic local Hamiltonians
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Eigenstate entanglement in the Sachdev-Ye-Kitaev model
• Surface Counterterms and Regularized Holographic Complexity
• Infrared-dressed entanglement of cold open-shell polar molecules for universal matchgate quantum computing
• Testing Holographic Conjectures of Complexity with Born-Infeld Black Holes
• Complexity of Holographic Superconductors
• Spread and Spectral Complexity in Quantum Spin Chains: from Integrability to Chaos
• Equilibration towards generalized Gibbs ensembles in non-interacting theories
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Correlation Length versus Gap in Frustration-Free Systems
• Approximation algorithms for quantum many-body problems
• Quantum Max-flow/Min-cut
• Action Growth in $f\left(R\right)$ Gravity
• Entanglement and correlation functions of the quantum Motzkin spin-chain
• Complexity growth of rotating black holes with a probe string
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Ground state connectivity of local Hamiltonians
• Evolutions of entanglement and complexity after a thermal quench in massive gravity theory
• Exponential clustering of bipartite quantum entanglement at arbitrary temperatures
• Importance of the spectral gap in estimating ground-state energies
• Optimizing sparse fermionic Hamiltonians
• Determining QMC simulability with geometric phases
• Variational wavefunctions for Sachdev-Ye-Kitaev models
• Holographic fluctuations and the principle of minimal complexity
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Entanglement dynamics in critical random quantum Ising chain with perturbations
• Effective dimension reduction with mode transformations: Simulating two-dimensional fermionic condensed matter systems
• The complexity of simulating local measurements on quantum systems
• Entropy Constraints for Ground Energy Optimization
• Holographic complexity in general quadratic curvature theory of gravity
• Higher-dimensional entanglement detection and quantum channel characterization using moments of generalized positive maps
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• Complexity growth of massive black hole with a probe string
• Statistical learnability of nuclear masses
• A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
• Sign problem in tensor network contraction
• Quantum advantage from energy measurements of many-body quantum systems
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• On connectivity-dependent resource requirements for digital quantum simulation of $d$-level particles
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• Entanglement Dynamics From Random Product States: Deviation From Maximal Entanglement
• Complexity growth of BTZ black hole in massive gravity with a null string
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
• A comparison of three ways to measure time-dependent densities with quantum simulators
• On efficiently solvable cases of Quantum k-SAT
• Extracting the spin excitation spectrum of a fermionic system using a quantum processor
• A multiprover interactive proof system for the local Hamiltonian problem
• Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
• Quantum fluctuation on the worldsheet of probe string in BTZ black hole
• Pinned QMA: The power of fixing a few qubits in proofs
• Measurement-Induced Phase Transition in a Disordered XX Spin Chain: A Real-Space Renormalization Group Study
• Predictive complexity of quantum subsystems
• Deviation from maximal entanglement for mid-spectrum eigenstates of local Hamiltonians
• Optimizing Sparse SYK
• On the characterization of partially entanglement breaking and annihilating channels
• Energy gap of quantum spin glasses: a projection quantum Monte Carlo study
• Quantum entropy thermalization