REVIEW
The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
Quantum Physics · Submitted 30 Sep 2026 · 58 references
Pith's verdict: First real relativized evidence bearing on the CLH-versus-QMA question, and the mathematics is sound, but the evidential force rests on a reflection-model relativization the authors themselves show is fragile.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Relative to a constructed classical oracle, the paper separates BQP from the commuting-verifier class QIMA, giving the first formal evidence that the general commuting local-Hamiltonian problem is neither BQP-hard nor QMA-complete.
The reading
What carries the argument
The argument rests on three objects. The reflection normal form (Definition 1.4) relativizes QIMA by requiring every unit that makes a quantum oracle query to be an exact self-inverse reflection, so its Hadamard-test acceptance operator $(I+R)/2$ is a true projector. Forrelation and its perfect pairs: by the Girish-Servedio characterization, $\Phi(g,f)=1$ exactly when $H_N g = f$, i.e., when $g$ is a bent function of the Maiorana-McFarland family, and perturbing the paired function by $k$ truth-table flips changes the Forrelation value linearly to $1 - 2k/N$, mapping Hamming layers onto rings of yes-instances and no-instances. The polynomial method plus Minsky-Papert symmetrization bounds the acceptance dimension $p(f) = \mathrm{Tr}(QP^f)$, a polynomial of degree at most the quantum query count that is at least 1 on yes-instances and 0 on no-instances, converting query counts into root counting on a univariate polynomial.
Extended reading notes
Core claim
The central claim, proved as Theorem 3.5 and promoted to a diagonalized oracle separation in Section 3.4, is that relative to a constructed classical oracle $O$, $\mathsf{BQP}^O \not\subseteq \mathsf{QIMA}^O$, and hence $\mathsf{QIMA}^O \neq \mathsf{QMA}^O$. Because CLH is complete for QIMA, this is relativized evidence that the general commuting local-Hamiltonian problem is neither BQP-hard nor QMA-complete. The proof works by showing that any verifier satisfying the reflection normal form and deciding the Forrelation promise problem must make exponentially many queries: after the classical preprocessing is frozen on a perfect Forrelation pair built from a bent function, the dimension of the accepting subspace becomes a multilinear polynomial in the oracle truth-table whose degree is bounded by the number of quantum queries; Minsky-Papert symmetrization turns it into a univariate polynomial that is nonzero at the perfect pair but vanishes on $\beta 2^n - O(1)$ integer no-instances, forcing a matching degree lower bound.
Load-bearing premise
The separation stands on treating the reflection normal form — requiring every oracle-touching verification unit to be an exact self-inverse reflection — as the canonical way to relativize QIMA, a choice the paper itself shows is fragile, since inverse-polynomial deviations, a single generic query, or a single trusted ancilla each collapse the class to QMA.
Editorial extensions
If this is right
- If the general CLH problem were QMA-complete, then QIMA would equal QMA; the oracle separation relativizes this possibility away, so any proof of QMA-completeness would have to be non-relativizing.
- The exponential lower bound $C(n)+T(n) \ge \beta 2^n - O(1)$ applies to the perfectly-complete restriction of the oracle model, not only the inverse-polynomial-gap version.
- The separation extends to units negligibly close to exact reflections (Section 3.3) and to one-query units with restricted address support (Section 3.5); the constant-query IQP Forrelation algorithms do not transfer because IQP verifiers use trusted initialized registers that QIMA verifiers lack.
- Allowing inverse-polynomial deviations from reflections, a single generic one-query unit, or a single trusted ancilla each collapse the class to QMA^O, so the separation is tight against these natural relaxations.
Reading between the lines
- The separation's bearing on the unrelativized CLH-versus-QMA question is hostage to whether the reflection normal form is the canonical relativization; the authors concede that at the trivial oracle the model gives $\mathsf{QIMA}^{O_0} = \mathsf{QMA}$, so it does not even recover plain QIMA.
- A reader who finds the reflection requirement arbitrary can read the collapse theorems as evidence the other way: because every nearby natural relaxation recovers QMA, the oracle separation may be an artifact of the normalization rather than a fact about commuting Hamiltonians.
- A testable extension would be a relativization derived directly from the commuting-local-Hamiltonian verifier rather than from the reflection normal form — if any such intrinsic definition makes $\mathsf{QIMA}^O = \mathsf{QMA}^O$, the relativized evidence evaporates.
Original 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 $\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 $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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 $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s1 | A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s2 | Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. | gap 1.00 | 0.04 | 0.03 | asserted 0.78 |
| s3 | CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. | result 0.48 | 0.33 | 0.04 | asserted 1.00 |
| s4 | Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. | background 0.54 | 0.24 | 0.07 | asserted 1.00 |
| s5 | In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. | contribution 0.93 | 0.96 | 0.14 | asserted 1.00 |
| s6 | Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. | interpretation 0.70 | 0.73 | 0.10 | asserted 1.00 |
| s7 | Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete. | interpretation 0.99 | 0.92 | 0.94 | hedged possibility 0.57 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.