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

AI summary

Overview

Research area: quantum complexity theory, specifically Hamiltonian complexity and oracle separations. Technical level: Advanced. Scope: a relativized complexity-theoretic study of whether the commuting local Hamiltonian problem can be BQP-hard or QMA-complete.

What This Paper Is About

The paper studies the commuting local Hamiltonian (CLH) problem, a restriction of the local Hamiltonian problem in which all local terms pairwise commute. It asks whether this restricted problem is still as hard as the general local Hamiltonian problem, and it provides relativized evidence that it is not BQP-hard, and hence not QMA-complete. The authors do this by defining an oracle analogue of the complexity class QIMA, for which CLH is complete, and constructing a classical oracle that separates BQP from QIMA.

Key Contributions

1. The paper defines an oracle analogue of QIMA, denoted QIMA^O, based on a verifier that performs classical preprocessing with adaptive classical oracle queries and then tests a polynomial-size set of commuting units using Hadamard tests. Units containing quantum oracle queries must be exact reflections, while oracle-free units may be arbitrary unitaries.
2. It proves an exponential query lower bound for the Forrelation problem against QIMA^O verifiers: any such verifier deciding Forrelation must satisfy C(n) + T(n) ≥ β2^n − O(1) for all sufficiently large even n, where C(n) counts classical preprocessing queries, T(n) counts quantum oracle queries, and β is the Forrelation promise parameter.
3. It uses diagonalization to construct a single classical oracle O such that BQP^O is not contained in QIMA^O. Since BQP^O is contained in QMA^O for any classical oracle O, this implies QIMA^O ≠ QMA^O for the constructed oracle.
4. It analyzes alternative relativizations and shows that several natural relaxations collapse QIMA^O to QMA^O, including allowing general non-reflection oracle-querying units, allowing one-query units with unrestricted address support, and adding one trusted ancilla qubit.

Main Findings

• CLH is complete for QIMA. The paper states that the general commuting local Hamiltonian problem is complete for QIMA, and therefore CLH is QMA-complete if and only if QIMA = QMA. This equivalence is the basis for interpreting the oracle separation as evidence about CLH.
• Forrelation requires exponentially many queries for QIMA^O verifiers. Although Forrelation can be decided by a polynomial-time quantum algorithm making constantly many oracle queries, any QIMA^O verifier for Forrelation must satisfy C(n) + T(n) ≥ β2^n − O(1) for sufficiently large even n.
• There is a classical oracle separating BQP from QIMA. The constructed oracle O satisfies BQP^O ⊄ QIMA^O. Because BQP^O ⊆ QMA^O for any classical oracle O, the result gives QIMA^O ≠ QMA^O. The authors describe this as relativized evidence against the general CLH problem being BQP-hard and, by the QIMA = QMA equivalence, against it being QMA-complete.
• The reflection requirement is essential in the oracle setting. The paper shows that if oracle-querying units are allowed to be general unitaries rather than exact reflections, the resulting class equals QMA^O. The same collapse occurs even if each such unit is only inverse-polynomially close in operator norm to an exact oracle-free reflection. This contrasts with the unrelativized setting, where reflecting units are without loss of generality under perfect completeness.
• Negligible deviations from reflections do not change the class. The lower bound extends to a relaxation in which each oracle-containing unit is negligibly close in operator norm to an exact companion reflection, uniformly over promised instances, provided the companions satisfy additional query and commutation conditions.
• One-query units with unrestricted address support collapse to QMA^O. If every oracle-containing unit has the form A O^(Q) B, where A and B are oracle-free circuits acting on the full witness register, and the reflection requirement is dropped, the resulting class equals QMA^O. Every problem in QMA^O can be verified using one such unit and therefore one oracle query.
• Restricting address support gives a lower bound. If each additional one-query unit acts nontrivially on at most k(n) of the n address qubits, any verifier deciding Forrelation must satisfy C(n) + 2^{k(n)} T(n) ≥ β2^n − O(1) for even n. Consequently, if C(n) is polynomial, then T(n) = Ω(2^{n−k(n)}). Polynomial-query verification is impossible when n − k(n) = ω(log n), and the bound is exponential for k(n) ≤ (1 − ε)n with constant ε > 0.
• One trusted ancilla qubit collapses the class. Variants of QIMA and QIMA^O that allow an inverse-polynomial completeness–soundness gap and one additional trusted qubit initialized to |0⟩ equal QMA and QMA^O, respectively. In the oracle setting, the simulation can use a single oracle-containing unit that is an exact reflection.
• No unrelativized separation is claimed. The paper does not prove QIMA ≠ QMA in the plain model. It also does not establish whether requiring perfect completeness changes the oracle class QIMA^O.

Methodology in Plain English

The authors reduce the question to a query-complexity lower bound for the Forrelation problem. Forrelation asks whether two Boolean functions f and g are highly correlated after applying a Hadamard transform to g. It is easy for a quantum algorithm with a constant number of oracle queries, so an exponential lower bound against QIMA^O verifiers gives a strong separation.

The proof fixes the classical preprocessing transcript on a special “perfect Forrelation pair” (g, h), where g and h are bent functions and the Forrelation value is exactly 1. Bent functions exist for any even n. Keeping g fixed and varying f on the entries not queried during preprocessing preserves the same transcript, so the verifier produces the same quantum circuits for many different f.

The authors then extract an algebraic quantity p(f) from the verifier. On YES-instances, completeness forces p(f) ≥ 1; on NO-instances, soundness forces p(f) = 0. Because each quantum oracle query contributes at most one degree to the polynomial describing the verifier’s matrices, p(f) is a low-degree polynomial in the truth-table entries of f, with degree bounded by the total number of quantum queries T(n). Choosing a family of NO-instances that are perturbations of the perfect pair yields many roots of this polynomial. A Minsky–Papert symmetrization step converts this into a univariate polynomial with many distinct roots, and counting those roots forces the query lower bound.

The oracle separation then follows by diagonalization: the authors assemble Forrelation instances into slices of a single classical oracle O, ensuring that a BQP machine can decide the resulting language while no QIMA^O verifier can.

Why This Matters

This paper sharpens the boundary between commuting and noncommuting quantum computations. It gives formal relativized evidence that the general commuting local Hamiltonian problem may not inherit the full hardness of the local Hamiltonian problem, and it identifies which features of the QIMA model are essential for keeping the oracle class nontrivial. The results also clarify why naive relativizations of QIMA can collapse to QMA, which is important for future work on oracle separations in Hamiltonian complexity.

The paper does not report real-world applications. Potential long-term areas of relevance include:

• Quantum error-correcting codes and quantum LDPC code Hamiltonians, which are commuting projector Hamiltonians and played a role in the proof of the NLTS conjecture.
• Quantum many-body physics, including ground-state entanglement structure, area laws, and efficient preparation of Gibbs states for commuting Hamiltonians.
• Quantum chemistry and materials science, where commuting Hamiltonian models can serve as tractable approximations or test cases for ground-state energy problems.
• Commuting quantum circuit models such as IQP, which are studied as candidates for demonstrating quantum advantage and as restricted computational models with distinctive structure.

Industry relevance is indirect and theoretical. The work informs how quantum computing researchers should think about the hardness of simulating commuting Hamiltonians, the limitations of commuting quantum circuits, and the design of oracle-based evidence for complexity separations. It does not present an algorithm, hardware protocol, or near-term application.

Future Directions

• Prove or refute QIMA = QMA in the unrelativized setting. The paper provides only relativized evidence, so the plain-model question remains open.
• Determine the exact boundary between the address-support lower bound and the collapse to QMA^O for one-query units. The paper compares restricted and unrestricted address support but does not identify an exact threshold.
• Determine whether requiring perfect completeness changes QIMA^O. The oracle model allows an inverse-polynomial completeness–soundness gap, and the paper does not establish whether the perfectly complete restriction defines the same class.
• Extend the separation to narrower oracle models and other commuting computational models, and clarify the relationship between these oracle results and structural questions such as the quantum PCP conjecture and NLTS.

Target Audience

This paper is best suited for researchers and graduate students in quantum complexity theory, Hamiltonian complexity, and theoretical computer science. Readers should be comfortable with QMA, oracle separations, the polynomial method, and query complexity. It is not beginner-friendly, but it is valuable for anyone studying the hardness of commuting local Hamiltonians, relativization in quantum complexity, or the power of commuting quantum computations.

Authors’ 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.