arXiv:2609.39592
The Complexity of Single-Interaction Hamiltonians
Elad Hecker
Abstract
We study the complexity of Local Hamiltonian problems under the restriction that every local term is an unweighted occurrence of the same fixed interaction. In the resulting Single-Interaction Hamiltonian (SIH) model, once the interaction is fixed, the Hamiltonian is specified entirely by its ordered interaction hypergraph. Our main technical tool is an exact compiler that converts any fixed finite alphabet of local interactions into a single interaction. On a designated auxiliary subspace, the compiled Hamiltonian reproduces the source Hamiltonian exactly, while the complete spectrum below a chosen separation scale is preserved with multiplicity. Combined with a finite-alphabet normalization, this gives a universal polynomial-time reduction from $k$-Local Hamiltonian to SIH$_{3k+3}$ up to a known global energy scale and inverse-polynomial approximation. Sharper constructions give QMA-completeness of SIH$_3$ and of geometrically local SIH$_8$ with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH$_3$ and QMA-completeness of 1-Pinned Stoq-SIH$_4$. We also establish hardness results for uniformly system-size-dependent interactions and derive single-interaction formulations of the Hamiltonian quantum PCP conjecture, frustration-free, exponentially precise, and guided Local Hamiltonian problems. These results show that independently chosen local matrices and independently tunable coupling strengths are not necessary for a broad range of Hamiltonian-complexity phenomena.
AI Summary
The paper asks how much Local Hamiltonian complexity survives when every term is an unweighted copy of one fixed qubit interaction, so that instances are encoded only in an ordered interaction hypergraph. This single-interaction Hamiltonian (SIH) model is distinct from translational invariance: interaction supports remain instance-dependent. The main tool compiles a fixed alphabet of $m$ $k$-local interactions into one interaction of locality $k+\lceil\log_2m\rceil+2$. Dedicated selector ancillas and diagonal energetic checks give an exact copy of the source Hamiltonian in a valid sector; invalid sectors lie at least $\gamma$ above its ground energy. Ground spaces and spectral multiplicities below that cutoff are preserved. Separately, Pauli expansion, coefficient rounding, and multiplicities reduce arbitrary $k$-Local Hamiltonian to $\mathrm{SIH}_{3k+3}$, with inverse-polynomial approximation and a known global energy scale. Specialized constructions establish QMA-completeness for a fixed three-local interaction and for geometrically local eight-local interactions with bounded degree and range. Stoquastic counterparts are StoqMA-complete at locality three, while pinning one qubit permits QMA-completeness at locality four. Further consequences include a single-interaction formulation equivalent to Hamiltonian qPCP, QMA-complete frustration-free instances at locality nine, PSPACE-complete geometrically local precise instances at locality eight, and BQP-complete guided instances at locality nine. The normalization step need not preserve geometry, stoquasticity, frustration freeness, or exact spectral structure; multiplicity can increase degree polynomially. Some additional constructions allow the interaction to depend uniformly on system size. Strict two-local SIH classification and lower-locality geometric constructions remain open. The universal reduction is not a general analogue-simulation theorem.
improving the clarity, organization, and language of the manuscript
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 83 pages, 1 table