Hamiltonian complexity

2011/06/29 by Tobias J. Osborne, Tobias J Osborne · 167 citations
Computer Science · Physics and Astronomy · #Classical mechanics #Covariant Hamiltonian field theory #Hamiltonian (control theory) #Hamiltonian system #Parallel Computing and Optimization Techniques #Physics #Quantum Computing Algorithms and Architecture #Quantum many-body systems #Statistical physics #Theoretical physics #cond-mat.str-el #quant-ph

paper · pdf · doi:10.1088/0034-4885/75/2/022001

published in Reports on Progress in Physics 75(2), 022001 (IOP Publishing) · 14 pages

arxiv created 2011/06/29 · openalex publication_date 2012/01/24 · arxiv updated 2015/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

In recent years we have 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.

Citations

• Colloquium: Area laws for the entanglement entropy
• The density-matrix renormalization group in the age of matrix product states

Cited by

• The Philosophy and Physics of Duality
• An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
• Spread and circuit complexity as a measure of particle content and phase space fluctuations
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Efficient simulation of many-body localized systems
• Approximation, Proof Systems, and Correlations in a Quantum World
• On the complexity of estimating ground state entanglement and free energy
• Free Snacks in Quantum Complexity
• On physical problems that are slightly more difficult than QMA
• A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
• The commuting local Hamiltonian on locally-expanding graphs is in NP
• Analogue Quantum Simulation: A Philosophical Prospectus
• Meson spectroscopy of exotic symmetries of Ising criticality in Rydberg atom arrays
• Noncontextual Pauli Hamiltonians
• An Efficient Algorithmic Way to Construct Boltzmann Machine Representations for Arbitrary Stabilizer Code
• Computing energy density in one dimension
• Complexity transitions in chaotic quantum systems: Nonstabilizerness, entanglement, and fractal dimension in SYK and random matrix models
• Time dependent Interface in AdS Black Hole Spacetime
• Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
• A multiprover interactive proof system for the local Hamiltonian problem
• Computational complexity in electronic structure
• Exponential Decay of Correlations Implies Area Law
• Quantum East Model: Localization, Nonthermal Eigenstates, and Slow Dynamics
• Quantum 3-SAT Is QMA1-Complete
• Quantum Entanglement in Neural Network States

Related

• Simulating Arbitrary Pair-Interactions by a Given Hamiltonian: Graph-Theoretical Bounds on the Time Complexity
• New Concept of Dynamic Complexity in Quantum Mechanics and Beyond
• Classification on the Computational Complexity of Spin Models
• Limits on Efficient Computation in the Physical World
• Quantum complexity in gravity, quantum field theory, and quantum information science