{"id":"189b8b67-1abd-4f2d-9fff-bcfe0380cc9f","arxiv_id":"2506.15551","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"With an infinite counter register as part of the witness, QMA and its perfect-completeness variant QMA_1 become the same complexity class, and a finite truncation gives doubly-exponential completeness amplification.","lead":"This paper proves that two versions of quantum Merlin-Arthur proofs, one where the verifier must always accept correct answers and one where it may occasionally err, become equal if the verifier is given an infinite counter register that can only count upward. The result also yields a new way to amplify quantum proofs that pushes the completeness error down doubly-exponentially small with very few extra operations.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.2 contains a false fidelity identity; the truncation proof needs correction, but the central claim survives with a constant factor.","rationale":"The paper's central claim is QMA = QMA^∞_1, with the reverse inclusion resting on Lemma 5.2. The reader's verdict is CONDITIONAL, citing patchable bounds and the one-way counter in Lemma 5.2 as the weakest assumption. My independent check found a more precise, concrete invalid step in that same lemma: the fidelity identity used to bound the distance between an arbitrary witness and its truncated approximation is false. This is a genuine error in the written proof of a load-bearing lemma. However, the error is localized and repairable: aligning phases of the orthogonal block approximations gives F(w,\\tilde w) ≥ Σ_j β_j F(θ_j,\\tilde θ_j), which changes the trace-distance bound by only a factor of √2 and preserves the asymptotic completeness loss c − O(√(2^{−m}ℓ)). The other questionable point in the same lemma, the use of a controlled R0 for shift-invariance, is also repairable because the zero-check gates of the QMA^∞ model act trivially on all states supported on d ≥ 1. No circularity, fraud, or fatal flaw was found. The main theorems therefore remain credible conditional on correcting these bounds. Since the reader's CONDITIONAL verdict already anticipates such technical corrections, my read does not change the verdict, but it sharpens the specific defect that should be fixed.","tokens_in":21641,"tokens_out":24035,"duration_ms":220988,"concrete_test":"Take the two-component example from Lemma 5.2: two blocks with β_1 = β_2 = 1/2, F(θ_1,\\tilde θ_1)=0, and F(θ_2,\\tilde θ_2)=1. Evaluate both sides of the asserted identity F(w,\\tilde w)² = Σ_j β_j F(θ_j,\\tilde θ_j)²: the right side is 1/2 while the actual fidelity squared is 1/4. Then replace Eq. (14) with the correct phase-aligned inequality F(w,\\tilde w) ≥ Σ_j β_j F(θ_j,\\tilde θ_j) and re-derive the completeness loss in Lemma 5.2. If the final bound remains c − O(√(ℓ/2^m)) up to an absolute constant, the central theorem is unaffected; if the loss is worse than any O(√(ℓ/2^m)) term, the truncation proof requires a new argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing defect is in the proof of Lemma 5.2, which is the key step showing QMA^∞ ⊆ QMA. In constructing the approximated witness |\\tilde w⟩ = Σ_j √β_j |\\tilde θ_j⟩ from orthogonal block states, the proof asserts the fidelity identity F(w,\\tilde w)² = Σ_j β_j F(θ_j,\\tilde θ_j)² (near Eq. 14). This equality is false. For orthogonal blocks, F(w,\\tilde w) = |Σ_j β_j ⟨θ_j|\\tilde θ_j⟩|; after choosing the phases of |\\tilde θ_j⟩ so all overlaps are nonnegative, this equals Σ_j β_j F(θ_j,\\tilde θ_j), whose square is generally smaller than Σ_j β_j F(θ_j,\\tilde θ_j)². A two-block example with equal weights and fidelities 0 and 1 gives claimed F² = 1/2 but actual F² = 1/4. Thus the displayed trace-distance bound T(w,\\tilde w) ≤ √(ℓ/(2^{m−3}−ℓ)) is not justified as written. With the corrected inequality, T(w,\\tilde w) ≤ √(2ℓ/(2^{m−3}−ℓ)), which still yields the needed completeness loss c − O(√(2^{−m}ℓ)) up to an absolute constant. The same lemma also phrases shift-invariance through a controlled R0 operation, although the general QMA^∞ gate set uses zero-checks; for states supported on d ≥ 1 those checks are inert, so this is repairable. The reader correctly identified Lemma 5.2 as delicate; the false fidelity identity is the precise broken step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces QMA^∞ and QMA_1^∞, variants of QMA in which the verifier can act on an additional infinite-dimensional counter register B with basis {|d⟩ : d∈N}, supporting controlled increments and zero-checks. It claims (Theorems 1.1 and 1.2) that QMA = QMA^∞ = QMA_1^∞, i.e., adding the counter does not increase the power of QMA but does make perfect completeness achievable. Two purification constructions are given in Section 4, the second of which works for any verifier with completeness c>1/4 and soundness s<1/4. Truncating the counter in Section 5 yields a QMA amplifier with completeness 1−2^{−q} using O(1) calls to V and V† and O(log q) overhead, leading to Theorem 1.3: QMA = QMA(1−2^{−2^r}, 2^{−r}). Section 6 contains the truncation lemma that is the key step for showing QMA^∞ ⊆ QMA. Overall, the paper argues that an infinite one-way counter is a natural, physically motivated model in which perfect completeness for QMA can be proven, and that the counter can be truncated back to the standard finite model at the cost of doubly-exponentially small completeness error.","tokens_in":21908,"tokens_out":20502,"duration_ms":198540,"significance":"If the proofs are brought to a fully correct state, this is a substantial contribution to the QMA vs. QMA_1 problem. The result that an infinite counter does not add power to QMA, while enabling perfect completeness, is a genuine structural statement about an infinite-dimensional proof system, and the finite amplifier is interesting in its own right because it improves completeness with only O(1) calls to the original verifier and O(log q) overhead. The paper is careful in several respects: Lemma 2.2 is proved in-line rather than cited, the block-diagonalization argument in Theorem 4.4 is explicit, and Table 1 gives a concrete resource comparison with prior amplifiers. The errors identified below are localized and repairable; they do not appear to invalidate the main conceptual claims.","major_comments":[{"comment":"The displayed identity F(w, \\tilde w)^2 = \\sum_j \\beta_j F(\\theta_j, \\tilde\\theta_j)^2 is false. Because the blocks are orthogonal, F(w, \\tilde w) = |\\sum_j \\beta_j \\langle\\theta_j|\\tilde\\theta_j\\rangle|, and after choosing the phases of |\\tilde\\theta_j\\rangle so that all overlaps are nonnegative this equals \\sum_j \\beta_j F(\\theta_j, \\tilde\\theta_j); its square is generally smaller than \\sum_j \\beta_j F(\\theta_j, \\tilde\\theta_j)^2. For example, with two blocks of equal weight and fidelities 0 and 1, the displayed formula gives F^2 = 1/2 while the actual fidelity squared is 1/4. The trace-distance bound T(w, \\tilde w) ≤ \\sqrt{\\ell/(2^{m-3}-\\ell)} is therefore not justified as written. The bound is repairable: since each F(\\theta_j, \\tilde\\theta_j) ≥ \\sqrt{1-\\ell/(2^{m-3}-\\ell)}, one directly obtains F(w, \\tilde w) ≥ \\sqrt{1-\\ell/(2^{m-3}-\\ell)} and hence T(w, \\tilde w) ≤ \\sqrt{\\ell/(2^{m-3}-\\ell)}; however, Eq. (14) and the sentence introducing it must be rewritten with the correct identity and a valid chain of inequalities.","section":"Section 6, proof of Lemma 5.2, displayed equation (14)"},{"comment":"The reduction 'without loss of generality ... c and s are centered around 1/4' is not valid for all (c,s) allowed in the statement. A probabilistic mix maps (c,s) to (λ+(1−λ−μ)c, λ+(1−λ−μ)s), and centering the new parameters around 1/4 forces the new gap to be η(c−s) for some η≤1, not necessarily η=1; in particular, δ=(c−s)/2 does not follow for large gaps, such as the verifiers with c≈1 and s≈0 used in the proof of Theorem 1.3. Moreover, the inequality |γ|≤|(1/2−2δ)/(1/2+2δ)| fails when the optimal acceptance probability p exceeds 1/2, and the subsequent simplification to |(1−4δ)/(1/2+2δ)| is an algebra error: (1/2−2δ)/(1/2+2δ) = (1−4δ)/(1+4δ). Since this bound feeds directly into the choice D=Θ(q/δ) and the completeness estimate 1−e^{−4δ(D−1)}, the proof of Proposition 5.3, and hence of Theorem 1.3, needs a corrected case analysis that separates p≤1/2 from p>1/2 and tracks the actual gap of the centered verifier.","section":"Section 5, proof of Proposition 5.3"},{"comment":"The proof asserts that for components supported on d≥1, 'the controlled R0 is applied deterministically,' and uses this to conclude that ∥|ξ_i⟩∥^2 is invariant under shifting the counter. However, the general QMA^∞ gate set defined in Section 3 contains only controlled increments and zero-checks; R0 is a component of the particular verifier constructed in Section 4.2, not of an arbitrary QMA^∞ verifier. The intended argument is that for supports lying entirely at d≥1 all zero-checks are inert, so any circuit built from increments and zero-checks is shift-invariant; this should be stated and proved for arbitrary V instead of relying on R0. As written, the proof of Lemma 5.2 is specialized to the verifier from Section 4.2, while the lemma is stated and used for arbitrary QMA^∞ verifiers in Corollary 6.2.","section":"Section 6, proof of Lemma 5.2, paragraph after Eq. (15)"}],"minor_comments":[{"comment":"The displayed equality T(\\tilde\\psi, \\psi) = \\gamma^{D-1} should read |\\gamma|^{D-1}, since γ may be negative; the subsequent bound should use the absolute value.","section":"Section 5, proof of Proposition 5.3"},{"comment":"The sentence 'there exists an approximation |\\tilde w⟩ of |w⟩ such that N consists of infinitely many intervals' should refer to the support of |\\tilde w⟩, not to 'N'; this is a typographical slip that makes the interval construction harder to follow.","section":"Section 6, proof of Lemma 5.2"},{"comment":"The abstract's phrase 'O(log q) other gates' could be misread as a strict gate count; Proposition 5.3 states t'_A = O(t_A + log(q/(c−s))), so the abstract should say 'O(log q) additional gates beyond those of the original verifier' to avoid suggesting an absolute bound independent of t_A.","section":"Abstract and Section 5"},{"comment":"The circuit implementing the measurement Q uses labels H and z without explanation; a one-sentence description of the Hadamard/zero-check decomposition would improve readability.","section":"Section 4.1, circuit after Eq. (4)"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the two main errors are localized in the proofs of Lemma 5.2 and Proposition 5.3 and are repairable without changing the main theorems. The false fidelity identity in Eq. (14) can be replaced by a direct inequality, and the WLOG centering in Proposition 5.3 needs a genuine case analysis. The contribution is strong enough to warrant a careful revision; I would not accept the paper in its current form because Theorem 1.3 currently rests on an invalid reduction. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid paper with a genuinely new idea, and the two technical bugs I found are patchable; the main theorems stand. The infinite-counter model is a real contribution: it gives a clean way around the obstruction that makes QMA vs QMA1 hard, and the doubly-exponential completeness amplifier is a concrete payoff.\n\nWhat is actually new: the definition of QMA∞ and QMA∞_1 with a one-way counter, the purification construction that yields perfect completeness, and the truncation argument that both removes the counter (QMA=QMA∞) and produces a finite QMA amplifier with completeness error 2^{-2^r}. The proofs are mostly self-contained; having the Marriott-Watrous rewinding lemma proved in place is helpful. The block-diagonalization argument in Theorem 4.4 is sound, and the comparisons with prior amplifiers in Table 1 are honest.\n\nSoft spots, in proportion. The proof of Lemma 5.2, the load-bearing step for QMA∞⊆QMA, states a false equality: F(w,tilde w)^2 is not Σ β_j F(θ_j,tilde θ_j)^2. The correct identity is F(w,tilde w)=Σ β_j F(θ_j,tilde θ_j) (with phases chosen so the overlaps are nonnegative), and the squared version is smaller, not larger. The stress-test worries this costs a constant factor, but I think the bound survives exactly: since each F_j is at least sqrt(1-ℓ/(2^{m-3}-ℓ)), the weighted average is too, so T(w,tilde w)≤sqrt(ℓ/(2^{m-3}-ℓ)) follows directly. The displayed line needs rewriting, but the lemma is true.\n\nThe other issue is in Proposition 5.3: the bound |γ|≤|1−4δ| is not valid for p close to 1 when δ>1/8. The true envelope is max(|1−4δ|/(1+4δ),1/2), which still gives exponential decay, with a mildly worse constant. A referee should ask for this to be fixed, not for a new proof.\n\nThe gate-set caveat on Theorem 1.3 is the authors' own, and it is real; the result is for a gate set with exact inverses, controlled increments, and controlled reflections. That is a boundary, not a flaw.\n\nCitation and attribution look right. [BJ25] is cited for the purification technique, and the new application is distinct. I saw no fitted parameters and no circularity.\n\nVerdict: this deserves a serious referee. I would take it to reading group and would cite it; I expect it to become standard in the QMA1 story.","headline":"A real step toward QMA=QMA1 via an infinite counter; two small technical bugs in the truncation lemmas, both repairable.","tokens_in":22538,"tokens_out":7608,"would_cite":true,"duration_ms":69072,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"With an infinite counter, QMA gains perfect completeness.","keywords":["QMA","QMA1","perfect completeness","infinite counter","quantum Merlin-Arthur games","quantum error amplification","quantum complexity classes","bosonic quantum computing"],"falsifier":"Run the $D$-level truncation of the Section 4.2 verifier on an instance whose optimal witness has acceptance probability $p = 1/2 + \\delta$, using the geometric counter witness: if the measured acceptance probability falls below $1 - \\gamma^{D-1}$ by more than the trace-distance error $O(\\sqrt{2^{-m}\\ell})$ for large $D$, the completeness analysis behind Theorem 1.3 is wrong.","tokens_in":21369,"feed_emoji":"♾️","tokens_out":8613,"duration_ms":86245,"temperature":0.7,"pith_summary":"This paper addresses the long-standing question of whether QMA, the quantum analogue of NP, equals QMA1, its version with perfect completeness. It proves that the two classes coincide if the verifier is allowed a one-way infinite counter: a register with basis states $|d\\rangle$ for $d\\in\\mathbb{N}$ on which it can perform controlled increments and test whether $d=0$. In this model, ${\\sf QMA} = {\\sf QMA}^{\\infty}_1$ and also ${\\sf QMA} = {\\sf QMA}^{\\infty}$, so the infinite register adds no power to QMA but does make perfect completeness achievable. Truncating the construction back to finite dimensions yields a QMA amplifier that drives completeness doubly exponentially close to 1 while using only $O(1)$ calls to the original verifier, proving ${\\sf QMA} = {\\sf QMA}(1-2^{-2^r}, 2^{-r})$ for any polynomial $r$.","feed_headline":"QMA equals QMA1 when verifiers get an unlimited counter","feed_subtitle":"An infinite one-way register is computationally harmless yet makes perfect completeness achievable, partially settling the question.","key_machinery":"The load-bearing object is the \"purification circuit\" built from the original verifier: apply $V$, then a controlled increment on the counter, then a reflection $R_0 = 2|0\\rangle\\langle 0|_A - I$ on the ancilla, then $V^\\dagger$. The geometric counter witness $|\\psi\\rangle_B = (1-\\gamma^2)^{1/2}\\sum_{d=0}^\\infty \\gamma^d |d\\rangle$ with $\\gamma = 1 - 1/(2p)$ is tuned so that the amplitude of the rejecting term vanishes exactly, yielding acceptance probability 1. For the converse, the key mechanism is an interval-truncation lemma: divide the counter line into blocks of size $2^{m-3}$, excise one length-$\\ell$ gap from each block, and re-weight the witness; because every increment moves states strictly rightwards by one, the forward-evolved images of pieces supported on separated intervals are orthogonal, letting the acceptance probability pass through the truncation with only $O(\\sqrt{\\smash{2^{-m}}\\ell})$ loss. This is the argument that makes ${\\sf QMA}^{\\infty} \\subseteq {\\sf QMA}$.","core_discovery":"The central claim is equality of the three classes ${\\sf QMA}$, ${\\sf QMA}^{\\infty}$ and ${\\sf QMA}^{\\infty}_1$, where ${\\sf QMA}^{\\infty}_1$ is QMA with perfect completeness and verifiers equipped with an infinite counter register $B$ with basis $\\{|d\\rangle : d\\in\\mathbb{N}\\}$, a controlled increment isometry $[+1]: |d\\rangle \\mapsto |d+1\\rangle$, and a check for $d=0$. The forward direction is constructive: any QMA verifier is \"purified\" by composing $V$ with a controlled increment and $V^\\dagger$, so that a witness with geometrically decaying counter amplitudes, $|\\psi\\rangle_B \\propto \\sum_d \\gamma^d |d\\rangle$ with $\\gamma = 1 - 1/(2p)$, cancels the rejecting branch exactly whenever the original acceptance probability $p$ exceeds $1/4$. The reverse direction shows the infinite register is superfluous for two-sided error: after a verifier uses at most $\\ell$ increments, every witness can be approximated, with controlled fidelity loss, by a witness supported on short separated intervals of counter values, and the one-way nature of the increment keeps the evolved components orthogonal. Together these give ${\\sf QMA} = {\\sf QMA}^{\\infty}_1$ and ${\\sf QMA} = {\\sf QMA}^{\\infty}$. A finite truncation of the same construction yields Theorem 1.3: any QMA problem has a verifier with completeness $1-2^{-q}$ using $O(1)$ calls to the original verifier and its inverse and $O(\\log q)$ extra gates.","pith_inferences":["Beyond the paper's stated results, the same purification idea is portable: it should turn any bounded-error quantum verification procedure with a promise gap into a zero-error verification procedure in a model augmented by a one-way counter, so analogous equalities may hold for QCMA or for bounded-energy bosonic QMA variants if the counter can be realized physically.","Because the proof of ${\\sf QMA}^{\\infty} \\subseteq {\\sf QMA}$ leans on the one-wayness of the increment, a natural strengthening is to make the counter unitary (increment and decrement on $\\mathbb{Z}$) and check whether the truncation lemma survives; Remark 6.3 suggests it should, but a full treatment would settle whether the model can be made reversible at no cost.","The gate-set conditions in Theorem 1.3, exact inverses and exact controlled increments, suggest that doubly-exponential completeness may itself be gate-set dependent; if so, the infinite-counter statement, not the finite truncation, is the gate-set-independent formulation of QMA1."],"forward_implications":["QMA and QMA1 are equal in the infinite-counter model, so the gap between two-sided and one-sided quantum Merlin–Arthur is not an obstruction that survives the addition of a one-way counter.","An infinite counter is computationally harmless for QMA: ${\\sf QMA}^{\\infty} = {\\sf QMA}$, meaning the class gains no languages from the infinite-dimensional register, only the ability to achieve perfect completeness.","Truncation gives a QMA amplifier that improves completeness to $1-2^{-q}$ with $O(1)$ verifier calls and $O(\\log q)$ other gates, and consequently ${\\sf QMA} = {\\sf QMA}(1-2^{-2^r}, 2^{-r})$ for every polynomial $r$, improving exponential closeness to doubly exponential.","In the infinite-counter model, error reduction holds in the same parameters as ordinary QMA: ${\\sf QMA}^{\\infty}_1 = {\\sf QMA}^{\\infty}(1, 1-1/r) = {\\sf QMA}^{\\infty}(1, 2^{-r})$ for any polynomial $r$.","As a corollary, a wider class of promise problems with doubly exponentially small completeness error, such as k-SAT variants, become QMA-hard."],"supporting_citations":[{"why":"Supplies the perfect-transducer construction that the purification protocol adapts, allowing composition without log factors.","marker":"[BJ25]"},{"why":"Provides Lemma 2.2, the eigenvector decomposition of the verifier and quantum rewinding used in both completeness-purifying circuits.","marker":"[MW05]"},{"why":"Gives the quantum oracle separation of QMA from QMA1 in finite dimensions that the infinite-counter model bypasses.","marker":"[Aar09]"},{"why":"Is the probability-truncation amplifier to which the new amplifier is compared and whose Proposition 18 bounds the soundness of that approach.","marker":"[KLGN13]"},{"why":"Provides prior QMA amplification work that also exploits exact acceptance probability and forms part of the comparison in Section 5.","marker":"[NWZ09]"},{"why":"Is the previous best amplifier whose resource usage the table compares against the new construction.","marker":"[FKYYL+16]"}],"fun_headline_variants":["Infinite counter makes QMA perfect without extra power","Perfect completeness for QMA via infinite counter","Quantum classes QMA and QMA1 merge with infinite counter","Unlimited counter yields QMA = QMA1","Infinite one-way register perfects QMA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that the infinite counter adds no power depends on the counter being strictly one-way, with only increments and no decrements, because that one-wayness is what keeps forward-evolved witness components on separated intervals orthogonal.","fun_headline_variants_meta":{"raw":{"variants":["Infinite counter makes QMA perfect without extra power","Perfect completeness for QMA via infinite counter","Quantum classes QMA and QMA1 merge with infinite counter","Unlimited counter yields QMA = QMA1","Infinite one-way register perfects QMA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000297,"raw_usage":{"total_tokens":1842,"prompt_tokens":1187,"completion_tokens":655,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":803,"completion_tokens_details":{"reasoning_tokens":580}},"tokens_in":803,"tokens_out":655,"duration_ms":6530,"temperature":1.0,"reasoning_tokens":580,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:34:44.794752+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the $D$-level truncation of the Section 4.2 verifier on an instance whose optimal witness has acceptance probability $p = 1/2 + \\delta$, using the geometric counter witness: if the measured acceptance probability falls below $1 - \\gamma^{D-1}$ by more than the trace-distance error $O(\\sqrt{2^{-m}\\ell})$ for large $D$, the completeness analysis behind Theorem 1.3 is wrong.","supporting_citations":[],"review_version":2}