{"id":"0004179f-7d06-4803-b9e0-51f10e73e649","arxiv_id":"1909.03787","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper asserts, with an unfinished proof, that deciding whether a 2-local Hamiltonian has a low-energy state preparable by a small quantum circuit is QCMA-complete.","lead":"This paper claims that the 2-Local Hamiltonian problem with a low-complexity ground state is QCMA-complete, placing it among the few complete problems for the classical-witness quantum class. The proof is a short sketch that leans on two known results, but it leaves a key soundness step unjustified.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The soundness proof for the QCMA reduction mishandles quantum superpositions of classical witnesses; QCMA's classical-witness soundness does not bound such states, and no dephasing step is supplied.","rationale":"The reader's weakest assumption is exactly the load-bearing gap. QCMA soundness is defined only over classical witnesses, while the Hamiltonian construction must control all low-complexity quantum states. The explicit M=(1/N)J verifier shows the gap is real and concrete, not a matter of missing epsilon details. The paper contains no dephasing or classicality-enforcing term, and the later remark about restricting to LC does not repair the step because the uniform superposition is low-complexity. Since the completeness reduction's soundness fails, the proof of Theorem 1 is invalid as written. The theorem might be salvageable by standard QCMA techniques, but the manuscript does not provide them. Therefore the reader's REJECT verdict is appropriate, and no verdict adjustment is needed.","tokens_in":5179,"tokens_out":8591,"duration_ms":98767,"concrete_test":"Take the verifier U defined by U|y⟩|0^n⟩ = sqrt(1−1/N)|0⟩|y⟩ + (1/sqrt(N))|1⟩|0^n⟩. For every classical y the accept probability is 1/N, so QCMA soundness is met; for |ψ⟩=|+^n⟩ the accept probability is 1. Build the paper's Hamiltonian H from this U and evaluate ⟨η|H|η⟩ on the history state built from |ψ⟩. An analytic calculation gives ⟨Hout⟩=0, ⟨Hin⟩=0, and ⟨Hprop⟩=0, so ⟨η|H|η⟩=0, contradicting the claimed λ(H)≥1/2−ε.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The soundness step of Section 2 (k-LHLC) asserts that if x is in L_no, then λ(Hout|Sin∩Sprop) ≥ 1−ε 'by the definition of QCMA.' This is false: QCMA soundness bounds only classical witnesses |y⟩, not arbitrary quantum superpositions. Let N=2^n and M=(1/N)J, where J is the all-ones matrix. M is PSD with trace 1, so it can be realized as M=V†P1V for a valid QCMA verifier. Every classical witness is accepted with probability 1/N, but the uniform superposition |+^n⟩ is accepted with probability 1. The corresponding Kempe history state lies in Sin∩Sprop, is preparable by a poly-size circuit (hence in LC), and has Hout expectation 0. Thus the claimed lower bound fails exactly at the quoted sentence. The later projection-lemma chain inherits this gap, and the text never adds a term forcing the witness register into the computational basis. This is a load-bearing error in the completeness reduction: the central claim is not established by the proof as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5553,"tokens_out":8895,"duration_ms":97387,"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":[{"comment":"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.","section":"Section 2, soundness of k-LHLC"},{"comment":"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.","section":"Section 2, note on LC notation"},{"comment":"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.","section":"Section 2, From k-LHLC to 2-LHLC"}],"minor_comments":[{"comment":"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.","section":"Section 1.1, Definition 1"},{"comment":"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.","section":"Section 2, Hamiltonian definitions"},{"comment":"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.","section":"Section 2, From k-LHLC to 2-LHLC"},{"comment":"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.","section":"Section 2, gate decomposition"}],"recommendation":"reject","confidential_remarks":"The manuscript is a short preprint whose main theorem is not established by the proof as written. The soundness gap is central and the proposed fix (e.g., adding a dephasing or classicality-enforcing term) is not present and would require substantial new analysis. In addition, the treatment of the low-complexity set as a subspace is a conceptual error that undermines the projection-lemma arguments. I do not see a path to acceptance without a major rewrite of the core proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a short course-project paper that makes a plausible claim—2-LH with Low Complexity is QCMA-complete—but does not actually prove it. The recipe is clear: take Wocjan et al.'s QCMA-completeness of 3-LH with low complexity and combine it with Kempe–Kitaev–Regev's QMA-completeness of 2-LH. The observation that the low-complexity restriction should turn the 2-LH construction into a QCMA problem is natural and, as far as I can tell, new. The author is upfront about relying on external results, and there is no self-citation or hidden parameter fitting.\n\nThe problem is in the soundness proof. The sentence 'By the definition of QCMA, if x ∈ L_no, then λ(Hout|Sin∩Sprop) ≥ 1−ε' is just wrong. QCMA soundness bounds only classical witnesses; it says nothing about quantum superpositions over the witness register. The stress-test example is decisive: a verifier can reject every classical witness with probability 1−1/N yet accept the uniform superposition with probability 1. The associated history state is in Sin∩Sprop, is preparable by a polynomial-size circuit, so it is in LC, and it makes Hout have zero expectation. The claimed lower bound fails exactly there.\n\nThere are also smaller wavering points: LC is treated as a subspace in spectral arguments, though it is not one, and the 3-to-2 local reduction is mostly delegated to [4], with the Hprop2 terms dismissed as 'similar.' These are not fatal by themselves, but they add to the sketch-like character.\n\nThe theorem may well be salvageable—a dephasing step and a careful invocation of the known reduction could probably fix it. But as written, the proof does not support the theorem. I would not cite this as a proof, though I might mention the statement as a plausible corollary in a footnote. The reader who gets value here is someone looking for QCMA-complete problems and willing to redo the details themselves.\n\nIf I were an editor, I would send this to a referee only to check whether the gap is repairable, but I would expect heavy revision. For a journal, I'd lean desk reject unless the author fixes the soundness step and fills in the missing reduction.","headline":"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.","tokens_in":5980,"tokens_out":3689,"would_cite":false,"duration_ms":38660,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q15","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adding a low-complexity condition to the 2-local Hamiltonian problem makes it QCMA-complete.","keywords":["2-local Hamiltonian","QCMA","QMA-complete","low complexity states","history state construction","projection lemma","quantum Merlin-Arthur games","locality reduction"],"falsifier":"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.","tokens_in":4938,"feed_emoji":"⚛️","tokens_out":13520,"duration_ms":133723,"temperature":0.7,"pith_summary":"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.","feed_headline":"Low-complexity witness makes 2-LH problem QCMA-complete","feed_subtitle":"Adding a low-complexity condition to the 2-local Hamiltonian problem yields a complete problem for QCMA.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the history-state Hamiltonian, the projection lemma, and the locality-reduction technique that the proof adapts from the QMA-completeness of 2-LH.","marker":"[4]"},{"why":"Introduced the low-complexity constraint and established QCMA-completeness of 3-LHLC, the result this paper extends to 2-local terms.","marker":"[6]"}],"fun_headline_variants":["Low-complexity 2-LH: QCMA-complete","2-LH with low complexity is QCMA-complete","Low complexity makes 2-LH QCMA-complete","2-local low-complexity Hamiltonians are QCMA-complete","QCMA-complete for 2-LH with low complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Low-complexity 2-LH: QCMA-complete","2-LH with low complexity is QCMA-complete","Low complexity makes 2-LH QCMA-complete","2-local low-complexity Hamiltonians are QCMA-complete","QCMA-complete for 2-LH with low complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002169,"raw_usage":{"total_tokens":8361,"prompt_tokens":855,"completion_tokens":7506,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":7420}},"tokens_in":471,"tokens_out":7506,"duration_ms":58189,"temperature":1.0,"reasoning_tokens":7420,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:44:23.292282+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Kempe, A","cited_arxiv_id":null,"evidence_quote":"Supplies the history-state Hamiltonian, the projection lemma, and the locality-reduction technique that the proof adapts from the QMA-completeness of 2-LH."},{"cited_title":"Wocjan, D","cited_arxiv_id":null,"evidence_quote":"Introduced the low-complexity constraint and established QCMA-completeness of 3-LHLC, the result this paper extends to 2-local terms."}],"review_version":1}