Hamiltonian complexity
arXiv:1106.5875 · doi:10.1088/0034-4885/75/2/022001
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.
arXiv comment14 pages
References in corpus (56)
- The density-matrix renormalization group in the age of matrix product states
- Area laws for the entanglement entropy - a review
- Efficient simulation of one-dimensional quantum many-body systems
- Entanglement renormalization
- An Area Law for One Dimensional Quantum Systems
- A class of quantum many-body states that can be efficiently simulated
- Lieb-Schultz-Mattis in Higher Dimensions
- Lieb-Robinson bounds and the generation of correlations and topological quantum order
- Spectral Gap and Exponential Decay of Correlations
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Lieb-Robinson Bounds and the Exponential Clustering Theorem
- Quasi-adiabatic Continuation of Quantum States: The Stability of Topological Ground State Degeneracy and Emergent Gauge Invariance
- Topological quantum order: stability under local perturbations
- Continuous Matrix Product States for Quantum Fields
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- 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
- A short proof of stability of topological order under local perturbations
- Locality in Quantum and Markov Dynamics on Lattices and Networks
- The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
- Bounds on Information Propagation in Disordered Quantum Spin Chains
- Lieb-Robinson Bound and Locality for General Markovian Quantum Dynamics
- Lieb-Robinson Bounds for Harmonic and Anharmonic Lattice Systems
- An area law for the entropy of low-energy states
- Simulating adiabatic evolution of gapped spin systems
- Holographic quantum states
- A Multi-Dimensional Lieb-Schultz-Mattis Theorem
- A new construction for a QMA complete 3-local Hamiltonian
- Interacting boson problems are QMA-hard
- Light Cone Matrix Product
- On the Existence of the Dynamics for Anharmonic Quantum Oscillator Systems
- QMA-complete problems for stoquastic Hamiltonians and Markov matrices
- Lieb-Robinson bounds for commutator-bounded operators
- On product, generic and random generic quantum satisfiability
- Unfrustrated Qudit Chains and their Ground States
- Quantum Dynamics with Mean Field Interactions: a New Approach
- Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
- 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
- An Efficient Algorithm for approximating 1D Ground States
- A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
- Lieb-Robinson bounds with dependence on interaction strengths
- On the propagation of a perturbation in an anharmonic system
- Lieb-Robinson bounds for classical anharmonic lattice systems
- Approximating the ground state of gapped quantum spin systems
- Efficient algorithm for a quantum analogue of 2-SAT
- Quantization of Hall Conductance For Interacting Electrons Without Averaging Assumptions
- Quantum Hamiltonian complexity and the detectability lemma
- 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 (95)
- 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
- Complexity of the AdS Soliton
- Surface Counterterms and Regularized Holographic Complexity
- 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
- 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
- Out-of-time-order correlators and quantum phase transitions in the Rabi and Dicke model
- Action Growth in Gravity
- Complexity growth of rotating black holes with a probe string
- Holographic complexity: A tool to probe the property of reduced fidelity susceptibility
- Hamiltonian simulation with nearly optimal dependence on spectral norm
- Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
- Evolutions of entanglement and complexity after a thermal quench in massive gravity theory
- Ground state connectivity of local Hamiltonians
- Exponential clustering of bipartite quantum entanglement at arbitrary temperatures
- Certified algorithms for equilibrium states of local quantum Hamiltonians
- Holographic fluctuations and the principle of minimal complexity
- Computing energy density in one dimension
- A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
- Entanglement dynamics in critical random quantum Ising chain with perturbations
- Quantum 3-SAT is QMA1-complete
- The complexity of simulating local measurements on quantum systems
- Connecting probability distributions of different operators and generalization of the Chernoff-Hoeffding inequality
- Holographic complexity in general quadratic curvature theory of gravity
- Approximating local properties by tensor network states with constant bond dimension
- Informational Approach to Identical Particles in Quantum Theory
- Complexity growth of massive black hole with a probe string
- Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
- An Efficient Algorithmic Way to Construct Boltzmann Machine Representations for Arbitrary Stabilizer Code
- The Complexity of Translationally Invariant Problems beyond Ground State Energies
- On the NP-completeness of the Hartree-Fock method for translationally invariant systems
- An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
- Double-bracket quantum algorithms for quantum imaginary-time evolution
- The computational complexity of density functional theory
- The commuting local Hamiltonian on locally-expanding graphs is in NP
- Complexity growth for topological black holes by holographic method
- Two-dimensional local Hamiltonian problem with area laws is QMA-complete
- Effects of the acceleration on holographic complexity
- Properties of Krylov state complexity in qubit dynamics
- Entanglement Dynamics From Random Product States: Deviation From Maximal Entanglement
- Complexity growth of BTZ black hole in massive gravity with a null string
- Physical consequences of PNP and the DMRG-annealing conjecture
- On efficiently solvable cases of Quantum k-SAT
- Oracle complexity classes and local measurements on physical Hamiltonians
- Efficient simulation of many-body localized systems
- Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
- Analogue Quantum Simulation: A Philosophical Prospectus
- Approximation, Proof Systems, and Correlations in a Quantum World
- Quantum fluctuation on the worldsheet of probe string in BTZ black hole
- A multiprover interactive proof system for the local Hamiltonian problem
- Pinned QMA: The power of fixing a few qubits in proofs
- QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
- Representing arbitrary ground states of toric code by a restricted Boltzmann machine
- Deviation from maximal entanglement for mid-spectrum eigenstates of local Hamiltonians
- On physical problems that are slightly more difficult than QMA
- Predictive complexity of quantum subsystems
- On polynomially many queries to NP or QMA oracles
- Quantum entropy thermalization
- Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
- Noncontextual Pauli Hamiltonians
- Time dependent Interface in AdS Black Hole Spacetime
- Quantum Walks on Necklaces and Mixing