{"id":"5b1321af-7576-4465-9742-9d4a61f6e414","arxiv_id":"2608.07986","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"This paper proves NEXP = QMA^+(2,1-1/poly,1/4+1/poly), a near-optimal gap amplification for nonnegative unentangled quantum proofs.","lead":"For quantum proofs with nonnegative amplitudes, the paper shows that NEXP can be verified with near-perfect completeness and soundness just above 1/4. This gives an almost optimal gap amplification, since pushing the soundness just below 1/4 would collapse two major complexity classes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader identified Theorem 7 and the de Finetti theorem as the weakest assumptions; I agree that these are the main dependencies, but the paper handles them by citation and detailed appendix proofs, respectively. The internal proof of Theorem 1 is careful: the soundness argument in Proposition 9 correctly combines the symmetric-subspace identity, the hypergeometric concentration, and the tensor-power approximation, and the parameter choices (M = poly(n), N = Ω(log M)) make all errors inverse-polynomial. I found no internal inconsistency or missing step that would invalidate the central claim. The abstract's equality QMA^R(2) = QMA^+(2, 1-1/poly, 1/4-1/poly) is flagged in the reader's verdict as requiring proof or citation; this is a separate claim not needed for Theorem 1, so it warrants a conditional acceptance but does not change the assessment of the main theorem. The reader's concern about Lemma A.2's pairwise inner products appears resolved by the invariance argument; in a concrete test with a small symmetric state the asserted equality holds. Thus the verdict remains CONDITIONAL, but on minor clarifications rather than on a load-bearing flaw.","tokens_in":30068,"tokens_out":33391,"duration_ms":318517,"concrete_test":"Verify the statement and constants of Theorem 7 in [BFM24]: specifically confirm that there exist fixed constants 1 > c0 > s0 > 0 with NEXP = QMA^+(1, c0, s0) and that the corresponding one-proof verifier has polynomial-length proofs. If the theorem holds as cited and the constants exist, Step 1 of the amplification is secure; if not, the central claim fails. Independently, a small numerical check of Theorem 12's bound (e.g., m=16, ℓ=4, random symmetric state) can confirm the dimension-free error rate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem, NEXP = QMA^+(2, 1-1/poly, 1/4+1/poly), is supported by a detailed and internally consistent argument. The main external dependency is Theorem 7 (Bassirian–Fefferman–Marwaha), which supplies the fixed-gap one-proof characterization NEXP = QMA^+(1, c0, s0). If that theorem were false or its proof-size behavior different, the amplification would collapse; however, it is a cited published result and the paper's use of it is explicit. The other key ingredient, the dimension-independent de Finetti theorem (Theorem 12), is proven in the appendix; the proofs of Lemmas 13 and 14 and the operator inequalities in Lemma A.2 and A.3 appear correct, and the error bounds are compatible with the claimed soundness. The abstract's equality QMA^R(2) = QMA^+(2, 1-1/poly, 1/4-1/poly) is not derived in the paper and seems too strong without proof, but it is not used in the proof of Theorem 1, so it does not threaten the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":30246,"tokens_out":52456,"duration_ms":519947,"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":[{"comment":"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.","section":"Abstract, first display"},{"comment":"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.","section":"Abstract, second display"}],"minor_comments":[{"comment":"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.","section":"Section 5, proof of Theorem 12"},{"comment":"The abstract uses the notation 'QMAR(2)' while the body uses 'QMA^R(2)'; please use the same notation throughout.","section":"Abstract"},{"comment":"The bibliography entries for [gri15] and [gri26] have malformed author fields ('author=Grilo, ...' appears inside the entry); these should be formatted properly.","section":"References"},{"comment":"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.","section":"Section 1.1, Corollary 2"}],"recommendation":"major_revision","confidential_remarks":"The central theorem and the proof of Proposition 9 appear technically sound, and the new de Finetti theorem is a strong contribution. The main obstacle to publication is the abstract's overclaiming: two displayed equalities are stated as established results but are not proved or cited in the body. These should be corrected before the paper is accepted. I do not see a need to reject, and I do not see any indication of circularity or parameter-fitting in the main derivation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper. The main result is a near-optimal gap amplification for QMA+(2): NEXP has two-prover nonnegative-amplitude proofs with completeness 1−1/poly and soundness 1/4+1/poly. The improvement over Jeronimo–Wu's 7/9 is real, and the 1/4 threshold is the right one because of the sign-removal bound: crossing it would give QMA^R(2)=NEXP. The second contribution, a dimension-independent de Finetti theorem in Hilbert–Schmidt norm for Θ(log m) registers, is a genuine technical addition and will likely be useful elsewhere.\n\nThe proof is careful and the main line is checkable. The symmetric-subspace identity in Lemma 11 is clean, and the soundness analysis reduces to the ε-approximation and the λ(1−λ)≤1/4 bound. The reader flagged a possible issue in Lemma A.2 about pairwise inner products; on closer look the equality holds, since |χ⟩ is invariant under permutations of the first-copy registers and that gives ⟨χ|F_{i1}|χ⟩=⟨χ|F_{11}|χ⟩ for all i. So that concern is resolved.\n\nThe one real problem is the abstract. It states QMA^R(2)=QMA^+(2,1−1/poly,1/4−1/poly) as if it were established. It is not proved anywhere in the paper, and it is not used in Theorem 1. As written it is likely false: the reverse inclusion would require a QMA+ protocol with soundness below 1/4 for arbitrary real-proof languages, and nothing here supplies that. The correct statement is the conditional one in Corollary 3, namely that such an inclusion would collapse QMA^R(2) to NEXP. The abstract should be fixed, not the theorem.\n\nMinor things: the implementation of the symmetric-subspace measurements relies on the high-dimensional Schur transform of Burchardt et al.; the authors state the complexity but might spell out the assumptions on the local dimension. The de Finetti theorem's error bound is a bit ugly but the rate is adequate. The external dependencies (BFM24, JWX26) are explicit and credible; I see no circularity.\n\nThis is a serious paper. The central theorem appears correct, the technical core is original, and the de Finetti result is independently valuable. It deserves a serious referee. I would accept it after the abstract is corrected and the minor clarifications are added.","headline":"The main theorem appears correct and is a genuine advance; the abstract overclaims one equality that is never proved.","tokens_in":30811,"tokens_out":5863,"would_cite":true,"duration_ms":58639,"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.Ac","03.67.-a"],"model":"deepseek-v4-flash","headline":"Two unentangled nonnegative-amplitude proofs verify NEXP with soundness 1/4 + 1/poly.","keywords":["NEXP","QMA+(2)","nonnegative amplitudes","unentangled quantum proofs","gap amplification","de Finetti theorem","symmetric subspace","QMA^R(2)"],"falsifier":"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).","tokens_in":29857,"feed_emoji":"⚛️","tokens_out":8724,"duration_ms":77913,"temperature":0.7,"pith_summary":"This paper proves that NEXP can be verified by two unentangled quantum proofs whose amplitudes are nonnegative, with completeness 1 − 1/poly(n) and soundness 1/4 + 1/poly(n) for any prescribed polynomial p(n) ≥ 4. That is, the equality NEXP = QMA+(2, 1 − 1/poly(n), 1/4 + 1/poly(n)) holds. The soundness constant 1/4 is essentially optimal: QMA^R(2) equals QMA+(2, 1 − 1/poly(n), 1/4 − 1/poly(n)), so any further improvement would collapse QMA^R(2) to NEXP. The argument replaces the original verifier by the fixed-gap one-proof characterization of NEXP, symmetrizes two long lists of proof registers, and uses a new dimension-independent de Finetti theorem in Hilbert–Schmidt norm to control reduced states on logarithmically many registers.","feed_headline":"Two nonnegative proofs verify NEXP at soundness 1/4 + 1/poly","feed_subtitle":"Near-perfect completeness and a sharp 1/4 soundness constant; improving it would collapse QMA^R(2) to NEXP.","key_machinery":"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)⟩.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the fixed-gap one-proof characterization NEXP = QMA+(1,c0,s0) that the amplification starts from.","marker":"[BFM24]"},{"why":"Introduced QMA+(2) and proved its constant-gap NEXP characterization, defining the regime this paper amplifies.","marker":"[JW23]"},{"why":"Provides the optimal trace-norm de Finetti theorem used in Lemma 14 to approximate the high-eigenvalue block.","marker":"[JWX26]"},{"why":"The product-test result that gives QMA(2) strong gap amplification; it is the baseline this paper's 1/4 soundness is compared against.","marker":"[HM13]"},{"why":"Established disentangler-based QMA+(3) protocols with soundness 1/2 + 1/poly, the prior best bound improved here.","marker":"[JW24]"}],"fun_headline_variants":["Nonnegative proofs amplify gap to pin NEXP exactly","Sharp 1/4 soundness: two nonnegative proofs decide NEXP","NEXP unlocked with two nonnegative proofs at 1/4 soundness","The 1/4 soundness limit: nonnegative proofs capture NEXP","Nonnegative proofs nail NEXP at optimal 1/4 soundness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Nonnegative proofs amplify gap to pin NEXP exactly","Sharp 1/4 soundness: two nonnegative proofs decide NEXP","NEXP unlocked with two nonnegative proofs at 1/4 soundness","The 1/4 soundness limit: nonnegative proofs capture NEXP","Nonnegative proofs nail NEXP at optimal 1/4 soundness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000602,"raw_usage":{"total_tokens":2950,"prompt_tokens":1225,"completion_tokens":1725,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":841,"completion_tokens_details":{"reasoning_tokens":1630}},"tokens_in":841,"tokens_out":1725,"duration_ms":13935,"temperature":1.0,"reasoning_tokens":1630,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:39:35.960228+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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).","supporting_citations":[],"review_version":1}