The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
quant-ph, cs.CC
Submitted: 2026-09-30
Updated: 2026-09-30
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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 for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is-complete. CLH is complete for the complexity class, defined through quantum verifiers whose local gates commute. Therefore, CLH is-complete if and only if =. In this work, we introduce a classical-oracle analogue O and construct a classical oracle O such that O O. Since O O for any classical oracle O, this implies O not equal to O for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is-hard, and hence also against the possibility that it is-complete.
Sources
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians