npj Quantum Information · 10 Nov 2026
On the complexity of the succinct state local Hamiltonian problem
Gabriel Waite, Karl Lin
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenCitations0
- Crossref0
Citations per year
The current year is still counting.
- 2026 so far0
Abstract
Abstract We study the computational complexity of the LOCAL HAMILTONIAN problem under the promise that its ground state, or a low-energy state, is succinctly represented. We show, for qubit Hamiltonians, that the SUCCINCT LOW-ENERGY STATE 2-LOCAL HAMILTONIAN problem, is (promise) MA -hard and the SUCCINCT GROUND STATE 3-LOCAL HAMILTONIAN problem is (promise) MA -complete. Our approach combines a systematic characterisation of succinct quantum states, defined through arithmetic over specific number fields, with a refined complexity-theoretic reduction that lowers the locality of Feynman–Kitaev circuit-Hamiltonians from 6 to 2, without increasing particle dimension. Since the 1-local case is solvable in P , these results narrow the locality-parameterised complexity transition and extend the scope of known MA -complete problem instances. Our results further clarify how succinctness behaves under circuit-based constructions, and progress towards a better understanding of the boundary between efficiently describable and efficiently verifiable quantum systems.
What the data shows
- No database records a citation yet, as is usual for a paper this new.
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (0)
What it cites, from open citation data, with Crossref's record of each.