Quantum Hamiltonian Complexity

Sevag Gharibian; Yichen Huang; Zeph Landau; Seung Woo Shin

Source-linked AI summary

Quantum Hamiltonian Complexity

Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin

arXiv:1401.3916v4Jan 16, 2014quant-phcond-mat.str-elcs.CC

TL;DR

Quantum Hamiltonian Complexity asks how to understand and compute properties of local quantum constraint systems while bridging computer-science and physics perspectives. This survey builds that bridge through accessible background, physics concepts, and selected complexity results, including foundational hardness and algorithmic developments. It also notes scope boundaries in the treatment of quantum-state interpretation and helium-4.

Problem
Quantum Hamiltonian Complexity studies local quantum constraint systems and their ground states, whose physical relevance is paired with computational difficulty and whose concepts span computer science and physics.
Method
The survey combines computer-science-oriented introductions to quantum information and QHC with physics glossaries, conceptual overviews, and expositions of selected results.
Results
The survey presents a quantum Cook-Levin theorem, selected QHC complexity results, and area-law insights, including that unsatisfiable encoded instances have energy at least 1.
Takeaways & Limitations
The survey provides a roadmap connecting local Hamiltonian models, quantum constraint satisfaction, physical ground states, and computational complexity.
Takeaways & Limitations
The survey states that helium-4’s precise ground state remains elusive and that density-operator interpretation remains highly non-trivial and debated.

Abstract

from arXiv · show

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.

Introduction

Quantum Hamiltonian Complexity studies local quantum constraint systems by encoding quantum evolution into local Hamiltonian constraints. Its central object is a succinctly represented Hamiltonian whose local terms restrict subsets of qudits.

QHC extends the locality underlying Cook-Levin from classical constraints to quantum evolution and quantum constraint systems.
A local Hamiltonian H governs quantum-state evolution through the Schrödinger equation and is represented as a sum of local Hermitian terms.
Each local term acts non-trivially on at most k qudits and functions as a quantum clause restricting their joint state to a subspace.
For a k-local Hamiltonian, the local-clause description has size polynomial in the number of qudits.

162 Introduction

QHC studies computational properties of local Hamiltonians whose matrices are exponentially large in the number of qudits. The survey motivates this challenge through ground-state questions in complexity theory and physics, then organizes accessible background and selected results.

The description of a local Hamiltonian is polynomial in n, even though H is a matrix of dimension d^n × d^n.
QHC commonly asks for a Hamiltonian’s ground-state energy or properties of its ground state, viewed as the state that best satisfies its constraints.
Helium-4 illustrates the physics motivation: its near-zero-temperature ground state exhibits superfluidity, while its precise ground state remains elusive.
The field includes a quantum Cook-Levin theorem, a polynomial-time Quantum 2-SAT algorithm, and area-law insights explaining effective one-dimensional methods.
The survey introduces quantum information and QHC definitions, sketches encoding 3-CSP into a local Hamiltonian, and provides a roadmap for later chapters.

Preliminaries

The preliminaries introduce quantum information and the formal language needed for QHC, including states, measurements, operators, and Hamiltonian constraint encodings. They also connect unsatisfiable classical constraints to positive Hamiltonian energy.

The survey begins with quantum-information basics and fundamental QHC definitions to make later material accessible to computer scientists.
Quantum mechanics is described using linear-algebraic objects such as complex, unitary, Hermitian, and positive semidefinite operators.
A pure quantum state is a unit vector, while a mixed state is represented by a density matrix that is positive semidefinite with trace one.
The survey cautions that the precise interpretation of density operators is highly non-trivial and remains debated.
Quantum measurements use operators satisfying a completeness relation, produce probabilistic outcomes, and update the state after an outcome is observed.
For an unsatisfiable encoded constraint system, every binary assignment has energy at least 1, and the corresponding local-Hamiltonian problem is QMA-complete for 5-local and 2-local cases.

Roadmap and Organization

The survey bridges computer science and physics perspectives on quantum Hamiltonian complexity. It introduces motivations and condensed-matter concepts before reviewing selected computer-science-inspired results.

The survey begins with a history of quantum Hamiltonian complexity from both computer science and physics perspectives.
Its first half explains why quantum Hamiltonians matter, including time evolution, thermal equilibrium, their origins, and indistinguishable particles.
Chapter 6 presents a glossary and develops mean field theory, tensor networks, Density Matrix Renormalization Group, Multi-Scale Entanglement Renormalization Ansatz, and area laws.
Chapter 7 reviews QMA-completeness results, commuting Hamiltonians, Quantum 2-SAT, and a one-dimensional area-law proof.

A Brief History

Quantum Hamiltonian complexity grew from intertwined physics and computer-science origins. Its milestones include quantum analogues of classical complexity results, tractable special cases, hardness classifications, and area-law theorems.

The field’s history has roots in both physics and computer science, with the survey presenting both perspectives.
1999: Kitaev’s quantum Cook-Levin analogue placed k-LH in QMA and proved QMA-hardness for k ≥ 5.
2-QSAT is in P, while later work classified broad 2-LH constraint families into P, NP-complete, TIM-complete, or QMA-complete.
Commuting local Hamiltonians admit several NP or P results, including commuting 2-LH in NP and Pauli-product cases in P.
Quantum Hamiltonian complexity also includes QMA-hardness for bosonic and fermionic systems, physically motivated models, and approximation questions.
Open directions include a quantum analogue of the PCP theorem and whether a two-dimensional area law holds.
Linear-time classical algorithms for quantum 2-SAT improved Bravyi’s earlier quartic-time algorithm.

Motivations From Physics

Physics motivates quantum Hamiltonian complexity through local properties of lattice systems, their dynamics and equilibrium states, and the challenge of obtaining useful tractable models and simulations.

Condensed-matter physics often studies local properties of particles arranged on a d-dimensional lattice with nearest-neighbor interactions.
These properties are examined through time evolution of isolated systems or thermal equilibrium after interaction with an environment.
The Gibbs-state description is useful in practice but is not provably an exact description of equilibrium for every system.
Hamiltonian models are phenomenological simplifications that may capture selected local properties while ignoring other degrees of freedom.
Gaussian states permit local predictions in polynomial time, while tensor-network approximations use controlled bond dimensions for relevant states.
Quantum simulations of the Hubbard model combine the model with quantum devices to investigate strongly correlated materials.
Experiments with ultracold atoms have obtained a good simulation of the 3D Hubbard model and evidence of a similar metal-insulator phase transition.

Physics Concepts in Greater Depth

The survey’s deeper physics treatment supplies a glossary of models and concepts connecting local Hamiltonians to many-body systems, spin models, correlations, and exactly or approximately representable ground states.

The chapter expands the survey with a physics glossary and reviews models including Ising, Heisenberg, AKLT, and quantum Ising systems.
An interaction graph records which particles are jointly acted on by local Hamiltonian terms, paralleling constraint relationships in CSPs.
The classical Ising model assigns binary variables to lattice sites, and a special ground-state formulation is equivalent to MAX CUT.
Quantum Ising and Heisenberg models introduce Pauli operators, coupling constants, magnetic fields, and related special cases such as XX and XXZ.
For spin-1/2 antiferromagnetic Heisenberg systems, the singlet spans the one-dimensional antisymmetric ground subspace of the two-local constraint.
The AKLT ground state is constructed from paired qubits, singlets between neighboring sites, and projections onto symmetric subspaces.
The AKLT model is gapped, has boundary-dependent ground-state degeneracy, exponentially decaying correlations, and an exact bond-dimension-2 MPS representation.

6.2 Mean-field theory

Mean-field theory approximates an interacting many-body Hamiltonian by a decoupled, exactly solvable Hamiltonian, using physical intuition to model collective behavior. It is widely used despite lacking an a priori accuracy guarantee.

Mean-field theory replaces the interacting system with a self-consistent effective description whose quality depends on the physical system being studied.The method has nevertheless succeeded in several physically important contexts.
Mean-field theory constructs a decoupled and exactly solvable Hamiltonian Hmf to circumvent coupling between particles.The approximation requires physical intuition, and its accuracy is not guaranteed beforehand.
The section illustrates the method using the classical Ising model on a D-dimensional hypercubic lattice at thermal equilibrium.Temperature T is the tuning parameter, and the target property is the model’s critical temperature.

6.2. Mean-field theory

The Ising example uses an infinitesimal symmetry-breaking field and a self-consistent mean-field equation to predict spontaneous magnetization and estimate the critical temperature. The resulting estimate is reasonably accurate in two dimensions, while more sophisticated methods can perform better in lower dimensions.

Symmetry breaking and phase transition: An infinitesimal positive magnetic field selects the all-spin-up state at T = 0 and yields zero magnetization at T = +∞.This establishes spontaneous magnetization at zero temperature and a critical temperature Tc between the two limits.
Known results: For D = 1, the exact critical temperature is Tc = 0, while for D = 2, Onsager’s result is Tc = 2J/ln(1 + 2) ≈ 2.27J.No exact solution is known for D ≥3.
Mean-field construction: The mean-field self-consistency condition is m = tanh(2βDJm), where m represents the uniform magnetization.The decoupled Hamiltonian is formed by approximating each spin with its expectation value.
Mean-field prediction: Mean-field theory predicts spontaneous magnetization when 2βDJ > 1, giving Tc = 2DJ and a reasonably good approximation to Onsager’s D = 2 result.The equation has only m = 0 when 2βDJ ≤1, but also solutions ±m0 when 2βDJ > 1.
Scope and variational view: Renormalization-group analysis outperforms mean-field theory for D ≤3, whereas the two methods agree on critical exponents for D ≥4.The mean-field equation can also be obtained by minimizing the mean-field free energy over a family of variational Hamiltonians.
Quantum extension: For quantum phase transitions at zero temperature, mean-field theory minimizes the ground-state energy of variational Hamiltonians whose ground states are product states.This contrasts with the finite-temperature setting, where mean-field theory minimizes free energy.

6.3 Tensor networks

Tensor networks provide succinct representations of selected entangled quantum states by connecting multidimensional arrays through shared indices. Their contraction operations, linear-map interpretation, and correspondence with quantum-state amplitudes support efficient computation in suitable network structures.

Tensor networks encode certain entangled quantum states succinctly, including Matrix Product States and related constructions.They address the fact that arbitrary n-qubit states may require exponentially many classical bits to represent.
A tensor is a multidimensional array, and its graphical representation uses vertices for tensors and edges for their input indices.A k-dimensional tensor maps index tuples to complex numbers.
Contracting two tensors over shared inputs produces a new tensor with the uncontracted inputs as its remaining legs.For M and N contracted on i2 and j2, the result is a four-dimensional tensor P.
Tensor networks can represent n-qubit states by storing their 2^n amplitudes as entries of an n-tensor, with the qudit generalization using local dimension d.The parameter d is called the bond dimension in the generalized correspondence.
Figure 6.2 presents five tensor networks as exercises involving their constituent tensors, input parameters, outputs, and contractions.One exercise asks how a network of 2m tensors with constant bond dimension can be contracted in polynomial time.
Viewing tensors as linear maps allows a network of constant bond dimension to compute an inner product in time polynomial in m.In the demonstrated network, intermediate tensors act as maps from (C^d)^⊗2 to (C^d)^⊗2, and the final contraction outputs a scalar.

6.4. Density Matrix Renormalization Group

Matrix Product States represent quantum amplitudes as products of local matrices and are effective when entanglement across cuts is limited. DMRG optimizes an MPS approximation to a ground state through repeated local updates, while related tensor-network schemes extend the representation to broader settings.

Matrix Product States: An MPS represents each computational-basis amplitude as a product of local matrices, with physical indices of dimension d and bond dimension D.Boundary matrices are vectors, while interior matrices have dimension D×D.
Matrix Product States: Any n-particle state has an exact MPS representation if D is at least its maximum Schmidt rank, but that D can grow exponentially with n.MPS are computationally useful when entanglement across bipartite cuts has polynomial Schmidt rank.
Matrix Product States: In 1D gapped systems, an area law bounds entanglement entropy across every cut by a constant independent of n, supporting efficient MPS approximations.Critical gapless systems introduce a logarithmic ∼log n violation, and MPS descriptions permit efficient computation of several physical properties.
Density Matrix Renormalization Group: DMRG minimizes ⟨ψ|H|ψ⟩ over MPS of fixed bond dimension D to approximate the ground state.The optimization involves O(ndD^2) parameters, and D may need to increase with system size, especially in critical systems.
Density Matrix Renormalization Group: The DMRG procedure performs local optimizations at successive sites and repeats forward and backward sweeps until convergence.A sweep visits sites in the order 1, 2, …, n, n−1, …, 1.
MERA: MERA extends tensor-network methods beyond MPS: local observables remain efficiently computable, while the representation can approximate certain states in D-dimensional lattices.Its construction uses coarse-graining, including truncation and disentangling steps, repeated across scales.

6.5. Multi-Scale Entanglement Renormalization Ansatz

MERA represents quantum states through layered disentanglers and isometries, while its bounded-width causal cones enable efficient computation of local observables. The surrounding area-law discussion explains why boundary-limited entanglement can support compact classical representations and summarizes major one-dimensional results and open dimensions.

Multi-Scale Entanglement Renormalization Ansatz: MERA uses a tree-like tensor network of disentangling unitaries and isometries, with n bottom legs corresponding to the original sites.The same construction can be viewed as a tensor network or as a circuit that reverses the coarse-graining procedure to prepare an approximation of the target state.
Multi-Scale Entanglement Renormalization Ansatz: O(nd^4) bits suffice for a MERA representation when each isometric tensor has bond dimension d.The storage estimate follows from 2n−1 tensors, each storing at most O(d^4) complex numbers.
Multi-Scale Entanglement Renormalization Ansatz: MERA permits reduced states on Θ(1) sites, and hence local-observable expectation values, to be computed in O(log n) time for constant lattice dimension.The key mechanism is that each site’s causal cone has constant width in every layer, or at most 4 · 3^(D−1) more generally.
Area laws: An area law bounds entanglement between a region and its complement by a quantity proportional to boundary size |∂L| rather than volume |L|.Entanglement is typically measured by the von Neumann entropy of the region’s reduced density matrix; arbitrary states can instead exhibit volume-law entanglement.
Area laws: Area laws motivate compact tensor-network descriptions because general quantum states require exponentially many parameters, whereas area-law states may admit small-bond-dimension representations.Constant-bond-dimension tensor networks automatically satisfy an area law.
Area laws: In 2007, Hastings proved that ground states of all one-dimensional gapped local Hamiltonians obey an area law, while thermal states obey one regardless of gap or dimension.Later work supplied combinatorial proofs, improved parameters, and extensions to constant-fold degenerate ground spaces.
Area laws: Whether area laws hold in dimensions larger than one remains a major open question because known approaches do not generalize easily.Suggested routes use sufficiently fast correlation decay with few low-energy states, or adiabatic connectivity between gapped systems.

Reviews of Selected Results

The survey reviews foundational quantum Hamiltonian complexity results, including the QMA-completeness of 5-local Hamiltonian and the verification strategy behind membership in QMA. A local Hamiltonian’s ground state serves as a quantum proof whose energy can be estimated through local phase estimation.

Selected results: The survey presents Kitaev’s quantum analogue of Cook-Levin alongside selected quantum Hamiltonian complexity results.The reviewed material includes Kitaev’s 5-local Hamiltonian result and other central results in the area.
Membership in QMA: For constant k, k-local Hamiltonian is in QMA because a ground state can serve as the quantum proof.The verifier uses a local version of phase estimation to estimate the energy penalty incurred by the submitted state.
Membership in QMA: The verification circuit uses an index register to select a local term H_j and applies the corresponding operation W_j to the proof register.The index register can be viewed as choosing j uniformly at random, after which W_j is applied and the answer register is measured.
Membership in QMA: The verifier’s acceptance probability is tied to the expected Hamiltonian energy ⟨η|H|η⟩, and inverse-polynomially separated thresholds yield k-LH ∈ QMA.This connects the local verification procedure to the promise gap defining the problem.

5-Local Hamiltonian is QMA-hard

Kitaev’s reduction encodes a quantum verification circuit into a 5-local Hamiltonian whose low-energy spectrum distinguishes accepting from rejecting proofs. A unary clock and stabilization penalty remove the locality obstacle while preserving the analysis and establishing QMA-hardness.

Reduction: Kitaev gives a polynomial-time reduction from any QMA problem to 5-local Hamiltonian.The constructed Hamiltonian has a small eigenvalue exactly when an accepting proof exists with sufficiently high probability.
Hamiltonian construction: The Hamiltonian acts on proof, ancilla, and clock registers and uses input, propagation, and output penalty terms.The history state records the verifier’s computational trajectory across clock times.
YES case: A change of basis transforms the history-state analysis into a form where the YES case yields a small eigenvalue when the verifier accepts with probability at least 1−ϵ.The transformed history state has the proof, zeroed ancillas, and a uniform clock state.
NO case: The NO-case lower bound combines the Geometric Lemma with A1 = H_in + H_out and A2 = H_prop because these components do not commute.The lemma relates the spectra of the positive operators to the angle between their null spaces.
NO case: The propagation operator’s smallest positive eigenvalue is at least c/L^2, obtained from λ_k = 1 − cos[πk/(L + 1)].This spectral estimate supplies the nonzero-eigenvalue parameter needed by the Geometric Lemma.
NO case: In the NO case, the minimum eigenvalue of H scales as Ω((1 − √ϵ)/L^3), separating it from the YES-case upper bound.The resulting inverse-polynomial gap is what supports QMA-hardness.
Making H 5-local: Unary encoding replaces the log(n)-local binary clock, and the stabilization term H_stab enforces valid unary time states.The final Hamiltonian H = H_in + H_prop + H_out + H_stab preserves the preceding analysis and is 5-local.

7.2 2-local Hamiltonian is QMA-complete

The section explains a perturbative reduction from 3-local to 2-local Hamiltonians, preserving the relevant low-energy spectrum and establishing QMA-completeness of 2-local Hamiltonian.

Reduction overview: 2-local Hamiltonian is shown QMA-hard by reducing arbitrary 3-local Hamiltonians to 2-local Hamiltonians.The reduction constructs a 2-local Hamiltonian eH from a 3-local input H.
Reduction overview: The construction decomposes H into a 2-local part and products of one-local positive semidefinite operators.This rewriting isolates terms resembling Y − 6B1B2B3.
Perturbative construction: The perturbed Hamiltonian eH combines a large-gap penalty Hamiltonian Q with a small perturbation P encoding the input Hamiltonian.Q depends on the desired spectral gap, while P depends on the decomposed input terms.
Perturbative construction: An effective Hamiltonian Heff reproduces the low-energy spectrum of H, while eH is designed to simulate Heff using only 2-local interactions.The effective Hamiltonian has the same ground-state energy as the rewritten input Hamiltonian.
Spectral analysis: The self-energy Σ−(z) approximates Heff through a truncated series expansion, with operator-norm error O(δ) for suitable z.The low-order terms of the self-energy match the desired effective Hamiltonian.
Spectral analysis: If the self-energy is within ϵ of Heff, corresponding eigenvalues of Heff and eH are also within ϵ.The perturbation-theory analysis relates the jth smallest eigenvalues of the two Hamiltonians.

7.3 Commuting k-local Hamiltonians and the Structure Lemma

The section studies commuting local Hamiltonians and presents the Structure Lemma, which decomposes shared spaces so commuting neighboring constraints act on separate tensor factors.

Open complexity questions: The complexity of commuting k-local Hamiltonians remains open for general locality and local dimension.The central question is whether these problems belong to NP, QCMA, or could be QMA-complete.
Open complexity questions: Several low-locality commuting Hamiltonian cases are known to lie in NP, supported by Bravyi and Vyalyi’s Structure Lemma.Known cases include commuting 2-local Hamiltonians for d ≥ 2 and selected 3- and 4-local settings.
Structure Lemma: The Structure Lemma decomposes the shared space Y into invariant slices Yi for commuting operators acting on X ⊗ Y and Y ⊗ Z.The decomposition has the form Y = ⨁i Yi.
Structure Lemma: Within each slice Yi = Yi1 ⊗ Yi2, the two operators act nontrivially on separate factors, eliminating their overlap.A acts on X ⊗ Yi1, while B acts on Yi2 ⊗ Z.
Consequences: The decomposition lets an NP prover identify the slice containing a joint ground state, after which the constraints decouple.Property 1 permits restriction to one slice, and property 2 separates the resulting actions.
Proof strategy: The proof uses C∗-algebra techniques, including centers, invariant decompositions, commutants, and tensor-product structure for trivial-center algebras.A trivial-center algebra can be represented as L(Y1) ⊗ IY2.

7.4 Quantum 2-SAT is in P

The section presents Bravyi’s polynomial-time algorithm for Quantum 2-SAT as a quantum analogue of classical 2-SAT procedures, using rank reduction, constraint generation, and a final product-state construction.

Problem definition: Quantum 2-SAT asks whether a state satisfies every 2-local projection constraint on n qubits.The projections may have arbitrary rank, making the problem a quantum generalization of 2-CSP.
Problem definition: Bravyi answered affirmatively that Quantum 2-SAT lies in P, and the survey reformulates his algorithm using local filters.The local-filter presentation is intended to be more accessible than the original tensor-based exposition.
Algorithm: The overall procedure alternates rank reduction with constraint generation, then accepts using the saturated-system solver.If rank reduction fails, the algorithm rejects; otherwise it returns the solver’s output after saturation.
Algorithm: The algorithm repeatedly reduces constraints of rank at least 2 and rejects immediately when rank 4 makes satisfaction impossible.Rank-3 constraints force an assignment, while rank-2 constraints allow two qubits to be merged through an isometry.
Algorithm: The generateConstraints procedure derives implicit constraints on a third qubit pair from overlapping rank-1 constraints.The procedure applies the local-filter lemma and adds only linearly independent constraints.
Algorithm: When the system becomes saturated, solveSaturatedSystem constructs an efficiently computable satisfying product state.The construction starts by assigning one qubit and propagates assignments through neighboring constraints.

7.5 Area laws for one-dimensional gapped quantum systems

For a 1D gapped Hamiltonian, the area-law proof constructs an approximate ground-space projector (AGSP) whose controlled shrinking and entanglement properties bound the ground-state entropy. The survey develops this through product-state overlap, AGSP lemmas, and a Chebyshev-polynomial construction using Hamiltonian truncation.

7.5 Area laws for one-dimensional gapped quantum systems: The proof considers a 1D chain with a unique ground state and a constant spectral gap, and bounds entanglement across every cut.The presentation focuses on frustration-free Hamiltonians, while the frustrated case requires a more delicate argument.
7.5 Area laws for one-dimensional gapped quantum systems: The high-level strategy starts with a product state having constant ground-state overlap and transforms it into a better approximation without greatly increasing entanglement.This separates the proof into finding an initial product state and improving it with an operator.
7.5.1 Approximate Ground-Space Projection (AGSP): An (D, ∆)-AGSP preserves the ground space, shrinks orthogonal states by at most ∆, and has Schmidt rank at most D across the cut.Repeated application improves the ground-state approximation while creating a tradeoff between accuracy and entanglement entropy.
7.5.2 Good AGSP implies a good product state: A good AGSP together with a product state of overlap µ bounds the ground-state entropy, while an AGSP satisfying D · ∆≤1/2 itself guarantees a product state with nontrivial overlap.The survey combines these two lemmas into Theorem 7.15, reducing the area-law proof to constructing a good AGSP.