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

1 Introduction

• The local-Hamiltonian problem asks whether the ground-state energy is at most α or at least β, and becomes QMA-complete under an inverse-polynomial promise gap.The introduction identifies commuting local Hamiltonians as a structural restriction that removes noncommuting observables, a central source of uniquely quantum behavior.Source: §1 · p. 3
• Commuting Hamiltonians also inform quantum many-body questions involving error-correcting codes, PCP techniques, ground-state entanglement, area laws, and Gibbs-state preparation.The cited examples include commuting projector Hamiltonians arising from quantum error-correcting codes [ABN23] and structural results exposing obstacles to adapting classical PCP techniques.Source: §1 · p. 3
• Earlier results place 2-local commuting Hamiltonians and several other restricted families in NP, but leave open whether the general problem is QMA-complete.The ground-space connectivity problem remains QCMA-complete even for commuting local Hamiltonians.Source: §1 · p. 3
• QIMA verifiers use polynomially many mutually commuting k-local reflections and Hadamard tests on a quantum witness; the commuting local-Hamiltonian problem is QIMA-complete.The paper uses a reflection normal form equivalent to a verifier definition allowing general local unitaries.Source: §1 · pp. 3–4
• QIMA-completeness is familywise: each fixed-locality problem lies in QIMA, while each QIMA problem reduces to k-local CLH for some constant k.The constant may depend on the promise problem; the paper does not claim one fixed locality is complete for all of QIMA.Source: §1 · p. 4

1.1 Our Contributions

• The paper introduces QIMA^O and states a Forrelation query lower-bound theorem parameterized by classical preprocessing queries, quantum queries, and the promise parameter.The oracle construction uses slices encoding Forrelation instances.Source: §1.1 · pp. 4–6

1.1.1 The Reflection Requirement

• Unrelativized QIMA can use reflecting units without loss under perfect completeness, but oracle relativization explicitly requires oracle-containing units to be reflections.The +1-eigenspace projectors commute, and replacing each unit by its associated reflection preserves perfect completeness and can only improve soundness; an implicit oracle-dependent projector may not be efficiently implemented with comparable query complexity.Source: §1.1.1 · pp. 6–7
• Negligible operator-norm deviations from reflections preserve QIMA^O, whereas inverse-polynomial deviations permit simulation of QMA^O verifiers.The negligible-deviation formulation requires commuting companions produced without additional classical queries and using no more quantum queries than the corresponding units.Source: §1.1.1 · p. 7
• One unrestricted one-query unit yields QMA^O, while bounded address support preserves a query lower bound when superlogarithmically many address qubits remain untouched.The lower bound is exponential when the support is at most (1−ε)n for constant ε; the paper does not identify an exact threshold between the restricted and unrestricted regimes.Source: §1.1.1 · p. 8

1.1.2 Ancilla Qubits

• Adding one trusted qubit initialized to |0⟩ makes the inverse-polynomial-gap variants of QIMA and QIMA^O equal to QMA and QMA^O, respectively.In the oracle setting, the simulation can use a single oracle-containing unit that is an exact reflection.Source: §1.1.2 · p. 9

1.1.3 Locality

• Because oracle queries act on an n-qubit register, QIMA^O permits nonlocal units; the resulting separation also applies to narrower oracle extensions contained in this model.The cited narrower example uses constant-locality oracle-free reflections and individual oracle-query reflections, with all units commuting.Source: §1.1.3 · p. 9

1.1.4 Completeness and Soundness Parameters

• QIMA^O allows inverse-polynomial completeness–soundness gaps, and the separation also applies to its perfectly complete restriction.The paper does not establish whether requiring perfect completeness changes this oracle class; arbitrary oracle-free unitaries mean its acceptance operator need not be a projector.Source: §1.1.4 · pp. 9–10

1.2.1 Commuting Local-Hamiltonians

• NP containment has been proved for commuting local Hamiltonians with several structural restrictions, including 2-local systems, selected 3-local systems, and certain geometric families.The cited work also includes arbitrary-local-dimension rank-one systems in two dimensions and a family of three-dimensional systems.Source: §1.2.1 · p. 10
• The ground-state connectivity problem remains QCMA-hard for commuting local Hamiltonians, as it is for general local Hamiltonians.Source: §1.2.1 · p. 10

1.2.2 The Forrelation Problem

• Forrelation has constant-query quantum algorithms, while prior work established strong randomized-query lower bounds and oracle separations involving BQP and the Polynomial Hierarchy.The cited results include an exponential randomized-query lower bound for an extremal Forrelation variant despite an exact one-query quantum algorithm.Source: §1.2.2 · p. 10
• IQP algorithms for Forrelation do not directly yield QIMA verifiers because QIMA receives an untrusted target register and lacks trusted initialized workspace.The paper states that allowing a trusted ancilla qubit collapses QIMA to QMA.Source: §1.2.2 · pp. 10–11

1.3.1 The oracle separation.

• Forrelation has a constant-query quantum algorithm, but QIMA^O verifiers require exponentially many queries, yielding a classical oracle separation.Source: §1.3.1 · p. 11, Perfect Forrelation Pairs · p. 15

Perfect Forrelation Pairs.

• Commuting reflection tests define a common accepting subspace whose dimension is positive on YES-instances and zero on NO-instances.The reflection condition makes oracle-dependent tests projectors, and commutativity lets the verifier’s accepting conditions be combined.Source: §1.3.1 · p. 11, Perfect Forrelation Pairs · p. 13
• After fixing g, Forrelation depends on f’s Hamming distance from h, enabling symmetrization into a bounded-degree polynomial with many NO-instance roots but a nonzero value at the perfect YES-instance.The root count forces a large degree and hence the query lower bound.Source: Perfect Forrelation Pairs · pp. 12, 14
• Fixing preprocessing on a perfect Forrelation pair freezes its transcript, with at most C(n) queried positions of h constrained across functions sharing that transcript.Source: Perfect Forrelation Pairs · p. 12

1.3.1 The oracle separation.

• The same query lower bound holds when oracle-containing units are negligibly close to commuting exact companion reflections.Replacing the units with their companions preserves a noticeable completeness-soundness gap.Source: Perfect Forrelation Pairs · p. 15

1.3.2 Collapse to QMAO

• Allowing inverse-polynomial deviations from reflections suffices to simulate QMA^O, with witness-supplied workspace validity checked while preserving commutation.The verifier’s workspace must be supplied by the witness because QIMA verifiers lack trusted workspace.Source: §1.3.2 · p. 15
• A cyclic clock construction reduces a polynomial-query verifier unit to one oracle query while retaining an inverse-polynomial completeness-soundness gap.The enlarged witness supplies both workspace and clock, but the construction does not preserve the near-reflection guarantee.Source: §1.3.2 · p. 16
• One trusted active qubit suffices for QMA in the plain model and QMA^O in the oracle model, with an inverse-polynomial gap.The plain-model route uses a pinned commuting Hamiltonian test; the oracle construction checks workspace initialization alongside acceptance.Source: §1.3.2 · pp. 16–17

• The authors report using AI tools to complete and formalize specified proofs and improve writing, while retaining responsibility for the results’ correctness.They state that they developed the separation idea, several proof approaches, and the exposition and interpretation.Source: §1.4 · p. 17

• Section 2 gives preliminaries, Section 3 proves Forrelation is outside QIMA^O, and Section 4 presents collapse results for natural model extensions.The authors describe the collapse results as showing a tightness property of their model.Source: §1.5 · p. 17

2.1 The Class QIMAk

• A QIMAk verifier receives a polynomial-size quantum witness and constructs polynomially many mutually commuting k-local reflections.The reflections act on the witness register, and the verifier tests each using a fresh control qubit, controlled-Ri, and an X-basis measurement, accepting only if every outcome is +.Source: §2.1 · p. 18
• The verifier’s reflection tests use Hadamard tests: each control qubit starts in |+⟩, and acceptance requires every X-basis measurement to yield +.Source: §2.1 · p. 18
• Constant-local unitaries specified by exact algebraic matrices are allowed as elementary gates, with descriptions generated uniformly in polynomial time.Local Hamiltonian terms use the same exact representation.Source: §2.1 · p. 18

2.2 Alternating Projectors

• The two projectors P and Q split the space into invariant blocks of dimension at most two, where λ is the acceptance probability associated with the QMA witness.For the unit vector |p⟩ spanning im P within a block, λ = ⟨p|Q|p⟩.Source: §2.2 · p. 19
• On each two-dimensional block, the product RQRP has eigenvalues e±2iφ when λ = cos2 φ, encoding acceptance as a rotation.The reflections correspond to full selective phase shifts; the section later uses the same two-projector mechanism with small phase shifts.Source: §2.2 · p. 19

3 Oracle Separation

• The Forrelation promise problem belongs to BQPO.Proposition 3.1 presents this as the BQPO algorithmic result for Forrelation.Source: §3 · p. 19

3.1 Perfect Forrelation Pairs

• For even n, the section constructs a self-dual bent function whose pair with itself has Forrelation value 1; perfect pairs of this form require even n.The proof notes that establishing the lower bound for every even input length suffices to rule out a polynomial-query verifier.Source: §3.1 · pp. 20–21
• Flipping k truth-table bits in one function of a perfect Forrelation pair changes the Forrelation value by an additive amount linear in k.This perturbation lemma is used in the oracle-separation proof.Source: §3.1 · p. 21

3.2 Forrelation Query Lower-Bound

• For even input lengths, no QIMAO verifier for Forrelation can have both polynomial classical-query and polynomial quantum-query complexity.Theorem 3.5 states the query lower bound for the Forrelation promise problem.Source: §3.2 · pp. 22, 27

3.3 Invariance under Negligible Deviations from Exact Reflections

• For every classical oracle O, allowing negligible-distance approximations to exact-reflection units leaves QIMA^O unchanged.The companion exact reflections can replace the actual units with only negligible error, provided the stated commutation and uniformity requirements hold.Source: §3.3 · pp. 27–28

3.4 BQPO̸ ⊆QIMAO

• A classical oracle O exists for which BQP^O is not a subset of QIMA^O, although a constant-query Forrelation circuit decides the associated promise problem LO.The construction defeats every candidate QIMA^O verifier at some input length while preserving the constant-query Forrelation algorithm for LO.Source: §3.4 · p. 29

3.5 One-Query Units with Restricted Address Support

• With restricted address support k, each spectral-projector entry of a one-query unit is a multilinear polynomial of degree at most 2k in f’s truth-table values.The extended model permits one-query units that need not be reflections, while requiring all units to commute on promised oracles and allowing no trusted workspace beyond fresh Hadamard-test control qubits.Source: §3.5 · pp. 29–30
• For constant k, the query lower bound remains Ω(2^n); for k = O(log n), it is 2^n/poly(n).These bounds imply that no polynomial-query verifier in the extended model decides Forrelation under the stated address-support conditions.Source: §3.5 · p. 32
• Negligible implementation errors preserve the restricted-unit lower bound when the ideal units commute and polynomially many tested units have an inverse-polynomial completeness–soundness gap.Replacing units at operator-norm distances δj changes acceptance probability by at most 2 times the sum of the δj.Source: §3.5 · p. 32

4 Tightness of the Computational Model

• Natural relaxations of QIMAO beyond QIMAO_negl-refl collapse the model to QMAO, illustrating the tightness of the computational model.Source: §4 · p. 32

4.1 Collapse Due to Relaxing the Reflection Requirement

• Allowing inverse-polynomial deviation from the reflection requirement collapses the model to QMAO, with the containment realizable using a single oracle-containing unit.A small-phase Marriott–Watrous gadget maps the verifier’s acceptance probability monotonically to a Hadamard-test acceptance probability while suppressing improperly initialized workspace directions.Source: §4.1 · pp. 36–37

4.2 One-query Collapse Without the Reflection Requirement

• Removing the reflection requirement lets one-query-per-unit QIMAO collapse to QMAO by converting a polynomial-query verifier into a single-query unit with an inverse-polynomial acceptance gap.The cyclic-clock transformation preserves the acceptance gap up to a factor of L^2 for 0 ≤ s < c ≤ 1.Source: §4.2 · pp. 38–39
• The spectral analysis of the enlarged-register unitary shows that query reduction maps acceptance a to fL(a), shrinking acceptance gaps by at most a factor of L^2.Its eigenvalues are the Lth roots of the original unitary's eigenvalues, and the Hadamard test selects the root closest to 1.Source: §4.2 · pp. 40–41
• A QMA^O verifier can be reduced to one oracle query with an inverse-polynomial acceptance gap, yielding the one-query collapse.The starting gap is at least 1/1152, and the reduction preserves a gap of at least 1/(1152L^2); the witness also supplies the clock, and the verifier performs one Hadamard test.Source: §4.2 · p. 41

4.3 Collapse due to Enabling Ancilla Space

• One trusted active qubit makes QIMA equal QMA by enabling verification of pinned commuting Hamiltonians with an inverse-polynomial gap.Commuting positive operators are encoded as local projectors, then the trusted qubit combines those tests with initialization checks as pairwise-commuting exact reflections.Source: §4.3 · pp. 42, 45, 46
• For every classical oracle O, one trusted active qubit makes QIMAO equal QMAO, with the reverse containment realized by a single oracle-containing exact reflection.The reflection checks workspace initialization coherently; its Hadamard-test acceptance matches that of the original QMAO verifier.Source: §4.3 · pp. 46–47
• The construction preserves completeness and soundness exactly, which proves the claimed equality.Source: §4.3 · p. 47

A The Commuting Local-Hamiltonian Problem is QIMA-Complete

• The reduction encodes each term’s eigenspace choice in a label register and uses local classical constraints to check whether the labels satisfy the energy bound.The midpoint threshold allows for the total approximation error while separating the YES and NO cases.Source: A The Commuting Local-Hamiltonian… · pp. 48–49
• Commuting projectors enforce common eigenspace conditions, while diagonal constraints check the label encodings and accepting computation of the energy-checking circuit.The resulting projectors commute because the classical constraints are diagonal and the label registers are distinct.Source: A The Commuting Local-Hamiltonian… · p. 49
• The construction has ground energy 0 in the YES case and at least 1 in the NO case, yielding a reduction to a commuting local-projector Hamiltonian.A zero-energy state corresponds to a common eigenstate satisfying the energy inequality; in the NO case, the commuting-projector Hamiltonian has integer eigenvalues.Source: A The Commuting Local-Hamiltonian… · p. 50
• The commuting local-Hamiltonian problem is QIMA-complete: membership follows from the reduction, and hardness follows because commuting local projectors are a QIMA-hard special case [BH26].Under the stated gate and representation convention, the result holds up to a constant-factor increase in locality.Source: A The Commuting Local-Hamiltonian… · pp. 48, 50

B BQP Algorithm for Forrelation

• The algorithm starts at |0^n⟩, applies Hadamard transforms and phase queries to the two functions, then measures in the computational basis.The sequence is H_N, O_g, H_N, O_f, H_N.Source: B BQP Algorithm for Forrelation · p. 51
• Forrelation is in BQP, with a constant-query quantum algorithm.The algorithm is attributed to Aaronson and Ambainis.Source: B BQP Algorithm for Forrelation · p. 51
• The probability of observing 0^n is Φ(f, g)^2, at least α^2 on yes-instances and at most β^2 on no-instances.A constant number of repetitions decides the problem.Source: B BQP Algorithm for Forrelation · p. 51