{"id":"arxiv/2609.38957","url":"https://arxiv.org/abs/2609.38957","tags":["quant-ph","cs.CC"],"score":0,"title":"The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness","domain":"quant-ph","source":"arxiv","authors":["Itay Shalit","Mark Zhandry"],"reviews":0,"subject":"quant-ph","summary":"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 $\\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\\mathsf{QMA}$-complete. CLH is complete for the complexity class $\\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\\mathsf{QMA}$-complete if and only if…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}