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

1. Problem Statement and Context

The Commuting Local Hamiltonian (CLH) problem asks whether the ground-state energy of a local Hamiltonian, where all local terms pairwise commute, is below a threshold $\alpha$ or above $\beta$. While the general Local Hamiltonian problem is QMA-complete, the complexity of the commuting variant remains a central open question in quantum complexity theory.

Previous work has demonstrated that for specific families of commuting Hamiltonians (e.g., 2-local, certain 3-local, or those on specific lattices), the problem lies in NP. However, no formal evidence existed to rule out the possibility that the general CLH problem is QMA-complete.

The complexity class QIMA (Quantum Interactive Merlin-Arthur with Commuting units) was introduced by Bostanci and Hwang to capture the power of quantum verifiers whose local test units are mutually commuting reflections. The CLH problem is complete for QIMA. Consequently, the question of whether CLH is QMA-complete is equivalent to asking whether QIMA = QMA.

This paper investigates the relationship between QIMA and BQP (Bounded-error Quantum Polynomial time) in a relativized setting. Specifically, it seeks to determine if there exists a classical oracle $O$ such that BQP$^O \not\subseteq$ QIMA$^O$. A positive result would provide relativized evidence against the possibility that the general CLH problem is BQP-hard, and thus against the possibility that it is QMA-complete.

2. Methodology and Definitions

2.1 The Oracle Model QIMA$^O$

The authors define a relativized analogue of QIMA, denoted QIMA$^O$, with specific constraints to ensure the model remains a non-trivial restriction of QMA$^O$:

• Verifier Structure: On input $x$, the verifier performs classical preprocessing (making adaptive queries to $O$) to generate a set of "units" $W_1^O, \dots, W_m^O$ acting on a quantum witness.
• Commutativity: On promised instances, all units must pairwise commute: $[W_i^O, W_j^O] = 0$.
• Reflection Requirement: Crucially, any unit $W_j^O$ that contains at least one quantum oracle query must be an exact reflection (i.e., $(W_j^O)^\dagger = W_j^O$ and $(W_j^O)^2 = I$). Oracle-free units may be arbitrary unitaries.
• Verification: The verifier uses the Hadamard test to check if the witness is in the $+1$ eigenspace of each unit.
• No Trusted Ancilla: The verifier has no trusted workspace beyond the fresh control qubits used for the Hadamard tests.

The authors argue that the Reflection Requirement is essential. They show that relaxing this to allow arbitrary commuting units (even those close to reflections) or allowing trusted ancilla qubits collapses the class to QMA$^O$.

2.2 The Forrelation Problem

The separation is based on the Forrelation problem, defined by Aaronson. Given oracle access to two Boolean functions $f, g: \{0,1\}^n \to \{-1, +1\}$, the task is to distinguish between:

• Yes: $f$ is highly correlated with the Fourier transform of $g$ ($\Phi(f,g) \ge \alpha$).
• No: The correlation is small ($|\Phi(f,g)| \le \beta$).

Forrelation is solvable by a BQP algorithm with a constant number of quantum queries. The paper aims to prove that any QIMA$^O$ verifier for Forrelation requires an exponential number of queries.

3. Key Contributions and Results

3.1 Oracle Separation: BQP$^O \not\subseteq$ QIMA$^O$

The primary result is the construction of a classical oracle $O$ such that BQP$^O \not\subseteq$ QIMA$^O$. This is achieved by proving an exponential query lower bound for the Forrelation problem against QIMA$^O$ verifiers.

Theorem 1.7 (Informal): Any QIMA$^O$ verifier deciding Forrelation for all promised pairs $(f, g)$ must satisfy:
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
where $C(n)$ is the number of classical preprocessing queries and $T(n)$ is the total number of quantum oracle queries.

Proof Sketch:

1. Polynomial Method: The acceptance probability of the verifier is expressed as a polynomial in the oracle's truth-table entries.
2. Commutativity and Reflections: Because the oracle-containing units are exact reflections and commute, their combined acceptance operator is a product of orthogonal projectors. This allows the authors to define a single projector $P_f$ representing the intersection of all acceptance subspaces.
3. Degree Bound: The degree of the polynomial representing the acceptance probability is bounded by the total number of quantum queries $T(n)$.
4. Perfect Forrelation Pairs: The authors utilize "perfect Forrelation pairs" (bent functions) where $\Phi(g, h) = 1$. They show that perturbing $h$ by $k$ bits changes the Forrelation value linearly: $\Phi(g, f) = 1 - 2k/N$.
5. Symmetrization: By fixing the classical transcript and averaging over functions with a fixed Hamming distance from a perfect pair, they construct a univariate polynomial $q(k)$.
6. Root Counting: The polynomial $q(k)$ must be zero for all "No" instances (a large range of $k$) and non-zero for the "Yes" instance ($k=0$). A non-zero polynomial cannot have more roots than its degree, forcing the degree (and thus the query count) to be exponential.

3.2 Robustness of the Separation

The paper demonstrates that the separation holds even under slight relaxations of the model:

• Negligible Deviations: If oracle-containing units are allowed to be negligibly close (in operator norm) to exact reflections, the class remains QIMA$^O$, and the lower bound still holds.
• Restricted Address Support: The authors extend the lower bound to units that are not reflections but make only a single query, provided the oracle-free circuits surrounding the query act non-trivially on only a small number of address qubits ($k$). If $n - k(n) = \omega(\log n)$, the query lower bound remains superpolynomial.

3.3 Tightness of the Model (Collapse Results)

To justify the specific constraints of QIMA$^O$, the authors prove that relaxing these constraints collapses the class to QMA$^O$:

• Inverse-Polynomial Deviations: If units are allowed to be within an inverse-polynomial distance of a reflection (rather than negligible), the class collapses to QMA$^O$. This is shown using a variation of the Marriott-Watrous amplification gadget, constructing a single unit that simulates a QMA verifier.
• Single Query without Reflection: If the reflection requirement is removed entirely but units are restricted to a single query, the class still collapses to QMA$^O$. This uses a cyclic clock construction (similar to Feynman-Kitaev) to encode a multi-query simulation into a single query.
• Trusted Ancilla: Allowing the verifier a single trusted ancilla qubit (initialized to $|0\rangle$) collapses QIMA to QMA and QIMA$^O$ to QMA$^O$. This relies on the "Pinned Commuting Local Hamiltonian" problem, which is known to be QMA-complete.

4. Significance and Claims

The paper claims to provide relativized evidence against the possibility that the general CLH problem is BQP-hard. Since BQP is contained in QMA, if CLH were BQP-hard, it would imply strong structural properties about QMA. The separation $BQP^O \not\subseteq QIMA^O$ suggests that the commutativity constraint in QIMA (and by extension, CLH) is a significant restriction that prevents the class from capturing the full power of BQP, even in the presence of oracles.

Furthermore, the work clarifies the tightness of the QIMA definition. The authors argue that the specific combination of commutativity, the reflection requirement for oracle queries, and the absence of trusted ancillas is necessary to define a class that is strictly weaker than QMA. Relaxing any of these conditions immediately recovers the full power of QMA, suggesting that the "quantumness" of QIMA is fragile and relies precisely on these structural constraints.

The results do not resolve the unrelativized question of whether CLH is QMA-complete, but they establish that any proof of such completeness would require non-relativizing techniques, as the statement fails relative to the constructed oracle.