PaperlayerView exact revision on arXiv

Source-linked AI summary

The complexity of antiferromagnetic interactions and 2D lattices

Stephen Piddock, Ashley Montanaro

arXiv:1506.04014v2quant-phcs.CC

TL;DR

The paper asks how the Local Hamiltonian problem changes when one fixed 2-local interaction is used with same-sign weights and restricted geometry. It classifies symmetric interactions, proves lattice hardness through perturbative gadgets, and finds broad QMA-completeness alongside specific StoqMA cases and unresolved exceptions.

  • Problem

    The work studies the complexity of Local Hamiltonian instances constrained to fixed 2-local interactions, same-sign weights, and prescribed spatial graphs.

    Source: §1 · pp. 1–3

  • Method

    The authors combine complexity classification with perturbative-gadget reductions, including sign gadgets and reductions from sparse interaction graphs to 2D lattices.

    Source: §1.2 · p. 5

  • Results

    Symmetric 2-local interactions without 1-local terms are classified as QMA-complete or in StoqMA; antiferromagnetic Heisenberg and XY are QMA-complete, transverse-field Ising is StoqMA-complete, and nearly all corresponding lattice cases remain hard.

    Source: §1 · p. 2, §1.1 · p. 3, §1.2 · p. 5

  • Takeaways & Limitations

    Same-sign and geometric restrictions still permit broad quantum computational hardness, while triangular lattices support stronger results than square lattices for several interactions.

    Source: §1.1 · p. 3, §1.2 · p. 5

    The results leave unresolved the general Heisenberg model on a square lattice, the antiferromagnetic Heisenberg model on a triangular lattice, and the issue of large gadget-induced interaction weights.

    Source: §6 · p. 33

Abstract

from arXiv · show

Estimation of the minimum eigenvalue of a quantum Hamiltonian can be formalised as the Local Hamiltonian problem. We study the natural special case of the Local Hamiltonian problem where the same 2-local interaction, with differing weights, is applied across each pair of qubits. First we consider antiferromagnetic/ferromagnetic interactions, where the weights of the terms in the Hamiltonian are restricted to all be of the same sign. We show that for symmetric 2-local interactions with no 1-local part, the problem is either QMA-complete or in StoqMA. In particular the antiferromagnetic Heisenberg and antiferromagnetic XY interactions are shown to be QMA-complete. We also prove StoqMA-completeness of the antiferromagnetic transverse field Ising model. Second, we study the Local Hamiltonian problem under the restriction that the interaction terms can only be chosen to lie on a particular graph. We prove that nearly all of the QMA-complete 2-local interactions remain QMA-complete when restricted to a 2D square lattice. Finally we consider both restrictions at the same time and discover that, with the exception of the antiferromagnetic Heisenberg interaction, all of the interactions which are QMA-complete with positive coefficients remain QMA-complete when restricted to a 2D triangular lattice.

1 Introduction

The paper classifies the complexity of restricted 2-local Hamiltonians under sign and spatial constraints, addressing limitations of unrestricted interactions. It establishes QMA-, StoqMA-, and NP-completeness results using perturbative-gadget reductions.

1 Introduction

  • The work addresses unrestricted spatial locality and mixed interaction signs, but not the physically relevant issue of polynomially large interaction weights.The authors identify large weights required by perturbation theory as a remaining limitation.Source: §1 · p. 3

1.1 Statement of results

  • Positive-weight symmetric 2-qubit interactions without 1-local terms are classified as QMA-complete, StoqMA-complete, in StoqMA, or in P under explicit coefficient conditions.The classification applies to interactions expressible as H = αXX + βYY + γZZ and extends to all symmetric 2-qubit interactions with no 1-local part via local unitaries.Source: §1.1 · p. 3
  • The antiferromagnetic Heisenberg and XY models are shown QMA-complete, while the antiferromagnetic transverse-field Ising model is StoqMA-complete.These are highlighted as first QMA-completeness results for the antiferromagnetic Heisenberg and XY interactions.Source: §1.1 · pp. 3–4
  • On a 2D square lattice, every 2-local interaction with Pauli rank at least 2 is QMA-complete except the Heisenberg interaction.The authors conjecture that the excluded Heisenberg case is also QMA-complete but do not prove it.Source: §1.1 · p. 4
  • On a 2D triangular lattice, positive-weight interactions satisfying α + β > 0, α + γ > 0, and β + γ > 0 are QMA-complete unless proportional to the Heisenberg interaction.The antiferromagnetic XY model is an important special case; the triangular lattice can therefore be more complex than the square lattice in this setting.Source: §1.1 · pp. 4–5

1.2 Proof techniques

  • The main proof strategy uses perturbative gadgets, including a second-order sign gadget and lattice reductions based on the antiferromagnetic XY model on a cyclic chain.The gadgets simulate interactions not directly available and reduce sparse interaction graphs to square lattices.Source: §1.2 · p. 5

2 Perturbation theory

The section formalizes simulation through low-energy subspaces and develops perturbative gadgets for constructing effective interactions. It then shows how gadgets compose in parallel and applies them to symmetric and antisymmetric interactions.

2.1 Definition of simulation

  • Simulation encodes a target Hamiltonian into a simulator’s low-energy subspace, approximating the target in operator norm and thereby preserving its lowest eigenvalues.A simple encoding is also used to relate simulator and target eigenvectors.Source: §2.1 · p. 6

2.2 Perturbative gadgets

  • Perturbative gadgets use Hsim = ∆H0 + V, with a dominant penalty term and first-, second-, or third-order corrections that approximate desired effective interactions.The required ∆ remains polynomial when approximation errors are inverse-polynomial.Source: §2.2 · pp. 6–8

2.3 Parallel use of gadgets

  • Gadgets can be applied in parallel on disjoint ancilla subsets, producing an effective Hamiltonian equal to the sum of the interactions simulated by each gadget.Each gadget acts on its own subset together with a shared target subset.Source: §2.3 · p. 8

2.4 The basic gadget

  • The basic gadget uses a two-ancilla ground state and partitions target qubits so opposite ancilla assignments yield positive interactions while shared assignments yield negative ones.For H = αXX + βY Y + γZZ, positivity of α + β, α + γ, and β + γ makes the singlet the unique ancilla ground state.Source: §2.4 · pp. 8–9

2.4.1 Antisymmetric case

  • For antisymmetric interactions, vanishing first-order terms leave second-order contributions that simulate XX + ZZ and ZX −XZ interactions between target qubits attached to the same or opposite ancillas.The resulting simulator Hamiltonian implements the target interaction through the stated gadget construction.Source: §2.4.1 · p. 10

3 Positive weights

For symmetric 2-local interactions with no 1-local terms, positive-weight Hamiltonians are classified as either QMA-complete or in StoqMA, with further completeness results for antiferromagnetic models.

3 Positive weights

  • A symmetric interaction H = αXX + βYY + γZZ with positive coefficients is QMA-complete when α + β > 0, α + γ > 0, and β + γ > 0; otherwise it is in StoqMA.The classification applies to the restricted {H}+-Hamiltonian problem.Source: §3 · p. 11
  • In the StoqMA region, a local basis change makes all potentially positive off-diagonal matrix elements equal to α + β ≤ 0, establishing stoquasticity.The ordering α ≤ β ≤ γ is used after relabelling Pauli operators.Source: §3 · p. 11
  • The QMA-complete region is proved by a second-order sign gadget that simulates both positive and negative interaction weights using ancillary qubits and parallel gadget applications.For each target interaction, two ancillas and a heavy interaction generate either eH12 or −eH12.Source: §3 · p. 11
  • When α = β and γ ≤ −|α|, the positive-weight problem is in P because |00...0⟩ is a ground state for every resulting Hamiltonian.This tractable region is obtained when |00⟩ is a ground state of the interaction.Source: §3 · pp. 11–12

3.1 Antiferromagnetic TIM

  • The antiferromagnetic transverse-field Ising problem {ZZ, X}+-Hamiltonian is StoqMA-complete, using encoded logical qubits in the ground space of ZZ and perturbative simulation of both signs of XX.The construction reduces from the StoqMA-complete transverse-field Ising model with unrestricted ZZ signs.Source: §3.1 · pp. 12–13

3.2 The case H = XX −Y Y + γZZ for γ > 1

  • For H = XX − YY + γZZ with γ > 1, the boundary cases are also StoqMA-complete through a two-qubit encoding and further perturbative gadgets that simulate XX and Z interactions.The proof completes the StoqMA-completeness part of the theorem for the remaining boundary region.Source: §3.2 · pp. 13–14

4 Restricted interaction graphs

The XY model is shown to remain QMA-complete with positive weights when interactions are restricted to the edges of a 2D triangular lattice.

4 Restricted interaction graphs

  • QMA-completeness on a 2D triangular lattice is established by reducing first to a spatially sparse graph and then adapting fork and crossing gadgets to the triangular lattice.The construction simultaneously preserves positive weights and triangular-lattice geometry.Source: §4 · p. 14

4.1 Spatial sparsity

The paper develops a spatially sparse XY construction using cyclic-chain correlations, then arranges the encoded system over a square-lattice layout before applying further geometric gadgets.

4.1 Spatial sparsity

  • A spatially sparse graph has bounded vertex degree, a planar straight-line drawing with bounded edge overlap, and O(1) edge lengths.These conditions define the graph class used for the reduction.Source: §4.1 · p. 14
  • The reduction targets Hamiltonians of XX, ZZ, X, and Z terms and requires efficiently computable spin correlations that remain at least inverse-polynomial in distance.The correlation lower bound ensures that simulated coefficients remain polynomially bounded.Source: §4.1 · p. 15
  • The spatially sparse construction is needed because the complete-graph XY model violates the required sparsity conditions, while a constant spectral gap would force long-distance correlations to decay exponentially.The chosen cyclic chain balances a vanishing gap against the inverse-polynomial correlation requirement.Source: §4.1 · p. 15
  • A cyclic XY chain with even length N not divisible by 4 has a nondegenerate ground state, spectral gap Ω(1/N), and correlations Ω(n^-1/2) for separations n = o(N^4/7).The spectral gap and correlations can be computed efficiently by a classical algorithm.Source: §4.1 · p. 15
  • The construction adds √n ancillas and encodes two logical qubits into three physical qubits while placing a cyclic XY chain along the layout, requiring correlations over distances at most 2n^1/2.This yields a spatially sparse XY Hamiltonian, but its local triples and inter-triangle couplings do not yet form a square lattice.Source: §4.1 · p. 15, Figure 3 · p. 16

4.2 Mediator qubit pair gadgets

Mediator-qubit-pair gadgets convert spatially sparse XY interaction graphs into planar lattice constructions by using perturbative subdivision, fork, and crossing gadgets.

4.2 Mediator qubit pair gadgets

  • A mediator-qubit pair projected into the ground space of a 2-local interaction generates effective interactions through second-order perturbation theory; XY gadgets require cancelling unwanted terms.This extends the basic perturbative gadget to settings where only 2-local interactions are available.Source: §4.2 · p. 16

4.2.1 Subdivision gadgets

  • Subdivision gadgets connected to opposite ancillas simulate X1X2 + Y1Y2, whereas connections to the same ancilla simulate −X1X2 − Y1Y2.Both positive and negative effective XY interactions can be extended through constant-length gadget chains.Source: §4.2.1 · p. 17

4.2.2 Fork gadget

  • The fork gadget reduces a vertex degree by replacing H13 + H23 with a gadget whose main terms are H1a + H2a + H3b and whose correction is H12.The correction cancels the unwanted −H12 term generated by perturbation theory.Source: §4.2.2 · p. 17, Figure 5 · p. 17

4.2.3 Crossing gadget

  • The crossing gadget removes an edge crossing by using main terms H1a + H2a + H3b + H4b and corrections H12 + H34 − H13 − H24 to simulate H14 + H23.The right-hand gadget therefore realizes the crossing interaction pattern without a geometric crossing.Source: §4.2.3 · p. 17

4.3 XY model on a 2D planar graph of degree 3

The construction transforms a spatially sparse Hamiltonian into a planar degree-3 interaction graph with controlled geometry using mediator-qubit gadgets.

4.3 XY model on a 2D planar graph of degree 3

  • Subdivision, fork, and crossing gadgets reduce high-degree vertices and crossings while preserving a planar interaction graph of degree at most 3.Degree reduction is repeated in parallel, and crossings are isolated before applying crossing gadgets.Source: §4.3 · p. 18
  • The resulting planar graph has straight-line edges of length O(1) and adjacent-edge angles of Ω(1), preparing it for lattice embedding.Source: §4.3 · p. 18

4.4 2D triangular lattice

The planar degree-3 construction is embedded into a fine triangular lattice, where path-parity control enables positive-weight simulation of the antiferromagnetic XY interaction.

4.4 2D triangular lattice

  • The planar graph is mapped onto a fine triangular grid, with vertices moved to nearby lattice points and edges rerouted along nonintersecting lattice paths.The controlled edge angles ensure intersections are confined to small regions around original vertices.Source: §4.4 · p. 18
  • Triangular-lattice paths can realize either +H or −H by choosing the parity of mediator qubits, completing QMA-completeness for antiferromagnetic XY.An extra qubit can be inserted along a triangular path to select the required parity.Source: §4.4 · p. 18
  • The parity construction extends to essentially any non-bipartite lattice containing suitable odd cycles.Source: §4.4 · p. 18

4.5 Other interactions on a triangular lattice

Triangular-lattice gadgets combine effective interactions along multiple paths to generate QMA-complete interactions using only positive weights, including general symmetric Pauli interactions outside the Heisenberg case.

4.5 Other interactions on a triangular lattice

  • A tessellating triangular gadget combines two path-mediated interactions to produce a linear combination sufficient to generate XX + YY.The gadget is designed so separate copies fit on the triangular lattice without overlap.Source: §4.5 · p. 19, Figure 6 · p. 19
  • Parallel fork gadgets cancel unwanted mediator-induced terms, yielding controlled effective interactions between selected endpoint qubits.The blue and red components implement different signed combinations of effective interactions.Source: §4.5 · p. 19
  • The triangular gadget first produces an effective interaction H′, which is then combined into −λH(1) and +µH(2) for the target simulation.Source: §4.5 · p. 20

4.5.1 The case αXX + βYY

  • For αXX + βYY with α, β > 0, positive coefficients λ and µ combine −λH(1) + µH(2) to simulate XX + YY.The required coefficients are computable from α and β.Source: §4.5.1 · p. 20

4.5.2 The case αXX + βYY + γZZ

  • For general αXX + βYY + γZZ satisfying pairwise-positive coefficient sums and excluding the Heisenberg interaction, the positive-weight Hamiltonian is QMA-complete on a 2D triangular lattice.The proof handles a unique maximum and tied-maximum cases through the one-parameter simulated family.Source: §4.5.2 · pp. 21–22

4.6 2D square lattice

Square-lattice gadgets preserve QMA-completeness for nearly all relevant 2-local interactions, while allowing negative weights and cancellation of non-trivial 1-local terms.

4.6 2D square lattice

  • Bipartite path parity prevents positive-only implementation of every desired interaction sign, so the square-lattice construction permits both positive and negative weights.Conjugating one partition by Z changes the signs of selected Pauli terms.Source: §4.6 · p. 22
  • For symmetric interactions with at least two nonzero Pauli coefficients that are not all equal, square-lattice gadgets generate XX + YY and establish QMA-completeness.Negative interactions are required in the gadget to cancel unwanted effective terms on the bipartite lattice.Source: §4.6 · pp. 22–23

4.6.1 Interactions with non-trivial 1-local part

  • Gadgets cancel 1-local terms on interior qubits and remove residual boundary terms using additional square gadgets.The construction assigns interaction signs to cancel local contributions across rows and columns.Source: §4.6.1 · pp. 23–25
  • A six-qubit square-lattice gadget tessellates and simulates XX + ZZ from XZ − ZX, enabling the antisymmetric case after relabelling Z to Y.Source: §4.6.1 · p. 25, Figure 11 · p. 25
  • Theorem 3 proves QMA-completeness on a 2D square lattice for any 2-local qubit interaction of Pauli rank at least 2 whose 2-local part is not proportional to XX + YY + ZZ.The theorem includes interactions with non-trivial 1-local parts.Source: §4.6.1 · p. 25

5 The XY model on a cyclic chain

The finite cyclic XY chain is solved through a free-fermion transformation, yielding a unique ground state, an inverse-linear spectral gap, and controlled spin correlations. Toeplitz and Fisher–Hartwig methods connect finite-chain quantities to their asymptotic behavior.

5.1 Ground State and Spectral Gap

  • The XY chain maps through a Jordan–Wigner transformation to free fermions, whose parity sectors can be diagonalized separately.The resulting single-particle eigenvalues are Λ_k = cos(2πk/N).Source: §5.1 · pp. 26–27
  • The ground state is unique because the negative-energy sector supplies the correct parity, while the competing sector lies at higher energy.For even N not divisible by 4, P|Ω⟩ = −|Ω⟩, so the ground state of H− is also an eigenstate of the full Hamiltonian.Source: §5.1 · pp. 27–28

5.1.1 Spectral gap

  • The exact spectral gap is tan(π/N)^−1, obtained by comparing excitation energies in the two parity sectors.The comparison includes the lowest excited states in both P = −1 and P = +1 sectors.Source: §5.1.1 · p. 28

5.2 Spin correlation functions

  • Spin correlations reduce by Wick’s theorem to determinants ρ_ij = det R_n,N, with translational invariance making them depend on the separation.The finite-chain matrix R_n,N is compared with its infinite-chain limit R_n.Source: §5.2 · pp. 29–30

5.3 Toeplitz matrices

  • Fisher–Hartwig analysis evaluates the discontinuous Toeplitz symbol and yields the asymptotic determinant constant 0.58835….The symbol has two Fisher–Hartwig singularities, and the exact constant agrees with prior work.Source: §5.3 · pp. 30–31

5.4 Relation between Rn,N and Rn

  • For even N not divisible by 4, the cyclic XY Hamiltonian has a nondegenerate ground state and spectral gap Ω(1/N).The same result gives an efficient classical algorithm for computing the gap and correlation functions.Source: §5.4 · p. 33
  • For separations n = o(N^4/7), the finite-chain correlations satisfy ⟨Ω|X_iX_j + Y_iY_j|Ω⟩ = Ω(n^−1/2).The finite-chain approximation is established under N = Ω(n^α) for α > 7/4, while stronger numerical evidence suggests relaxed conditions may suffice.Source: §5.4 · pp. 31, 33

6 Outlook

The outlook identifies large interaction weights and unresolved complexity classifications as important remaining boundaries. It also notes that sign and topology restrictions produce a rich complexity structure.

6 Outlook

  • Large interaction weights remain a significant limitation because the perturbative gadgets used for QMA-completeness require them.The authors suggest combining their results with lower-weight QMA-hardness techniques [9] [10] [11].Source: §6 · p. 33
  • The complexity of the general Heisenberg model on a square lattice and the antiferromagnetic Heisenberg model on a triangular lattice remains unresolved.The authors suggest that an exactly solvable, nontrivial, suitably sparse Heisenberg special case could resolve these questions.Source: §6 · p. 33
  • Other open cases include tighter fixed-sign classifications, the ferromagnetic XY model, nonzero 1-local interactions, and S+-Hamiltonians with |S| ⩾ 2.These gaps include interactions known to lie in StoqMA but not known to be StoqMA-complete or in a smaller class.Source: §6 · p. 33
  • Together, the results and open questions show that Local Hamiltonian complexity depends richly on restrictions of interaction signs and interaction-graph topology.The conclusion specifically highlights the combined role of these restrictions.Source: §6 · p. 33
Loading 1506.04014v2…