Skip to content
DraconiticResearch
Search Sources API
182,544 studies31 sourcesUpdated 28 min ago
PreprintCC BY 4.0arXiv

The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness

  • Itay Shalit
  • Mark Zhandry
Open at sourcePDFDOICite

Abstract

The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in NP for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is QMA-complete. CLH is complete for the complexity class QIMA, defined through quantum verifiers whose local gates commute. Therefore, CLH is QMA-complete if and only if QIMA=QMA. In this work, we introduce a classical-oracle analogue QIMA𝒪 and construct a classical oracle 𝒪 such that BQP𝒪not⊆QIMA𝒪. Since BQP𝒪⊆QMA𝒪 for any classical oracle 𝒪, this implies QIMA𝒪≠QMA𝒪 for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is BQP-hard, and hence also against the possibility that it is QMA-complete.

Related

  1. The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
    Mikhail Mints, Eric R. Anschuetz
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. Problem-aware sampling for bias and variance reduction in randomised Hamiltonian simulation
    Brian Coyle, Jonathan H. Fetherolf, Antonio Márquez Romero +3
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. A Full Reproduction of the Godfrey--Isgur Relativized Quark Model
    Mikhail Mikhasenko
    arXivPreprintCC BY-NC-ND 4.0Full textHigh-energy & particle physicsarXiv
  4. The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups
    Mauro E. S. Morales
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  5. Hardware's Cut: The Non-Commuting Consequence Gate and the Guillotine of Thermodynamics (Document 134)
    Torjusen Marius Egerhei
    Zenodo (CERN European Organization for Nuclear Research)PreprintLicence not stated9 citedStatistical & nonlinear physicsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{shalit2026commuting,
  title = {{The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness}},
  author = {Itay Shalit and Mark Zhandry},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38957},
  eprint = {2609.38957},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38957},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
AU  - Itay Shalit
AU  - Mark Zhandry
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.38957
UR  - https://arxiv.org/abs/2609.38957
AB  - The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in NP for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is QMA-complete. CLH is complete for the complexity class QIMA, defined through quantum verifiers whose local gates commute. Therefore, CLH is QMA-complete if and only if QIMA=QMA. In this work, we introduce a classical-oracle analogue QIMA^𝒪 and construct a classical oracle 𝒪 such that BQP^𝒪not⊆QIMA^𝒪. Since BQP^𝒪⊆QMA^𝒪 for any classical oracle 𝒪, this implies QIMA^𝒪≠QMA^𝒪 for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is BQP-hard, and hence also against the possibility that it is QMA-complete.
ER  -