Hamiltonian complexity

Abstract

In recent years we've seen the birth of a new field known as hamiltonian complexity lying at the crossroads between computer science and theoretical physics. Hamiltonian complexity is directly concerned with the question: how hard is it to simulate a physical system? Here I review the foundational results, guiding problems, and future directions of this emergent field.

14 pages

References in corpus (26)

• The density-matrix renormalization group in the age of matrix product states
• A class of quantum many-body states that can be efficiently simulated
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Lieb-Robinson Bounds and the Exponential Clustering Theorem
• Continuous Matrix Product States for Quantum Fields
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Propagation of Correlations in Quantum Lattice Systems
• The power of quantum systems on a line
• N-representability is QMA-complete
• General entanglement scaling laws from time evolution
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Lieb-Robinson Bounds for Harmonic and Anharmonic Lattice Systems
• Holographic quantum states
• A Multi-Dimensional Lieb-Schultz-Mattis Theorem
• A new construction for a QMA complete 3-local Hamiltonian
• Quantum Dynamics with Mean Field Interactions: a New Approach
• Computational Difficulty of Computing the Density of States
• Quasi-adiabatic Continuation for Disordered Systems: Applications to Correlations, Lieb-Schultz-Mattis, and Hall Conductance
• Observations Outside the Light-Cone: Algorithms for Non-Equilibrium and Thermal States
• Approximating the ground state of gapped quantum spin systems
• Efficient algorithm for a quantum analogue of 2-SAT
• Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• Dynamics and Lieb-Robinson estimates for lattices of interacting anharmonic oscillators
• Statistical mechanics of classical and quantum computational complexity

Cited by in corpus (94)

• Quantum Chemistry in the Age of Quantum Computing
• Quantum information processing with superconducting circuits: a review
• Complexity Equals Action
• Complexity, action, and black holes
• Circuit complexity in quantum field theory
• Quantum Entanglement in Neural Network States
• Comments on Holographic Complexity
• Liouville Action as Path-Integral Complexity: From Continuous Tensor Networks to AdS/CFT
• Complexity of Formation in Holography
• Complexity Growth for AdS Black Holes
• Circuit complexity for free fermions
• Circuit complexity in interacting QFTs and RG flows
• Exponential Decay of Correlations Implies Area Law
• Quantum Hamiltonian Complexity
• An area law for entanglement from exponential decay of correlations
• Time Evolution of Complexity: A Critique of Three Methods
• Strictly linear light cones in long-range interacting systems of arbitrary dimensions
• Divergences in Holographic Complexity
• Quantum Neural Network States: A Brief Review of Methods and Applications
• Quantum East model: localization, non-thermal eigenstates and slow dynamics
• Tensor network techniques for the computation of dynamical observables in 1D quantum spin systems
• A Complexity for Quantum Field Theory States and Application in Thermofield Double States
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Complexity in de Sitter Space
• Holographic subregion complexity under a thermal quench
• Universal eigenstate entanglement of chaotic local Hamiltonians
• Computational Complexity in Electronic Structure
• Scaling of variational quantum circuit depth for condensed matter systems
• Eigenstate entanglement in the Sachdev-Ye-Kitaev model
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Surface Counterterms and Regularized Holographic Complexity
• Complexity of the AdS Soliton
• Testing Holographic Conjectures of Complexity with Born-Infeld Black Holes
• Introduction to Quantum Algorithms for Physics and Chemistry
• Complexity of Holographic Superconductors
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Equilibration towards generalized Gibbs ensembles in non-interacting theories
• Spread and Spectral Complexity in Quantum Spin Chains: from Integrability to Chaos
• Correlation Length versus Gap in Frustration-Free Systems
• Out-of-time-order correlators and quantum phase transitions in the Rabi and Dicke model
• Action Growth in $f\left(R\right)$ Gravity
• Complexity growth of rotating black holes with a probe string
• Holographic complexity: A tool to probe the property of reduced fidelity susceptibility
• Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• 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
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Computing energy density in one dimension
• Holographic fluctuations and the principle of minimal complexity
• A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
• Entanglement dynamics in critical random quantum Ising chain with perturbations
• The complexity of simulating local measurements on quantum systems
• Quantum 3-SAT is QMA1-complete
• Connecting probability distributions of different operators and generalization of the Chernoff-Hoeffding inequality
• Approximating local properties by tensor network states with constant bond dimension
• Holographic complexity in general quadratic curvature theory of gravity
• An Efficient Algorithmic Way to Construct Boltzmann Machine Representations for Arbitrary Stabilizer Code
• 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
• Informational Approach to Identical Particles in Quantum Theory
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• On the NP-completeness of the Hartree-Fock method for translationally invariant systems
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• The computational complexity of density functional theory
• Complexity growth for topological black holes by holographic method
• The commuting local Hamiltonian on locally-expanding graphs is in NP
• Complexity growth of BTZ black hole in massive gravity with a null string
• Entanglement Dynamics From Random Product States: Deviation From Maximal Entanglement
• Properties of Krylov state complexity in qubit dynamics
• Effects of the acceleration on holographic complexity
• On efficiently solvable cases of Quantum k-SAT
• Efficient simulation of many-body localized systems
• Oracle complexity classes and local measurements on physical Hamiltonians
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Approximation, Proof Systems, and Correlations in a Quantum World
• Analogue Quantum Simulation: A Philosophical Prospectus
• A multiprover interactive proof system for the local Hamiltonian problem
• Quantum fluctuation on the worldsheet of probe string in BTZ black hole
• On physical problems that are slightly more difficult than QMA
• Deviation from maximal entanglement for mid-spectrum eigenstates of local Hamiltonians
• Representing arbitrary ground states of toric code by a restricted Boltzmann machine
• Predictive complexity of quantum subsystems
• Pinned QMA: The power of fixing a few qubits in proofs
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
• On polynomially many queries to NP or QMA oracles
• Time dependent Interface in AdS Black Hole Spacetime
• Quantum entropy thermalization
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• Noncontextual Pauli Hamiltonians
• Quantum Walks on Necklaces and Mixing