Classical witnesses for commuting local Hamiltonians
For every fixed locality and local dimension , is the commuting-projector local-Hamiltonian promise problem in ? The input has polynomially many commuting -local projectors with finite rational/algebraic descriptions and inverse-polynomi
Problem statement
For every fixed locality and local dimension , is the commuting-projector local-Hamiltonian promise problem in ? The input has polynomially many commuting -local projectors with finite rational/algebraic descriptions and inverse-polynomially separated ground-energy thresholds; no interaction geometry is assumed.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
Commuting terms have a common eigenbasis, but a useful eigenstate need not have an obvious efficiently verifiable classical description. Topological order can occur even in frustration-free commuting models, such as the toric code; it does not require frustration.
What is known: Two-local commuting Hamiltonians are in NP at every fixed local dimension (Bravyi–Vyalyi), as are three-local qubit instances. Results for four-local qubits, including Schuch's square-lattice case, have geometric hypotheses; they are not blanket theorems for arbitrary four-local interactions.
More recent positive cases include Irani–Jiang's two-dimensional qutrit setting and factorized two-dimensional interactions, and Bostanci–Hwang's rank-one two-dimensional case without a local-dimension restriction and a specified rank-one three-dimensional family with qudits on edges. Rank, geometry and local dimension are essential parts of these theorems. General fixed-locality NP membership remains open. Related: A4, A6.
Progress & source assessment
Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.
published: ITCS 2026 proves NP membership for specified rank-one 2D and 3D commuting Hamiltonians, not arbitrary commuting local Hamiltonians. Evidence
- [1]Bravyi & Vyalyi, 'Commutative version of the local Hamiltonian problem and common eigenspace problem', Quantum Inf. Comput. 5 (2005) link
- [2]Irani & Jiang, 'Commuting local Hamiltonian problem on 2D beyond qubits', Commun. Math. Phys. (2025) link
- [3]Bostanci & Hwang, 'Commuting Local Hamiltonians Beyond 2D', ITCS 2026 link
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.