PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity classification of local Hamiltonian problems

Toby Cubitt, Ashley Montanaro

arXiv:1311.3161v5quant-ph

TL;DR

The paper asks how restricting local Hamiltonian terms to a fixed interaction set changes the complexity of ground-state energy estimation. It develops algebraic classifications for these sets, resolving all 2-local qubit cases and extending the result to arbitrary constant locality when 1-local terms are available. The classifications yield tractable, NP-complete, StoqMA-complete, or QMA-complete problems and establish QMA-completeness for several important physical interactions.

  • Problem

    The paper studies how to characterize the complexity of local Hamiltonian problems when all terms are chosen from a fixed set S, a quantum analogue of classifying restricted constraint satisfaction problems.

  • Method

    The authors classify interaction sets using local diagonalisation and related algebraic conditions, and prove hardness through perturbative gadgets that simulate QMA-hard interactions.

  • Results

    The classification resolves all 2-local qubit cases, including QMA-completeness of the Heisenberg, XYZ, XXZ, and XY models and StoqMA-completeness of the transverse-field Ising case.

  • Takeaways & Limitations

    Restricted local Hamiltonians fall into sharply characterized complexity classes, extending the dichotomy perspective from Boolean constraint satisfaction to quantum interactions.

  • Takeaways & Limitations

    The full classification beyond 2-local interactions is not obtained when 1-local interactions are unavailable, and the general assumptions can allow physically less meaningful weights and interaction ranges.

Abstract

from arXiv · show

The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterise the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes has been shown to be StoqMA-complete by Bravyi and Hastings. The characterisation holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.

1 Introduction

The paper classifies the computational complexity of fixed-interaction local Hamiltonians, essentially resolving the 2-local qubit case. It gives separate classifications with and without access to 1-local terms and proves hardness for important physical models.

  • Problem setting: The k-local Hamiltonian problem asks whether a Hamiltonian’s smallest eigenvalue is below a or above b, and general k-local Hamiltonian is QMA-complete for k ≥ 2.This formalises ground-state energy estimation as a quantum analogue of constraint satisfaction.
  • Main classification: The paper essentially completely resolves the complexity classification of S-Hamiltonian when every interaction acts on at most 2 qubits.S-Hamiltonian restricts each local term to be proportional to a matrix from a fixed finite set S.
  • Scope and limitations: The results do not fully classify S-Hamiltonian for k > 2 without 1-local interactions, and the classified instances may contain polynomially large weights, mixed signs, or long-range interactions.The authors identify the lack of 1-local interactions as one reason a full classification beyond 2-local interactions was not achieved.
  • With local terms: With arbitrary 1-local terms available, the classification is P when S′ is empty, StoqMA-complete when S′ is locally diagonalizable, and QMA-complete otherwise.S′ removes each interaction’s 1-local part and then deletes 0-local matrices.
  • Without local terms: Without assuming any 1-local matrices, 2-local S-Hamiltonian is classified into P, NP-complete, StoqMA-complete, or QMA-complete cases according to algebraic properties of S.The intermediate StoqMA-complete class includes the transverse-field Ising model, where {ZZ, X}-Hamiltonian is StoqMA-complete.
  • Physical models: The classification proves QMA-completeness for the Heisenberg, XYZ, XXZ, and XY models, including Heisenberg interactions without additional 1-local terms.For Heisenberg interactions, the coefficients may be independently positive or negative; prior work had not established even NP-hardness in that unrestricted setting.
  • Proof techniques: The hardness proofs simulate QMA-hard interactions with perturbative gadgets that project onto low-energy subspaces or generate virtual interactions.The constructions produce virtual Heisenberg or XY interactions from almost any 2-qubit interaction without 1-local parts.

2 Preliminaries

The paper establishes notation for Pauli decompositions and two-qubit normal forms, then develops perturbative tools for simulating interactions through low-energy subspaces.

  • Notation: Any k-qubit Hermitian matrix can be decomposed into tensor products of Pauli matrices, with local parts classified by the number of non-identity factors.Pauli weight counts non-identity factors, while traceless matrices have no 0-local component.
  • Normal form: Two-qubit interactions are represented by a correlation matrix M(H), whose rank defines the Pauli rank and whose symmetry reflects qubit-exchange symmetry.Symmetric interactions have equal one-qubit coefficient vectors, whereas antisymmetric interactions have opposite vectors.
  • Normal form: Single-qubit unitaries induce SO(3) rotations on Pauli coefficients, enabling a common local-unitary normal form for two-qubit Hamiltonians.The same unitary on both qubits preserves eigenvalues of Hamiltonians built from the transformed interaction.
  • Perturbation theory: Perturbative gadgets simulate interactions unavailable directly by projecting onto low-energy subspaces or inducing effective two-local terms with strong auxiliary interactions.The second gadget type has no classical analogue and uses suitably scaled 1-local terms to generate effective interactions.
  • Perturbation theory: Corollaries of perturbation theory support both second-order simulations and first-order encodings, with the latter controlling the low-energy subspace in operator norm.The first-order result can be applied a constant number of times in series, which is needed for encoding data in the low-energy subspace.

3 S-Hamiltonian with local terms

With arbitrary 1-local terms available, the paper classifies 2-local S-Hamiltonian problems using local diagonalisation and interaction normal forms. The nontrivial cases are either StoqMA-complete or QMA-complete, with hardness surviving equal weights and square-lattice restrictions.

  • Setup: The local-terms variant adds arbitrary single-qubit Hermitian interactions to S, making it a generalisation of S-Hamiltonian and facilitating hardness reductions.Access to X, Y, and Z is equivalent to access to all 1-local Hermitian terms.
  • QMA-complete cases: The QMA-complete category includes XX + γZZ, XX + βYY + γZZ, and XZ − ZX interactions for the stated nonzero-parameter conditions.Each listed problem remains QMA-complete under equal weights and square-lattice locality.
  • Classification: For 2-local sets, removing 1-local and 0-local parts yields a three-way classification: P, StoqMA-complete after local diagonalisation, or QMA-complete otherwise.The QMA-complete case remains hard with equal-weight interactions restricted to a two-dimensional square lattice.
  • StoqMA-complete case: The locally diagonalizable case is equivalent to the ZZ model with local terms and is StoqMA-complete.A suitable single-qubit unitary transforms every two-qubit interaction into a ZZ interaction up to rescaling.
  • General k-local extension: The classification extends to constant-k local terms: empty nonlocal parts give P, locally diagonalizable sets give StoqMA-completeness, and all remaining sets are QMA-complete.The theorem applies when S contains all 1-local terms and uses simultaneous local diagonalisation as the dividing condition.

4 The case without local terms

Without assuming access to arbitrary 1-local terms, the paper classifies all 2-local qubit S-Hamiltonians into P, NP-complete, StoqMA-complete, or QMA-complete cases.

  • Proof strategy: The proof without local terms replaces the earlier perturbative gadgets with encodings of logical qubits into multiple physical qubits and reductions among simpler interaction sets.The approach is designed for settings where the interaction set does not include all 1-local terms.
  • QMA-complete cases: The Heisenberg interaction XX + YY + ZZ, the XY interaction XX + YY, and XZ − ZX are QMA-complete without freely available 1-local terms.The paper also establishes QMA-completeness for broader families with nonzero XX, YY, or ZZ coefficients and certain 1-local additions.
  • Diagonal interactions: Purely 1-local diagonal sets yield problems in P, whereas diagonal sets containing a genuinely 2-local interaction are NP-complete.This is the classical diagonal subcase of the general classification.
  • Classification: For arbitrary 2-local sets, local diagonalisation gives NP-completeness, an Ising-like normal form with local terms gives StoqMA-completeness, and all remaining cases are QMA-complete.The four cases are determined by whether interactions are all 1-local, locally diagonalizable, reducible to ZZ plus 1-local terms, or none of these.
  • QMA-hardness proof: The QMA-hard subcases are reduced to canonical interactions using Pauli-rank analysis, local-unitary transformations, and combinations of interaction terms.When transformed rank-one interactions have incompatible directions, subtraction produces an XX + γZZ-type interaction with γ nonzero.

5 Special cases

The paper proves QMA-completeness for several restricted two-qubit interactions, including Heisenberg, XY, and XZ−ZX, even without additional 1-local terms. It uses encoded logical qubits and exactly solvable Heisenberg instances to simulate general Hamiltonians.

  • 5.1 The Heisenberg model: The Heisenberg interaction is XX + YY + ZZ, with coefficients αij that may be positive or negative.The antiferromagnetic and ferromagnetic cases correspond respectively to nonnegative and nonpositive coefficients.
  • 5.2 Restricted Heisenberg models: A three-physical-qubit encoding exploits swap symmetry to represent each logical qubit in a larger invariant subspace.Interactions within encoded blocks generate logical X and Z operators, while cross-block interactions generate logical two-qubit terms.
  • 5.2 Restricted Heisenberg models: The construction implements arbitrary Hamiltonians of the form αkXk + βkZk + γijXiXj + δijZiZj, which suffices for QMA-completeness.A non-degenerate auxiliary ground state is used to project unwanted encoded degrees of freedom away.
  • 5.2 Restricted Heisenberg models: {XX + YY + ZZ}-Hamiltonian is QMA-complete, establishing hardness without additional 1-local terms.This extends prior hardness results that allowed arbitrary local magnetic fields.
  • 5.1 The Heisenberg model: For nonpositive Heisenberg coefficients, ground-state energy estimation is in P, while nonnegative coefficients on bipartite interaction graphs place the problem in StoqMA.These restrictions differ from the unrestricted-sign model proved QMA-complete.
  • 5.3 The XY model: {XX + YY}-Hamiltonian and {XZ − ZX}-Hamiltonian are also QMA-complete.The skew-symmetric result follows by reducing from the XY model.

6 More general models

The paper extends the hardness analysis to broader two-qubit interactions by constructing encoded gadgets that reproduce the XY interaction or retain two nonzero Pauli components. These reductions yield QMA-completeness for broad parameter families.

  • 6 More general models: For XX + αYY with α not in {0, 1}, a three-qubit gadget produces a logical two-qubit space.Projecting two copies into their lowest-energy subspaces yields effective XX and YY interactions.
  • 6 More general models: Linear combinations of the effective interactions implement XX and YY separately, and therefore XX + YY is QMA-complete.The reduction uses the previously established QMA-completeness of the XY model.
  • 6 More general models: For XX + αYY + βZZ, a three-qubit gadget creates a logical qubit whenever at least one of α or β is nonzero.Two copies of the gadget provide effective interactions whose combinations retain the required nonzero components.
  • 6 More general models: For any real β and γ with at least one nonzero, {XX + βYY + γZZ}-Hamiltonian is QMA-complete.The remaining case α = 1 is reduced to the XY interaction by taking a suitable linear combination.

7 Extracting local terms

The paper shows how restricted two-qubit interactions can generate arbitrary 1-local terms through projection gadgets. This reduces several models with local terms to previously established QMA-complete interaction families.

  • 7 Extracting local terms: A gadget for a symmetric interaction produces arbitrary 1-local terms of the form αX + βZ.Taking linear combinations and discarding the identity term gives the claimed local interactions.
  • 7 Extracting local terms: A four-qubit gadget can eliminate an arbitrary 1-local term while preserving a nontrivial interaction αXX + βYY + γZZ.The gadget has a maximally entangled ground state across a suitable bipartition, causing unwanted terms to vanish after projection.
  • 7 Extracting local terms: Consequently, {XX + βYY + γZZ + AI + IA}-Hamiltonian is QMA-complete whenever at least one of β and γ is nonzero.The result follows by reducing to the QMA-complete interaction family without local terms.
  • 7 Extracting local terms: For XZ − ZX + AI − IA, a directed four-edge gadget extracts the arbitrary single-qubit operator A.The direction of the interaction matters because XZ − ZX is not symmetric.
  • 7 Extracting local terms: Using an ancilla and an XX interaction, the construction effectively implements arbitrary local X terms alongside XX and Z terms.The two sign choices are unitarily equivalent under conjugation by Z⊗n.
  • 7 Extracting local terms: The construction also shows that {ZZ, X, Z}-Hamiltonian reduces to {ZZ + AI + IA}-Hamiltonian for A not commuting with Z.A related skew-symmetric gadget gives the reduction to {ZZ, AI − IA}-Hamiltonian.

8 The diagonal case

For diagonal two-qubit interactions, the complexity dichotomy is simple: purely 1-local sets are in P, while every set containing a genuinely 2-local diagonal interaction is NP-complete.

  • 8 The diagonal case: If every matrix in a diagonal set S is 1-local, S-Hamiltonian is in P; otherwise, it is NP-complete.The problem lies in NP because diagonal Hamiltonians attain their minimum on computational-basis states.
  • 8 The diagonal case: When a diagonal interaction has a unique minimum entry, gadgets and linear combinations can implement any diagonal matrix, including ZZ.The resulting reduction from MAX-CUT establishes NP-hardness.
  • 8 The diagonal case: If the diagonal interaction has non-unique maximum and minimum values, any non-1-local case has the form diag(α, β, β, α) with α ≠ β.Combining this interaction with the identity directly produces ZZ.

9 Outlook

The paper resolves the complexity of a natural subclass of S-Hamiltonian problems while leaving several generalisations and related dichotomy questions open. These include broader locality and domains, restricted interactions, commuting Hamiltonians, quantum k-SAT, and unitary gates.

  • Open generalisations: Extending the full S-Hamiltonian classification to k > 2 is hindered by the lack of a suitable normal form for Hermitian matrices on k ≥ 3 qubits.The existing reduction to 2-local Hamiltonians also appears difficult without access to 1-local terms.
  • Open generalisations: Generalising the results beyond qubits may be difficult, paralleling the 24-year effort required to extend Schaefer’s dichotomy theorem to a 3-element domain.Bulatov resolved that constraint-satisfaction generalisation in 2002.
  • Restricted models: Further hardness classifications remain open for restricted coefficients, such as antiferromagnetic interactions, and restricted geometries, such as planar graphs or square lattices.Subsequent work obtained results for some antiferromagnetic XY and Heisenberg cases.
  • Related classifications: Commuting Hamiltonians already have tractable special cases, including 2-local and 3-local qubit systems and certain projector-based families, while one commuting 4-local class is in NP.These results cover several distinct locality and operator restrictions.
  • Related classifications: A further direction is a dichotomy theorem for quantum k-SAT, where projector terms define constraints and the question asks whether a state satisfies them all.Quantum k-SAT was introduced by Bravyi, who established an initial result for the problem.
  • Related classifications: Another open question asks whether gate sets are always classically simulable or universal for BQP, although the analogous Hamiltonian-generated gate case was recently resolved.That resolved case allows 2-local Hamiltonians from a given set to act for arbitrary lengths of time.

A Complexity class definitions

This appendix defines QMA and StoqMA as promise-problem classes through verifier acceptance probabilities, with bounded completeness and soundness conditions.

  • QMA: QMA is defined for promise problems using polynomial-size quantum witnesses and uniformly generated quantum verifier circuits.
  • QMA: For yes instances, QMA requires a witness accepted with probability at least 2/3.
  • QMA: For no instances, every polynomial-size witness must be accepted with probability at most 1/3.
  • StoqMA: StoqMA uses stoquastic verifiers built from X, CNOT, and Toffoli gates, with witness, ancilla, and |+⟩ registers.
  • StoqMA: StoqMA requires completeness c and soundness s for acceptance probabilities over yes and no instances, respectively.The definitions impose a promise gap between the two thresholds.

B Characterisations of diagonalisability by local unitaries

The appendix gives equivalent criteria for when a finite family of 2-qubit Hermitian matrices can be simultaneously diagonalised by local unitaries, including an efficient commutator-based test.

  • Equivalent characterisations: A family is locally simultaneously diagonalizable exactly when one single-qubit unitary diagonalizes every matrix under its tensor square.
  • Equivalent characterisations: Equivalently, every family member is a linear combination of A⊗A, A⊗I, I⊗A, and I⊗I for one single-qubit Hermitian matrix A.
  • Equivalent characterisations: A further equivalent condition requires specific cross-subsystem commutators to vanish for every pair of family members.
  • Proof structure: In the diagonal basis, each matrix has the form α_nZ⊗Z + β_nZ⊗I + γ_nI⊗Z + δ_nI⊗I.
  • Proof structure: The commuting conditions imply a common diagonalizing unitary, and the characterisation yields an efficient test for local diagonalizability.An alternative test solves linear equations for a nontrivial single-qubit matrix A commuting appropriately with H.

C Normal form for Hermitian matrices

The appendix develops normal-form results for traceless 2-qubit Hermitian matrices using rotations in SO(3), their SU(2) representation, and exchange symmetry.

  • General normal form: The normal-form analysis begins with traceless 2-qubit Hermitian matrices and represents their coefficient transformations through real orthogonal rotations.
  • General normal form: For every R∈SO(3), an associated U∈SU(2) conjugates the Pauli operators according to the rotation.
  • Exchange symmetry: If a matrix is symmetric under exchanging its two qubits, a common single-qubit unitary brings it to a form with separately structured coefficients.
  • Exchange symmetry: If a matrix is antisymmetric under qubit exchange, an SU(2) transformation yields a corresponding antisymmetric normal form with distinct Pauli directions.

D QMA-hardness of special cases of S-Hamiltonian with local terms

The paper proves QMA-hardness for several restricted Hamiltonian families by using perturbative gadgets to synthesize interactions and transfer hardness from known QMA-complete problems. These results remain valid under strong geometric and weighting restrictions, including square-lattice support and uniform interaction weights.

  • Perturbative-gadget framework: Second-order perturbative gadgets generate effective interactions from allowed terms, with additive error O(δ^-1) when the penalty parameter δ is polynomially large.The construction reduces from a QMA-complete target interaction set and uses δ = poly(n).
  • Perturbative-gadget framework: Parallel gadget applications simulate arbitrarily many interactions without changing parameters, whereas serial applications are restricted to a constant number because each increases the Hamiltonian norm polynomially.The parallel construction works because distinct gadgets do not interfere to second order.
  • Base hardness result: 2-local Hamiltonian remains QMA-complete for Pauli-product interactions on the edges of a two-dimensional square lattice, with arbitrary real coefficients and arbitrary one-qubit Hermitian terms.The cited theorem combines earlier hardness results for restricted Pauli interactions and lattice geometry.
  • Restricted interaction families: {XX, ZZ}-Hamiltonian with local terms is QMA-complete even on a two-dimensional square lattice when all XX terms have fixed nonzero weight α and all ZZ terms have fixed nonzero weight β.Gadgets produce effective XZ, XX, and ZZ interactions with arbitrary weights while preserving the lattice structure and equal-weight constraints.
  • Restricted interaction families: For any fixed nonzero γ, {XX + γZZ}-Hamiltonian with local terms is QMA-complete with equal-weight interactions restricted to a two-dimensional square lattice.The result follows by reducing from the fixed-weight {XX, ZZ} family.
  • Restricted interaction families: The same hardness holds for {XX + βYY + γZZ} with fixed β and nonzero γ, and for {XZ − ZX}, even with equal weights and square-lattice support.The former follows by generating XX + γ²ZZ and applying the preceding lemma; the latter is stated as a separate QMA-complete family.

E The Lieb-Mattis model

The Lieb-Mattis model is analyzed through collective-spin operators and the Heisenberg model on complete graphs. Its ground state is unique, has energy −n(n + 2), and exhibits distinct flip correlations within and between the two blocks.

  • Collective-spin analysis: The Heisenberg Hamiltonian on the complete graph has eigenvalues 2s(s + 1) − 3n/4, with allowed spin values determined by whether n is even or odd.For even n, s ranges from 0 to n/2; for odd n, it ranges over half-integers from 1/2 to n/2.
  • Collective-spin analysis: Simultaneous eigenvalues of S2 and Sz satisfy λ = s(s + 1), with s ranging up to n/2 and |m| ≤ s.The allowed values of s are integral for even n and half-integral for odd n.
  • Ground state: The Lieb-Mattis ground state is unique and has energy −n(n + 2).The lower bound is achieved by the explicitly constructed ground state, and uniqueness is established by fixed-Hamming-weight sectors and spin constraints.
  • Ground-state correlations: The ground state is invariant under flips within either block, giving expectation 1, while flips between blocks have expectation −2/n.The two blocks each contain n qubits in the complete bipartite model.
  • Ground state: Uniqueness within each fixed-magnetization sector follows by applying Perron-Frobenius to an irreducible matrix, while nonzero-magnetization sectors cannot attain the ground energy.The spin bound s ≥ |m| excludes additional ground states outside the zero-magnetization sector.
Loading 1311.3161v5…