REVIEW 2 major objections 4 minor 13 references
Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs
T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Two unentangled nonnegative-amplitude proofs verify NEXP with soundness 1/4 + 1/poly.
desk verdict The main theorem appears correct and is a genuine advance; the abstract overclaims one equality that is never proved. 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 protocol is carried by four ingredients. (1) The fixed-gap equality NEXP = QMA+(1, c0, s0) from [BFM24] supplies a one-proof verifier whose acceptance operator B, after thresholding, obeys sup_{|ψ⟩≥0} ⟨ψ|B|ψ⟩ ≤ r < 1 over all nonnegative unit vectors. (2) Symmetric-subspace projections $P_sym^{{(M)}}$ on each proof and $P_sym^{{(2N)}}$ on the retained registers force permutation symmetry of the proof states; because the projectors and the proof states have nonnegative entries, the conditional states remain entrywise nonnegative. (3) The symmetric-subspace identity Tr[$P_sym^{{(2N)}}$(X⊗Y)] = (1/binom(2N,N)) Σ_{j=0}^N binom(N,j)^2 Tr(X_j Y_j) reduces the acceptance probability to a weighted average of j-register overlaps, concentrating the analysis on reduced states with j ≈ N/2 = Θ(log M) registers. (4) Theorem 12, a dimension-independent de Finetti theorem in Hilbert–Schmidt norm, approximates those reduced states by mixtures of identical pure tensor powers with error poly(log M) $M^{{−Ω(1)}}$ independent of dim H; the proof splits the one-register spectrum at eigenvalue 1/m, discards all blocks touching the light subspace by a purity bound, and approximates the surviving heavy block using the known trace-norm de Finetti result. The positivity of the reduced states converts the bound on ⟨ψ|B|ψ⟩ into the constant 1/4 through the comparison ⟨w|ρ|w⟩ ≤ ⟨abs(w)|ρ|abs(w)⟩.
What would settle it
Exhibit a symmetric state on m systems with local dimension exponential in m whose reduced state on (1/2 − η) log2 m registers is Ω($m^{{−η/2}}$) far in Hilbert–Schmidt norm from every mixture of identical pure tensor powers; this would refute Theorem 12. Alternatively, find a NEXP-complete no-instance where the two-proof protocol accepts with probability 1/4 + Ω(1).
Extended reading notes
Core claim
The central claim is the exact characterization NEXP = QMA+(2, 1 − 1/poly(n), 1/4 + 1/poly(n)), with the reverse containment following from brute-force simulation and the forward containment built as a concrete two-proof protocol. On honest inputs both provers send a tensor power of the honest one-proof witness; the verifier projects each proof onto the symmetric subspace, retains N = Θ(log M) registers from each, projects the combined 2N registers onto the joint symmetric subspace, and then runs the thresholded one-proof test on every retained register. Soundness relies on two mechanisms: the nonnegative-expectation bound sup_{|ψ⟩≥0} ⟨ψ|B|ψ⟩ ≤ r < 1 on the threshold operator B, and the new approximation theorem showing that reduced states on Θ(log M) registers are close in Hilbert–Schmidt norm to mixtures of identical pure tensor powers, with error independent of the local dimension. The analysis pins the resulting soundness to 1/4 + o(1), and the paper shows this constant is tight: crossing c = 4s by an inverse-polynomial amount would imply QMA^R(2) = NEXP.
Load-bearing premise
The construction collapses if the fixed-gap equality NEXP = QMA+(1, c0, s0) fails, because the entire two-proof protocol is built on replacing the input verifier with that one-proof verifier; it also depends on the new de Finetti theorem in Hilbert–Schmidt norm holding for Θ(log M) registers with dimension-independent error.
Editorial extensions
If this is right
- Every inverse-polynomial-gap protocol in QMA+(k) with polynomially many proofs collapses into QMA+(2, 1 − 1/poly, 1/4 + 1/poly), so the two-proof nonnegative model acquires the full gap-amplification power of the single model.
- The soundness constant 1/4 is the phase-transition point: QMA^R(2) exactly coincides with QMA+(2, 1 − 1/poly, 1/4 − 1/poly), so any protocol beating 1/4 − 1/poly would prove QMA^R(2) = NEXP.
- The known QMA(2) product-test guarantee (soundness 7/9 + exp(−poly)) and the disentangler-based QMA+(3) guarantee (1/2 + 1/poly) are both improved for nonnegative proofs by this two-proof protocol, which reaches soundness 1/4 + 1/poly.
- The Hilbert–Schmidt de Finetti theorem covers reduced states on up to (1/2 − η) log M registers with dimension-independent error, which is exactly the register count the symmetric-subspace identity requires; without this range the soundness proof would fail.
Reading between the lines
- The 1/4 barrier is likely a property of any proof that only uses the nonnegative-expectation bound plus Hilbert–Schmidt moment matching; going below 1/4 may require controlling trace-norm distance or complex-amplitude tricks, which the sign-removal lemma shows would trigger QMA^R(2) = NEXP.
- A natural testable extension is to apply the same symmetric-projector scheme to other amplitude-restricted proof classes, such as stoquastic verification, where the analogous de Finetti constant would determine whether a similar phase transition exists.
- If the de Finetti theorem could be strengthened to hold for (1 − η) log M registers, the protocol could choose N = Θ(ℓ) more flexibly; the paper's Lemma A.3 suggests the block-deletion bound is the obstruction, so sharper purity bounds on light-subspace blocks are the bottleneck.
- The completeness–soundness tradeoff in Corollary 3 implies that proving QMA(2) ≠ QMA^R(2) would be a way to avoid NEXP ⊆ QMA(2); the paper thus connects the real-versus-complex amplitude question to the nonnegative-proof phase transition.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies gap amplification for QMA^+(2), the class defined by two unentangled nonnegative-amplitude quantum proofs. Its main result (Theorem 1) is that NEXP = QMA^+(2, 1−1/p, 1/4+1/p) for every prescribed polynomial p ≥ 4. The protocol replaces the input NEXP problem by the fixed-gap one-proof characterization of Bassirian–Fefferman–Marwaha, builds a threshold acceptance operator B on L repeated registers, asks two Merlins for M symmetric registers, retains N = Θ(log M) registers from each proof, and applies a joint symmetric-subspace projection together with B-tests. The soundness analysis is centered on Proposition 9, which uses an exact expansion of the symmetric projector (Lemma 11) and a new dimension-independent de Finetti theorem (Theorem 12) that approximates reduced states on Θ(log M) registers by mixtures of identical pure tensor powers in Hilbert–Schmidt norm, with error poly(log m)m^{-Ω(1)} independent of the local dimension. The paper also states corollaries about gap amplification for QMA^+(k) and an optimality barrier at soundness 1/4.
Significance. If the main theorem is correct, it gives a near-optimal answer to a central question about QMA^+(2): the class equals NEXP at completeness 1−1/poly and soundness 1/4+1/poly, and a further improvement to soundness 1/4−1/poly would collapse QMA^R(2) to NEXP. The proof is detailed and largely checkable; the key analytic steps (Lemma 10, Lemma 11, Proposition 9, Theorem 12) are explicit and do not fit parameters to force the 1/4 constant. The dimension-independent tensor-power approximation for logarithmically many registers is a genuine technical contribution, extending the two-register Hilbert–Schmidt de Finetti theorem of Jeronimo–Wu–Xu. The main external dependency is the cited fixed-gap one-proof equality NEXP = QMA^+(1,c0,s0); the construction is explicit about where that assumption enters. The central derivation appears sound, and no circularity or parameter-fitting was found.
major comments (2)
- [Abstract, first display] The assertion that for every completeness c and soundness s with c−s = 1/poly(n) one has NEXP = QMA^+(2,c,s) = QMA^+(2,1−1/poly,1/4+1/poly) is not proved in the body. Theorem 1 establishes the right-hand equality for the specific near-perfect parameters, and Corollary 2 only gives QMA^+(k,c,s) ⊆ QMA^+(2,1−1/p,1/4+1/p). The reverse inclusion for arbitrary c,s requires an additional argument (for instance, a random-acceptance dilution step) and is false in boundary cases such as s = 0. Please either prove the statement with a precise domain for c and s, or restrict the abstract and Section 1.1 to the parameters actually covered by the proof.
- [Abstract, second display] The equality QMA^R(2) = QMA^+(2,1−1/poly,1/4−1/poly) is not derived anywhere in the paper, and no reference is given for it. The body contains only Proposition 6, which gives the one-way inclusion QMA^+(2,c,s) ⊆ QMA^R(2,c,min{1,4s}), and Corollary 3, which gives a conditional collapse QMA^R(2) = NEXP if NEXP ⊆ QMA^+(2,1−δ,1/4−η) with 4η−δ ≥ 1/q. The abstract's equality is a stronger claim. It should be proved, attributed to a precise external result, or removed and replaced by a statement that accurately reflects what is established in the paper.
minor comments (4)
- [Section 5, proof of Theorem 12] The displayed bound in Theorem 12 and the intermediate line '∥ρP − eρP∥1 ≤ 8ℓ√m' are inconsistent with Lemma 14. The correct bound is 8ℓ√(rankP−1)/m, and the final displayed term should be parsed as (8ℓ+√ℓ)/√m. Please fix these typos so the dimension-free nature of the bound is unambiguous.
- [Abstract] The abstract uses the notation 'QMAR(2)' while the body uses 'QMA^R(2)'; please use the same notation throughout.
- [References] The bibliography entries for [gri15] and [gri26] have malformed author fields ('author=Grilo, ...' appears inside the entry); these should be formatted properly.
- [Section 1.1, Corollary 2] The statement of Corollary 2 says 'for every p as in Theorem 1,' but the containment QMA^+(k,c,s) ⊆ QMA^+(2,1−1/p,1/4+1/p) holds for every such p; the wording could be clarified to avoid suggesting that p is constrained by the original c,s.
Circularity Check
No significant circularity; the derivation is self-contained relative to external cited results.
full rationale
The paper's central claim NEXP = QMA^+(2, 1-1/poly, 1/4+1/poly) rests on two external inputs: the fixed-gap one-proof characterization NEXP = QMA^+(1, c0, s0) of Bassirian, Fefferman, and Marwaha [BFM24], and the de Finetti theorem of Jeronimo, Wu, and Xu [JWX26], used inside the paper's own Theorem 12. Neither input is derived from the target result, and neither is a self-citation: the author is Masayuki Miyamoto, not an author of [BFM24] or [JWX26]. The paper explicitly notes that its threshold construction is only available after passing through the fixed-gap characterization, and the threshold bound r = s0/theta is obtained from the soundness of the external one-proof verifier, not from the target two-proof conclusion. The constant 1/4 is not fitted: it arises from the elementary inequality lambda(1-lambda) <= 1/4 after a Cauchy-Schwarz and absolute-value argument, with the soundness constant r entering only through exponential error terms ((1+sqrt r)/2)^{2j} that vanish as j grows. The tensor-power approximation theorem is proved in the appendix from stated assumptions (symmetric support, eigenvalue splits, and the cited JWX26 trace-norm theorem on a subspace of rank at most m); no parameter is tuned to match the claimed 1/4 threshold. The abstract's equality QMA^R(2) = QMA^+(2, 1-1/poly, 1/4-1/poly) appears to be asserted without a proof in the text, but it is not used in the proof of Theorem 1 and is therefore a potential correctness concern rather than a circular step. Overall, no step reduces, by definition or by self-citation, to its own inputs.
Assumptions & free parameters
assumptions (4)
- domain assumption NEXP = QMA+(1,c0,s0) for fixed constants c0>s0 (Theorem 7 of Bassirian-Fefferman-Marwaha)
- domain assumption The high-dimensional Schur transform of Burchardt et al. can be implemented in polynomial time with polylogarithmic local-dimension dependence
- domain assumption Jeronimo-Wu-Xu trace-distance de Finetti theorem (Theorem A.4) with error 8*ell*sqrt(d-1)/a
- standard math Standard facts: Chernoff bound, Hoeffding inequality, Cauchy-Schwarz, operator monotonicity of Schatten norms for PSD matrices
Cite this review
Pith. "Pith review of Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs." pith.science (2026). https://pith.science/paper/2YOWTMAU
@misc{pith2026260807986,
author = {Pith},
title = {Pith review of: Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs},
year = {2026},
howpublished = {\url{https://pith.science/paper/2YOWTMAU}},
note = {Machine review of arXiv:2608.07986}
}
abstract
We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[ \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \] Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.
Figures
Reference graph
Works this paper leans on
-
[7]
On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
[GR26] Sabee Grewal and Dorian Rudolph. On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity. In53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), pages 103–1. Schloss Dagstuhl–Leibniz- Zentrum f¨ ur Informatik,
work page 2026
-
[10]
Optimal Quantum de Finetti Theorems via Argmax Rounding
[JWX26] Fernando Granha Jeronimo, Pei Wu, and Haochen Xu. Optimal Quantum de Finetti Theorems via Argmax Rounding.arXiv preprint arXiv:2608.02590,
-
[12]
[L W26] Yupan Liu and Pei Wu. Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference.arXiv preprint arXiv:2604.27886,
-
[13]
Testing matrix product states
[SW22] Mehdi Soleimanifar and John Wright. Testing matrix product states. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679–1701. SIAM,
2022
-
[2005]
[LNR15] Mathieu Lewin, Phan Th` anh Nam, and Nicolas Rougerie. Remarks on the quantum de Finetti theorem for bosonic systems.Applied Mathematics Research eXpress, 2015(1):48– 63,
work page 2015
-
[2007]
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
[GJ26] William Gay and Fernando Granha Jeronimo. The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems.arXiv preprint arXiv:2605.16249,
-
[2011]
High-dimensional quantum Schur transforms
[BFG+25] Adam Burchardt, Jiani Fei, Dmitry Grinko, Martin Larocca, Maris Ozols, Sydney Timmerman, and Vladyslav Visnevskyi. High-dimensional quantum Schur transforms. arXiv preprint arXiv:2509.22640,
-
[2013]
An Optimal Analysis of the Product Test
[BJW26] Jacob Beckey, Fernando Granha Jeronimo, and Pei Wu. An Optimal Analysis of the Product Test.arXiv preprint arXiv:2607.21477,
Show all 13 references
-
[2015]
[gri26] The Complexity of Stoquastic Sparse Hamiltonians, author=Grilo, Alex B and Rozos, Marios.arXiv preprint arXiv:2605.02845,
-
[2023]
Dimension Independent Disentanglers from Unentanglement and Applications
[JW24] Fernando Granha Jeronimo and Pei Wu. Dimension Independent Disentanglers from Unentanglement and Applications. In39th Computational Complexity Conference (CCC 2024), pages 26–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,
2024
-
[2024]
Quantum Merlin-Arthur and Proofs Without Relative Phase
29 [BFM24] Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. Quantum Merlin-Arthur and Proofs Without Relative Phase. In15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pages 9–1,
2024
-
[2025]
Quantum Merlin-Arthur with an internally separable proof.arXiv preprint arXiv:2410.19152,
[BFL+24] Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu. Quantum Merlin-Arthur with an internally separable proof.arXiv preprint arXiv:2410.19152,
-
[2026]
Unentanglement and post-measurement branch- ing in quantum interactive proofs.arXiv preprint arXiv:2509.15319,
[GK25] Sabee Grewal and William Kretschmer. Unentanglement and post-measurement branch- ing in quantum interactive proofs.arXiv preprint arXiv:2509.15319,
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.