Complexity of commuting Hamiltonians on a square lattice of qubits

Norbert Schuch

Source-linked AI summary

Complexity of commuting Hamiltonians on a square lattice of qubits

Norbert Schuch

arXiv:1105.2843v2May 13, 2011quant-ph

TL;DR

The paper studies whether commuting plaquette terms on a square lattice of qubits have a common state minimizing every local term. It constructs an efficiently checkable classical certificate for this property, without providing instructions to prepare the state, and establishes NP containment for the problem.

Problem
Determining whether commuting Hamiltonians have a ground state that minimizes every local term is difficult because an efficiently checkable classical description of the ground state is not generally known.
Source: §1 · p. 3, §2 · p. 4
Method
The approach decomposes the commuting structure into two layers and uses algebraic direct-sum decompositions so a certificate can specify slices whose overlap is nonzero and efficiently computable.
Source: §3.2 · p. 5, §3.4 · p. 13
Results
The commuting Hamiltonian problem for square-lattice qubits with plaquette interactions is in NP, with the certificate verified by efficiently computing the relevant overlap.
Source: §1 · p. 3, §3.4 · p. 13, §3.5 · p. 14
Takeaways & Limitations
The certificate proves existence of a suitable ground state without yielding a quantum circuit to prepare it, so the approach remains applicable to systems with topological order.
Source: §1 · p. 3
Beyond qubits, efficient overlap evaluation is not guaranteed, and a decomposition into three layers cannot be used for the same argument.
Source: §3.3 · p. 7, §4 · p. 15

Abstract

from arXiv · show

We consider the computational complexity of Hamiltonians which are sums of commuting terms acting on plaquettes in a square lattice of qubits, and we show that deciding whether the ground state minimizes the energy of each local term individually is in the complexity class NP. That is, if the ground states has this property, this can be proven using a classical certificate which can be efficiently verified on a classical computer. Different to previous results on commuting Hamiltonians, our certificate proves the existence of such a state without giving instructions on how to prepare it.

1 Introduction

The commuting Hamiltonian problem asks whether local ground-state conditions can be jointly satisfied, and this paper proves NP containment for qubit plaquette Hamiltonians on a square lattice without requiring a state-preparation circuit.

For general quantum spin systems, estimating ground-state energy is QMA-complete, including restricted two-dimensional nearest-neighbor and one-dimensional settings [5].Source: §1 · p. 2
Commuting Hamiltonians can support topological order and anyonic excitations despite having mutually commuting local terms, motivating their complexity study.Source: §1 · p. 2
The commuting Hamiltonian problem asks whether a ground state minimizes every local term individually, but its general membership in NP is unclear because ground states may lack efficient classical descriptions.Source: §1 · pp. 2–3
Earlier NP-membership results for two-local and selected three-body commuting Hamiltonians also yielded constant-depth preparation circuits, ruling out topological order in those cases [11].Source: §1 · p. 3
For square-lattice qubits with plaquette-wise commuting interactions, the paper proves NP membership using a classical certificate that verifies existence without providing a ground-state preparation circuit.Source: §1 · p. 3

2 The setup

The setup uses commuting four-qubit plaquette terms on a two-dimensional square lattice and asks whether their local ground spaces have a common state.

The model places spins on square-lattice vertices with either open or periodic boundary conditions.Source: §2 · p. 3
Each plaquette term acts on its four adjacent spins, and all Hamiltonian terms commute pairwise.Source: §2 · p. 4
The commuting Hamiltonian decision problem asks whether an eigenstate simultaneously minimizes the energy of every local term.Source: §2 · p. 4
The problem is NP-hard because it includes classical Ising spin glasses in a field, which are NP-hard for two-level systems.Source: §2 · p. 4
Equivalently, the local ground-state projectors commute, and the question is whether their product projector onto the common ground space is nonzero.Source: §2 · p. 4

3 Commuting Hamiltonian in NP

The proof splits the square lattice into black and white plaquette layers, encodes simultaneous local ground spaces through decompositions, and reduces verification to a nonzero overlap. For qubits, overlap structures are one-dimensional and computable efficiently, including with finite numerical accuracy, establishing NP membership.

3.1 Two layers

3.1 Two layers: Checkerboard projectors reduce the commuting Hamiltonian question to deciding whether the black- and white-layer ground-space projectors have nonzero overlap.A certificate must establish the validity of this nonzero-overlap condition.Source: §3.1 · pp. 4–5

3.2 The structure of one layer

3.2 The structure of one layer: C*-algebraic decompositions split each overlapping local Hilbert space into slices where neighboring projectors act on independent subsystems.Applying these decompositions across vertices makes each layer factorize over compatible local sectors, and the decompositions can be computed efficiently.Source: §3.2 · pp. 5–6

3.3 Combining the layers

3.3 Combining the layers: A classical certificate supplies sector labels α⃗ and β⃗ for which the overlap Ω(α⃗,β⃗) is nonzero, proving existence without encoding state-preparation instructions.Although overlaps of differently partitioned plaquette-product states can generally be PP-hard, commuting-layer constraints enable efficient evaluation here.Source: §3.3 · p. 7

3.4 Computing the overlap

3.4 Computing the overlap: Effective plaquette terms form only one-dimensional chains because each central term can overlap nontrivially with at most two adjacent terms, so their contraction is efficient.The qubit-specific local decompositions rule out branching structures, reducing Ω(α⃗,β⃗) to efficiently contractible one-dimensional components.Source: §3.4 · pp. 8, 10, 11, 12, 13

3.5 Finite accuracy

3.5 Finite accuracy: The relevant certificate can be chosen with Ω(α⃗,β⃗) ≥ 2^-2N, so polynomial-precision contraction suffices for polynomial-time verification.The Hamiltonian terms are assumed exactly represented with poly(N) digits, while local decomposition projectors arise from fixed-size eigenvalue problems.Source: §3.5 · pp. 13–14

4 Summary

The paper proves the commuting Hamiltonian problem is NP-complete for square-lattice qubits with plaquette interactions, using layer decompositions and efficiently computable overlaps. The approach can extend to some systems beyond qubits, but has clear limitations for higher-dimensional local systems and three-layer decompositions.

4 Summary

The problem is NP-complete, with a classical certificate establishing that a ground state minimizes every local term.The certificate proves existence without providing a procedure for preparing the ground state.Source: §4 · p. 14
The proof splits the Hamiltonian into two layers, decomposes each into direct-sum slices, and checks whether selected layer ground states have non-zero overlap.For qubits, the overlap reduces to one-dimensional structures that can be contracted efficiently.Source: §4 · p. 14
The method can apply beyond qubits when slice decompositions or separable states make the relevant overlap efficiently computable.Examples include one-dimensional spaces in Kitaev’s toric code or quantum double models, separable ρp states, and suitable two-layer graphs.Source: §4 · pp. 14–15
A three-layer decomposition is unusable for this argument because tr[ABC] can have either real or imaginary parts with either sign.Thus, nonzero overlap is no longer equivalent to the positivity condition required by the proof.Source: §4 · p. 15
For four-level systems, commuting operators may both act nontrivially on one local spin, while qutrit extensions face unresolved projection and tracing difficulties.For qutrits, it remains unclear whether an analogue of the needed relation can be established when projections have rank 1 or 2.Source: §4 · p. 15