REVIEW 3 major objections 4 minor 18 references
${\sf QMA}={\sf QMA}_1$ with an infinite counter
T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read With an infinite counter, QMA gains perfect completeness.
desk verdict A real step toward QMA=QMA1 via an infinite counter; two small technical bugs in the truncation lemmas, both repairable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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}$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 6, proof of Lemma 5.2, displayed equation (14)] 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 5, proof of Proposition 5.3] 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 6, proof of Lemma 5.2, paragraph after Eq. (15)] 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.
minor comments (4)
- [Section 5, proof of Proposition 5.3] 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 6, proof of Lemma 5.2] 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.
- [Abstract and Section 5] 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 4.1, circuit after Eq. (4)] 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.
Circularity Check
No significant circularity: the main inclusions are proved from first principles with standard lemmas; self-citations are technique credits and comparison points, not load-bearing premises.
full rationale
The derivation chain is self-contained. Theorem 1.1 is proved via two inclusions: QMA ⊆ QMA∞_1 in Section 4 uses an explicit witness construction |ψ⟩_B = sqrt(1−γ²) Σ_d γ^d |d⟩ with γ = (1−p)/p or γ = 1−1/(2p), together with Lemma 2.2, the Marriott–Watrous rewinding lemma, which is proved in the paper; QMA∞ ⊆ QMA in Section 6 uses a truncation argument (Lemma 5.2) based on interval orthogonality and shift-invariance. No parameter is fitted to the target conclusion, and no quantity called a prediction is defined in terms of the output. The authors cite [BJ25] and [BJY24] for the transducer technique, but the present proofs of the relevant statements are given in the paper, and the cited results are not used as axioms for the main theorems. The 'probability truncation' discussion of [KLGN13] is explicitly presented for comparison and is not a premise of Theorem 1.3. A skeptical objection that the fidelity identity near Eq. (14) is false concerns mathematical correctness of a trace-distance bound, not definitional circularity: even if that identity is wrong, the step is an algebraic estimate, not a reduction of the claimed result to an input or to a self-citation. The paper contains no fitted-input-called-prediction step, no uniqueness claim imported from the authors' prior work, and no ansatz smuggled in via citation. The known QMA amplification results are used as baselines, not as the source of the new construction. The central equality QMA = QMA∞ = QMA∞_1 is therefore not circular; it is a substantive pair of inclusions with independent arguments. The false fidelity identity, if confirmed, is a correctness risk, but under the circularity rubric it does not raise the score.
Assumptions & free parameters
assumptions (4)
- standard math Standard postulates of quantum mechanics: pure states, unitary evolution, projective measurement, tensor product structure.
- domain assumption Existence of universal gate sets that include exact inverses, exact CNOT and Hadamard gates (or Clifford+T), and allow exact implementation of controlled reflection R0 and controlled increment modulo powers of two.
- domain assumption The infinite counter register B is a countably infinite-dimensional Hilbert space with orthonormal basis |d⟩ for d∈N, the controlled increment [+1] is a well-defined isometry, and the zero-check gate is a well-defined unitary.
- standard math Standard properties of Hilbert spaces and projections used in the truncation argument, including the fidelity/distance inequalities in Lemma 6.1.
invented entities (1)
-
Infinite counter register B
Cite this review
Pith. "Pith review of ${\sf QMA}={\sf QMA}_1$ with an infinite counter." pith.science (2026). https://pith.science/paper/TM53CLUC
@misc{pith2026250615551,
author = {Pith},
title = {Pith review of: $\sf QMA=\sf QMA_1$ with an infinite counter},
year = {2026},
howpublished = {\url{https://pith.science/paper/TM53CLUC}},
note = {Machine review of arXiv:2506.15551}
}
abstract
A long-standing open problem in quantum complexity theory is whether ${\sf QMA}$, the quantum analogue of ${\sf NP}$, is equal to ${\sf QMA}_1$, its one-sided error variant. We show that ${\sf QMA}={\sf QMA}^{\infty}= {\sf QMA}_1^{\infty}$, where ${\sf QMA}_1^\infty$ is like ${\sf QMA}_1$, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an ``infinite counter'', and compare it to a program counter in a Las Vegas algorithm. The result ${\sf QMA}={\sf QMA}^\infty$ means such an infinite register does not increase the power of ${\sf QMA}$, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a ${\sf QMA}$-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous ${\sf QMA}$ amplifiers. Our new construction achieves completeness $1-2^{-q}$ using $O(1)$ calls to each of the original verifier and its inverse, and $O(\log q)$ other gates, proving that ${\sf QMA}$ has completeness doubly exponentially close to 1, i.e. ${\sf QMA}={\sf QMA}(1-2^{-2^r},2^{-r})$ for any polynomial $r$.
Reference graph
Works this paper leans on
-
[3]
Taming quantum time com- plexity
arXiv: 2502.09249 [BJY24] Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. Taming quantum time com- plexity. Quantum, 8(1444),
-
[6]
arXiv: 2410.04274 [CK24] Marcos Crichigno and Tamara Kohler. Clique homology is QMA 1-hard. Nature Communications, 15(9846),
-
[7]
Space-efficient error reduction for unitary quantum computa- tions
arXiv: 2209.11793 [FKYYL+16] Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-efficient error reduction for unitary quantum computa- tions. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55, pages 14:1–14:14,
-
[10]
Quantum 3-SAT is QMA 1-complete
arXiv: 2310.18010 [GN13] David Gosset and Daniel Nagaj. Quantum 3-SAT is QMA 1-complete. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 756 – 765,
-
[13]
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
arXiv: 1210.1290 [KSV02] Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. Classical and quantum computation. American Mathematical Soc.,
-
[15]
arXiv: 0904.1549 [RGN25] Dorian Rudolph, Sevag Gharibian, and Daniel Nagaj. Quantum 2-SAT on low di- mensional systems is QMA1-complete: Direct embeddings and black-box simulation. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS), volume 325, pages 85:1–85:24,
-
[16]
arXiv: 2401.02368 [Rud24] Dorian Rudolph. Towards a universal gateset for QMA 1,
-
[17]
Bounding the computational power of bosonic systems,
arXiv: 2411.02681 [UC25] Varun Upreti and Ulysse Chabaud. Bounding the computational power of bosonic systems,
Show all 18 references
-
[18]
arXiv: 2503.03600 23
-
[2005]
Fast amplification of QMA
arXiv: cs/0506068 [NWZ09] Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information and Computation , 9(11&12):1053–1068,
-
[2009]
Can effective descriptions of bosonic systems be considered complete?,
arXiv: 0806.0450 [ABC25] Francesco Arzani, Robert I Booth, and Ulysse Chabaud. Can effective descriptions of bosonic systems be considered complete?,
-
[2011]
Bosonic quantum computational complexity
arXiv: quant-ph/0602108 [CJMM25] Ulysse Chabaud, Michael Joseph, Saeed Mehraban, and Arsalan Motamedi. Bosonic quantum computational complexity. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS) , pages 33:1–33:19,
-
[2012]
arXiv: 1111.5306 22 [Kit99] Alexei Y. Kitaev. Quantum NP,
-
[2013]
Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura
arXiv: 1302.0290 [JKNN12] Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information and Computation , 12(5-6):461–471,
-
[2016]
A complete characterization of unitary quan- tum space
arXiv: 1604.08192 [FL18] Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quan- tum space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pages 4–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,
2018 arXiv
-
[2018]
The 7 faces of quantum NP
arXiv: 1604.01384 [Gha24] Sevag Gharibian. The 7 faces of quantum NP. ACM SIGACT News , 54(4):54–91,
-
[2024]
Efficient algorithm for a quantum analogue of 2-SAT
arXiv: 2311.15873 [Bra11] Sergey Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. In Cross Disciplinary Advances in Quantum Computing , volume 536 of Contemporary Math- ematics. AMS,
-
[2025]
Space-efficient quantum error reduction with- out log factors,
arXiv: 2501.13857 [BJ25] Aleksandrs Belovs and Stacey Jeffery. Space-efficient quantum error reduction with- out log factors,
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.