Quantum Hamiltonian Complexity
arXiv:1401.3916 · doi:10.1561/0400000066
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.
arXiv commentv4: 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 (74)
- Fault-tolerant quantum computation by anyons
- The density-matrix renormalization group
- Entanglement Entropy and Quantum Field Theory
- Entanglement in quantum critical phenomena
- Efficient classical simulation of slightly entangled quantum computations
- Entropy and Area
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- Efficient simulation of one-dimensional quantum many-body systems
- Entanglement entropy and conformal field theory
- Entanglement renormalization
- Thermodynamic limit of the density matrix renormalization for the spin-1 Heisenberg chain
- An Area Law for One Dimensional Quantum Systems
- A Mott insulator of fermionic atoms in an optical lattice
- Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
- A Theory of Quantum Error-Correcting Codes
- A class of quantum many-body states that can be efficiently simulated
- Symmetry protection of topological order in one-dimensional quantum spin systems
- Continuous variable quantum information: Gaussian states and beyond
- Matrix product states represent ground states faithfully
- Metallic and Insulating Phases of Repulsively Interacting Fermions in a 3D Optical Lattice
- Area laws in quantum systems: mutual information and correlations
- Lieb-Schultz-Mattis in Higher Dimensions
- Dynamics of quantum phase transition: exact solution in quantum Ising model
- Quantum mechanical evolution towards thermal equilibrium
- DMRG and periodic boundary conditions: a quantum information perspective
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Violation of the entropic area law for Fermions
- A class of ansatz wave functions for 1D spin systems and their relation to DMRG
- Entropy scaling and simulability by Matrix Product States
- The computational complexity of PEPS
- Entanglement in XY Spin Chain
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Solving Gapped Hamiltonians Locally
- The power of quantum systems on a line
- N-representability is QMA-complete
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Hamiltonian complexity
- Exponential Decay of Correlations Implies Area Law
- Approximating Gibbs states of local Hamiltonians efficiently with PEPS
- Variational matrix product state approach to quantum impurity models
- Entanglement in a Valence-Bond-Solid State
- An area law for the entropy of low-energy states
- Criticality without frustration for quantum spin-1 chains
- Projected entangled-pair states can describe chiral topological states
- Entanglement rates and area laws
- Stochastic Error Cancellation in Analog Quantum Simulation
- An improved 1D area law for frustration-free systems
- A new construction for a QMA complete 3-local Hamiltonian
- The computational difficulty of finding MPS ground states
- Interacting boson problems are QMA-hard
- Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
- Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
- QMA-complete problems for stoquastic Hamiltonians and Markov matrices
- Merlin-Arthur Games and Stoquastic Complexity
- Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
- The Quantum PCP Conjecture
- Local tests of global entanglement and a counterexample to the generalized area law
- Entanglement area law from specific heat capacity
- Hardness of approximation for quantum problems
- The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
- Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
- Ground state connectivity of local Hamiltonians
- An Efficient Algorithm for approximating 1D Ground States
- Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
- A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
- Local Hamiltonians in Quantum Computation
- On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
- 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 (81)
- 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
- Universal eigenstate entanglement of chaotic local Hamiltonians
- Neural network representation of tensor network and chiral states
- 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
- Testing Holographic Conjectures of Complexity with Born-Infeld Black Holes
- Infrared-dressed entanglement of cold open-shell polar molecules for universal matchgate quantum computing
- 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
- Correlation Length versus Gap in Frustration-Free Systems
- The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
- Approximation algorithms for quantum many-body problems
- Action Growth in Gravity
- Quantum Max-flow/Min-cut
- 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
- Evolutions of entanglement and complexity after a thermal quench in massive gravity theory
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- Ground state connectivity of local Hamiltonians
- 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
- On connectivity-dependent resource requirements for digital quantum simulation of -level particles
- Double-bracket quantum algorithms for quantum imaginary-time evolution
- Quantum advantage from energy measurements of many-body quantum systems
- Two-dimensional local Hamiltonian problem with area laws is QMA-complete
- Complexity growth of BTZ black hole in massive gravity with a null string
- Entanglement Dynamics From Random Product States: Deviation From Maximal Entanglement
- Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
- On efficiently solvable cases of Quantum k-SAT
- A comparison of three ways to measure time-dependent densities with quantum simulators
- Quantum fluctuation on the worldsheet of probe string in BTZ black hole
- A multiprover interactive proof system for the local Hamiltonian problem
- Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
- Extracting the spin excitation spectrum of a fermionic system using a quantum processor
- Deviation from maximal entanglement for mid-spectrum eigenstates of local Hamiltonians
- Measurement-Induced Phase Transition in a Disordered XX Spin Chain: A Real-Space Renormalization Group Study
- Predictive complexity of quantum subsystems
- Pinned QMA: The power of fixing a few qubits in proofs
- On the characterization of partially entanglement breaking and annihilating channels
- Optimizing Sparse SYK
- Energy gap of quantum spin glasses: a projection quantum Monte Carlo study
- Quantum entropy thermalization