Source-linked AI summary
Hamiltonian complexity
Tobias J. Osborne
TL;DR
Hamiltonian complexity asks how hard it is to simulate physical systems and formalizes that question through computational problems over Hamiltonian families and observables. The review synthesizes foundational hardness and easiness results, including QMA-complete one-dimensional ground-state approximation and efficient simulation regimes, while identifying unresolved scope boundaries and future directions.
Problem
Hamiltonian complexity addresses the computational difficulty of simulating physical systems, especially families whose observable properties may be hard to estimate.
Method
The review organizes simulation complexity around Hamiltonian families, states, observables, time parameters, precision, and techniques including locality bounds and variational representations.
Results
The field includes QMA-complete ground-state-energy approximation for one-dimensional quantum lattice systems, while imaginary-time simulation is in NP for gapped one-dimensional systems and real-time simulation is in P for |t| ∼ log(n).
Takeaways & Limitations
Hamiltonian complexity provides foundational results spanning both physically realistic systems that are hard to simulate and regimes that admit efficient simulation.
Takeaways & Limitations
Open boundaries include whether commuting-interaction systems are harder than NP, whether low-dimensional one-dimensional chains are easier, and the nonconstructive nature of some efficient representations.
Abstract
from arXiv · showhide
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.
1. Introduction
Hamiltonian complexity applies computational complexity theory to many-body physics to ask how hard it is to simulate physical systems. The field is motivated by systems whose physical properties may be fundamentally difficult to calculate, while quantum simulation introduces both new capabilities and new complexity barriers.
- 1. Introduction: Many-body systems involve large numbers of interacting particles governed by simple physical laws, producing equations with many variables.
- 1. Introduction: Equilibrium states of some physical systems correspond directly to satisfying assignments of propositional formulae, making computational-complexity methods relevant to physics.
- 1. Introduction: Hamiltonian complexity asks how hard it is to simulate a physical system using computational complexity theory and many-body physics.Computational complexity quantifies difficulty, while condensed matter physics supplies strongly correlated systems to study.
- 1. Introduction: Barahona’s Ising model shows that an engineered physical system can have a ground-state energy whose calculation requires computational resources growing too quickly with system size.
- 1. Introduction: Quantum computers can simulate certain real-time many-body dynamics, but quantum simulation algorithms cannot always efficiently simulate equilibrium properties.
- 1. Introduction: Metastable configurations explain why equilibrium properties can be difficult to simulate: systems with many such configurations may end in a metastable state rather than the unique lowest-energy state.
2. Complexity theory
Complexity theory classifies computational problems by how the required number of basic steps scales with input size, distinguishing efficiently solvable problems from problems whose solutions are only efficiently verifiable. Hamiltonian examples connect these classes to physical energy minimization and show that quantum verification yields a broader hardness landscape.
- 2. Complexity theory: Complexity classes organize problems by the scaling of computational steps needed as input size grows.P contains decision problems solvable with polynomially many steps, although a high polynomial exponent can still be impractical.
- 2. Complexity theory: NP contains problems whose proposed solutions can be checked in polynomially many steps, including energy-minimization decision problems with efficiently computable energy functions.
- 2. Complexity theory: Exhaustive search over n-bit configurations takes O(2^n) steps, and frustrated interactions can create many local minima that obstruct better general strategies.
- 2. Complexity theory: 3SAT maps to a classical spin Hamiltonian whose minimum corresponds to a satisfying assignment, linking NP-complete logic problems to physical energy minimization.
- 2. Complexity theory: A ferromagnetic Ising model with arbitrary interaction graph admits a polynomial-time Gibbs sampler despite initially appearing intractable.
- 2. Complexity theory: Quantum complexity extends classical classes with BQP and QMA, where quantum computation and quantum proofs support verification problems beyond the classical NP framework.Kitaev’s result provides a QMA-complete problem and establishes that QMA contains harder problems than NP.
3. The simulation problem
The simulation problem formalizes physical simulation as deciding between two expectation values for a family of Hamiltonians, states, observables, times, and system sizes. Its difficulty depends on the observable, evolution regime, precision, and temperature, with important cases ranging from hard ground-state estimation to potentially easier approximations.
- 3. The simulation problem: The simulation problem specifies a Hamiltonian family, initial state, observable family, possibly complex time, two expectation values, and system size.
- 3. The simulation problem: Computational hardness is measured by how the number of arithmetic operations scales with the number of particles in the Hamiltonian family.
- 3. The simulation problem: Simulation must identify the system’s state, such as thermal equilibrium or dynamical evolution, because different regimes define different computational problems.
- 3. The simulation problem: Real-time and ground-state simulation are prominent special cases, with the latter obtained through an imaginary-time limit and a thermal-state expression.
- 3. The simulation problem: For general observables, simulation complexity can vary with required precision: estimating magnetisation is as hard as the ground-state problem at small error, while certain regular lattices admit efficient approximation at error ϵ ∼ n.
- 3. The simulation problem: Finite-temperature and decoherent dynamics are less explored, and the review anticipates a hardness transition from low to high temperature or decoherence rates.
4. What is hard
Hamiltonian complexity shows that ground-state and related simulation problems can be computationally hard across classical, quantum, bosonic, fermionic, and constrained systems. Its central open frontier is whether quantum hardness persists when approximation gaps become constant rather than inverse-polynomial.
- Foundational quantum hardness: QMA-completeness of 5-local Hamiltonian ground-state simulation implies efficient classical simulation would make all QMA problems, including quantum computation, classically simulable.Kitaev’s construction uses a 5-local Hamiltonian with promise gap O(n^-3).
- Foundational quantum hardness: One-dimensional quantum spin systems can have ground-state energies hard to simulate to precision O(n^-α), even under translation invariance, unlike the classical one-dimensional case.The result holds for α ≥ 3 and rules out a direct quantum analogue of the classical transfer-operator method.
- Physically motivated settings: Ground-state simulation remains hard in physically motivated particle settings: stoquastic Hamiltonians are stoquastic-MA-complete, while fermionic and bosonic cases are QMA-hard.Stoquastic systems avoid the sign problem because their ground-state coefficients are nonnegative.
- Related problems: Related consistency problems are also hard: density-operator consistency is QMA-hard, as is the fermionic N-representability problem important in quantum chemistry.
- Quantum satisfiability: Quantum k-SAT asks whether a positive semidefinite Hamiltonian is frustration-free, and random quantum k-SAT exhibits a transition between abundant and scarce frustration-free ground states.
- Open problems: Commuting-interaction systems may be harder than classical systems because their common eigenbasis can be highly entangled, leaving their complexity classification open.
- Guiding problem: the quantum PCP conjecture: The quantum PCP conjecture asks whether QMA-complete simulation remains hard at constant precision, but a full theorem has resisted proof despite progress via the detectability lemma.Existing quantum constructions establish hardness only for inverse-polynomial promise gaps, motivating the constant-gap question.
5. What is easy
The section explains how locality and information-propagation bounds make some quantum simulation problems tractable, while efficient representations and practical heuristics remain limited by dimensionality, optimization landscapes, and rigorous gaps.
- 5. What is easy: Locality bounds information propagation, enabling compact state descriptions and efficient real-time simulation in one dimension for |t| ≲ log(N).The Lieb-Robinson bound yields an effectively local description, and matrix product states support a polynomial-complexity algorithm in the stated time regime.
- 5. What is easy: A spectral gap allows one-dimensional ground states to be efficiently approximated by matrix product states, although the existence proof is nonconstructive.The associated variational optimization is difficult because the objective is nonlinear and has many local minima.
- 5. What is easy: DMRG offers a practical heuristic for varying over matrix product states, despite local minima, but its empirical success does not make it a general polynomial-time method.A polynomial algorithm exists for a fixed number of variational parameters, yet its performance is not comparable with DMRG.
- 5. What is easy: Lieb-Robinson methods and quasi-adiabatic continuation also establish results on topological-order stability and Hall-conductance quantization.These techniques extend beyond translation-invariant systems to disordered and other settings.
- 5. What is easy: Rigorous entropy-area-law results remain concentrated in gapped one-dimensional and Gaussian systems, with gapped two-dimensional systems still unresolved.Topological order is identified as one difficulty for existing proof techniques.
6. Conclusion
The conclusion highlights foundational complexity classifications alongside efficient simulation results, then identifies open problems in hard-to-simulate systems and future extensions to continuous quantum systems.
- 6. Conclusion: Hamiltonian complexity established both hardness and tractability results, including QMA-completeness for one-dimensional ground-state energies and efficient simulation in restricted settings.The review highlights NP membership for imaginary-time simulation of gapped one-dimensional systems and P membership for real-time simulation at |t| ∼ log(n).
- 6. Conclusion: Finding quantum lattice systems that are hard to simulate has reached a natural pause, while commuting Hamiltonians and inefficient quantum PCPs remain open problems.Progress on these problems could open new research directions.
- 6. Conclusion: Efficient algorithms for low-dimensional quantum lattice simulation continue to develop, with quantum approximation algorithms identified as particularly promising.
- 6. Conclusion: Hamiltonian-complexity insights are being generalized to continuous-degree-of-freedom systems, including quantum fields, through continuous versions of MPS and MERA.The review suggests that further lattice-to-continuum results may follow.
- 6. Conclusion: The review acknowledges contributors who read preliminary drafts and provided comments and suggestions.