Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

2-Local Hamiltonian with Low Complexity is QCMA

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adding a low-complexity condition to the 2-local Hamiltonian problem makes it QCMA-complete.

desk verdict Plausible but unproven: the soundness step confuses classical and quantum witnesses, so the paper fails as written; the statement is likely true as a corollary. read the letter →

arxiv 1909.03787 v1 pith:PVYETCLJ submitted 2019-09-06 cs.CC quant-ph

Ying-hao Chen This is my paper · ORCID
classification cs.CCquant-ph MSC 68Q1268Q1581P68
keywords 2-localHamiltonianQCMAQMA-completelowcomplexitystateshistorystateconstructionprojectionlemmaquantumMerlin-Arthurgameslocalityreduction
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that the 2-Local Hamiltonian with Low Complexity problem (2-LHLC) is QCMA-complete, where QCMA is the class of problems verifiable by a quantum verifier given a classical witness. Given a 2-local Hamiltonian $H$, the problem asks whether some state preparable by a polynomial-size circuit has energy at most $\varepsilon$, or whether every such low-complexity state has energy at least $1/2 - \varepsilon$. The proof adds the low-complexity constraint to the QMA-complete 2-local Hamiltonian problem, which turns the witness into a classical description of a preparing circuit, and then adapts the standard history-state construction to show every QCMA problem reduces to this form. If the argument is right, 2-LHLC becomes a natural complete problem for QCMA, a class with few known complete problems, and a concrete setting in which classical witnesses suffice for low-energy states of 2-local Hamiltonians.

What carries the argument

The machinery is the history-state Hamiltonian from the 2-LH QMA-completeness construction, together with the projection lemma. A history state encodes the full evolution of the verifier over time with an additional clock register, and the Hamiltonian penalizes invalid inputs, invalid clock behaviour, and mismatches between adjacent time steps, so that low-energy states must follow the verified computation. The projection lemma, a bound relating the ground energy of a sum of Hamiltonians to the ground energy of one part restricted to the zero eigenspace of the penalty terms, is what converts the verifier's acceptance and rejection behaviour into an energy gap. Two adjustments make the terms 2-local: the clock is written in unary with pairwise consistency penalties, and the non-2-local controlled-phase gates are decomposed into sequences of gates with preceding and following single-qubit $Z$ rotations, so that propagation can be checked by local comparisons between nearby clock positions.

What would settle it

Construct a QCMA verifier whose maximum acceptance probability over classical witnesses is at most $\varepsilon$ but which accepts some superposition of witness states with probability at least $1-\varepsilon$; feeding it into the paper's reduction would produce a 2-local Hamiltonian with a low-energy low-complexity state in a no-instance, refuting the claimed soundness gap. Such a verifier could be checked by computing acceptance probabilities on all classical strings and on the chosen superposition.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1, is that 2-LHLC is QCMA-complete: the promise problem of distinguishing a Hamiltonian with a low-energy low-complexity state from one whose low-complexity states all have energy at least $1/2 - \varepsilon$ is exactly the complete problem for QCMA. The containment in QCMA is direct, since a yes-instance is witnessed by a polynomial-size circuit description that a quantum verifier can execute. Hardness comes from encoding an arbitrary QCMA verifier as a 2-local Hamiltonian whose low-energy low-complexity states are the accepting history states of the verifier: on yes-instances the construction gives energy $\leq \varepsilon$, and on no-instances repeated use of the projection lemma forces all low-complexity states to have energy at least $1/2 - \varepsilon$. To reduce the locality from logarithmic to two, the clock is stored in unary with clock-consistency penalties, and each controlled-phase gate is expanded into a short sequence of gates that can be checked by pairwise 2-local comparisons.

Load-bearing premise

The load-bearing premise is that a QCMA verifier that rejects every classical witness also rejects every quantum state on the witness register, so the constructed output Hamiltonian has high energy on all valid low-complexity states; QCMA's definition only guarantees rejection of classical witnesses, and the paper does not prove the stronger quantum rejection property.

Editorial extensions

If this is right

  • 2-LHLC belongs to QCMA, so restricting the witness of a QMA-complete problem to low-complexity states moves it into QCMA while keeping it complete for that class.
  • Every QCMA problem can be reduced to deciding the minimum energy, over low-complexity states, of a 2-local Hamiltonian, giving an energy-optimization characterization of QCMA.
  • The paper's reduction works for logarithmic-locality and then for 2-locality; combining both steps shows that the low-complexity constraint, rather than the locality parameter, is what makes the problem QCMA-complete.
  • Since unrestricted 2-LH is QMA-complete, the low-complexity constraint is a concrete separation handle: any algorithm for 2-LHLC would solve all of QCMA.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • As written, the soundness proof assumes a QCMA verifier rejects every quantum state on the witness register, not only classical strings; if that stronger property cannot be proved, the reduction needs an explicit dephasing or classicality-enforcing step.
  • Replacing polynomial-size circuits by other circuit-size bounds, such as constant, logarithmic, or polynomial, would define a family of restricted Hamiltonian problems whose complexity plausibly interpolates between NP and QMA; the paper does not explore this interpolation.
  • The gate-decomposition trick used to lower locality from 3 to 2 seems reusable in other history-state constructions whenever a Hamiltonian term depends on a gate that is not itself of low locality.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper claims to prove that the 2-Local Hamiltonian with Low Complexity (2-LHLC) problem is QCMA-complete. The argument has three parts: first, it asserts that every k-LHLC problem is in QCMA because a classical witness can describe the circuit preparing a low-complexity state; second, it claims QCMA-hardness for k-LHLC with k=O(log n) by adapting the Kempe-Kitaev-Regev Hamiltonian construction and applying the projection lemma; third, it sketches a reduction from 3-LHLC to 2-LHLC using a unary clock, a clock-validity constraint, and pairwise propagation constraints, again invoking the projection lemma. The proof is presented as a straightforward combination of the QMA-completeness of 2-LH and the QCMA-completeness of 3-LH with low complexity.

Significance. If the main theorem were established, it would add a natural QCMA-complete problem and sharpen the known landscape of QCMA versus QMA. The approach of combining existing QMA-hard constructions with a low-complexity restriction is attractive, and the claimed result is plausible. However, the correctness of the proof is not established: the central soundness step is false as stated, and the manuscript uses the set of low-complexity states as if it were a subspace, which is undefined. The paper provides no machine-checked proofs, no numerical verification, and no new technical tool beyond reference to prior work; its significance therefore rests entirely on the validity of the reduction, which is not demonstrated.

major comments (3)
  1. [Section 2, soundness of k-LHLC] The sentence 'By the definition of QCMA, if x in L_no, then lambda(Hout|Sin intersect Sprop) >= 1 - epsilon' is false. Definition 1 gives soundness only for classical witnesses |y> in {0,1}^{nx}; it does not bound the acceptance probability of a quantum superposition on the witness register. Concretely, let N=2^{nx} and let M=(1/N)J, where J is the all-ones matrix. M is a valid POVM element and can be implemented by a quantum circuit. For every classical y, the acceptance probability is 1/N <= epsilon, so the QCMA soundness condition holds, but the uniform superposition |+^{nx}> is accepted with probability 1. The corresponding history state lies in Sin intersect Sprop, is preparable by a polynomial-size circuit (hence belongs to LC), and has Hout expectation 0. Thus the claimed lower bound fails at exactly this step. The later remark that lambda(.) should be restricted to LC does not repair the argument because |+^{nx}> itself is a low-complexity state.
  2. [Section 2, note on LC notation] The proof writes 'we should write lambda(Hout|LC intersect Sin intersect Sprop) - 2/8 <= lambda(H|LC)' and then says it ignores the LC constraint 'for simplicity'. This is not a harmless simplification: LC is not a subspace. The set of states preparable by polynomial-size circuits is not closed under linear combinations, so expressions such as lambda(H|LC) are not defined as eigenvalue problems, and the projection lemma cannot be applied to the minimum over a non-subspace set. The soundness argument needs a separate argument showing that the low-energy states (or the restricted minimum over LC) inherit the lower bound obtained for the full Hilbert space; no such argument is given.
  3. [Section 2, From k-LHLC to 2-LHLC] The reduction from k-LHLC to 2-LHLC is only sketched, and several steps that are load-bearing for the claimed 2-locality are delegated to reference [4] without adaptation to the low-complexity constraint. In particular, the sentence 'The elimination of Jprop2Hprop2 is not exactly the same as with other hamiltonians, but the results are similar' leaves unproved the key spectral behavior of the pairwise constraints Hqubit and Htime. The chain of inequalities ending with '>= lambda(Hout|Sclock intersect Sprop1 intersect Sprop intersect Sin) - 4/8' also silently drops the LC restriction throughout, inheriting the flaw from the k-LHLC soundness proof. A complete proof must show that the added clock and propagation terms preserve both the low-complexity property of the YES witness and the soundness against arbitrary low-complexity states; the current text does neither.
minor comments (4)
  1. [Section 1.1, Definition 1] The condition 'Fix epsilon = epsilon(|x|) s.t. 2^{Omega(|x|)} <= epsilon <= 1/3' appears to have the exponent direction wrong; standard QCMA allows an inverse-exponential or constant soundness error, not an exponentially large one.
  2. [Section 2, Hamiltonian definitions] In the definitions of Hin and Hprop, the clock-qubit subscripts are frequently omitted or ambiguous (e.g., '|0><0|' without a qubit index), making the locality claims difficult to verify as written.
  3. [Section 2, From k-LHLC to 2-LHLC] The phrase 'we just need 1 qubit to keep the clock' is confusing because the construction immediately uses T qubits in unary representation; the intended meaning is likely 'one-hot' rather than a single qubit.
  4. [Section 2, gate decomposition] The identity Cphi = (Z tensor I)(I tensor Z)Cphi(I tensor Z)(Z tensor I) is not a decomposition into elementary gates that removes Cphi; the text should explain how this identity, together with the time constraints, reduces the locality of the term Ut tensor |1><0|_t from 3-local to 2-local.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is a standard reduction built on external QCMA/QMA-completeness results, with an acknowledged soundness gap that is not circular.

full rationale

The paper's central claim, that 2-LHLC is QCMA-complete, is assembled from two external results: Wocjan, Janzing, and Beth's QCMA-completeness of 3-LH with low complexity [6] and Kempe, Kitaev, and Regev's QMA-completeness of 2-LH [4]. These are not self-citations, and using them as premises of a reduction is not circular. The local-Hamiltonian construction and the projection lemma are quoted from [4] and applied to the low-complexity variant; the proof does not define its target quantity in terms of its own conclusion, nor does it fit any parameter and rename the fit a prediction. The only serious issue is the soundness sentence in Section 2: 'By the definition of QCMA, if x ∈ L_no, then λ(Hout|Sin∩Sprop) ≥ 1 − ε.' Definition 1 only guarantees soundness for classical witnesses |y⟩ ∈ {0,1}^{n_x}, not for arbitrary quantum states in Sin∩Sprop, so this inference is a correctness gap rather than a circular one. The paper itself notes the relevant simplification: 'Note that we should write λ(Hout|LC ∩ Sin ∩ Sprop) − 2/8 ≤ λ(H|LC). For simplicity, we ignore the notation for low complexity constraint LC while writing λ(·).' That simplification underscores the gap but does not make the derivation circular, because the claimed bound is not already assumed in the input; it is left unproved. Accordingly, no circular step is present, and the score is 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on two cited completeness theorems, the projection lemma, and two unstated assumptions: dephasing robustness and subspace treatment of LC. The construction parameters J are free and unspecified. No new physical entities are introduced.

free parameters (1)
  • J_in, J_prop, J_clock, J1, J2 = not specified
    The projection lemma requires choosing these large enough to separate subspaces, but the paper never fixes their values or proves the resulting spectral gap and polynomial bounds. The reduction's soundness depends on these choices.
assumptions (5)
  • domain assumption QCMA-completeness of 3-LH with Low Complexity (Wocjan et al. [6])
    Used as the starting point for hardness; the paper does not re-prove it.
  • domain assumption QMA-completeness of 2-LH (Kempe, Kitaev, Regev [4])
    Used to import the 2-local Kempe construction and projection lemma.
  • standard math Projection Lemma from [4]
    Invoked multiple times to lower-bound eigenvalues of sums of Hamiltonians; stated without proof.
  • ad hoc to paper Unstated: QCMA verifier can be made robust to quantum superpositions of witnesses
    The soundness step requires that rejection of all classical witnesses implies rejection of all quantum states; this is false as stated and no dephasing transformation is supplied.
  • ad hoc to paper LC is treated as a subspace in spectral arguments
    Expressions like lambda(H|LC) and the projection lemma are applied to the non-subspace set of low-complexity states, which is mathematically invalid.

how reviews work

0 comments
Cite this review

Pith. "Pith review of 2-Local Hamiltonian with Low Complexity is QCMA." pith.science (2026). https://pith.science/paper/PVYETCLJ

@misc{pith2026190903787,
  author       = {Pith},
  title        = {Pith review of: 2-Local Hamiltonian with Low Complexity is QCMA},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PVYETCLJ}},
  note         = {Machine review of arXiv:1909.03787}
}
read the original abstract

We prove that 2-Local Hamiltonian (2-LH) with Low Complexity problem is QCMA-complete by combining the results from the QMA-completeness[4] of 2-LH and QCMA-completeness of 3-LH with Low Complexity[6]. The idea is straightforward. It has been known that 2-LH is QMA-complete. By putting a low complexity constraint on the input state, we make the problem QCMA. Finally, we use similar arguments as in [4] to show that all QCMA problems can be reduced to our proposed problem.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

    quant-ph 2025-06 conditional novelty 8.0 of 10

    New QSAT variants on qubits and qudits are complete for BQP_1, coRP, QCMA and six PI/SoPU classes, implying any classification of strong quantum CSPs must contain at least 13 classes unless some collapse.

Reference graph

Works this paper leans on

6 extracted references · 5 canonical work pages · cited by 1 Pith paper

  1. [4]

    Kempe, A

    J. Kempe, A. Kitaev, and O. Regev. The complexity of the lo cal hamiltonian problem. SIAM Journal on Computing , 35(5):1070–1097, 2006

    work page 2006

  2. [1]

    Aaronson and G

    S. Aaronson and G. Kuperberg. Quantum versus classical p roofs and advice. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07 ), pages 115–128. IEEE, 2007

    work page 2007

  3. [2]

    Babai and S

    L. Babai and S. Moran. Arthur-merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences , 36(2):254–276, 1988

    work page 1988

  4. [3]

    Kempe and O

    J. Kempe and O. Regev. 3-local hamiltonian is qma-comple te. arXiv preprint quant-ph/0302079, 2003

    arXiv 2003

  5. [5]

    A. Y. Kitaev, A. Shen, M. N. Vyalyi, and M. N. Vyalyi. Classical and quantum computation . Number 47. American Mathematical Soc., 2002

    work page 2002

  6. [6]

    Wocjan, D

    P. Wocjan, D. Janzing, and T. Beth. Two qcma-complete pro blems. arXiv preprint quant- ph/0305090, 2003. 7

    work page arXiv 2003

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.