{"id":"2f2471ff-2fbf-4117-bfa5-294daec5bf71","arxiv_id":"2507.17581","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A convergent SDP hierarchy over 'nice' sum-of-squares certificates bounds compiled nonlocal game values, with all degree-1 certificates transformable to nice form.","lead":"This paper constructs a hierarchy of semidefinite programs that bounds the quantum value of compiled nonlocal games, converging to the quantum commuting value. It provides a systematic framework that recovers all previously known special-case bounds and gives quantitative soundness for a wide class of games.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's convergence proof extends truncated positive functionals to the whole PVM algebra by zero on high-degree monomials; this extension violates relations like N^3=N and is not positive, so the Banach-Alaoglu argument is invalid.","rationale":"The paper's central contribution is Theorem 4.3, which rests on Theorem 4.2 (convergence of the one-sided NPA hierarchy) and Theorem 3.5 (compiled soundness of nice certificates). The reader's conditional verdict focused on the quantitative dependence on QHE and the lack of convergence rates; those are limitations rather than internal errors. However, the proof of Theorem 4.2 contains an internal error: the truncated functionals φ^d_ax are extended to the whole algebra by declaring all monomials of degree >2d to vanish. This extension is not well-defined modulo the PVM relations (e.g., N³=N), and it does not preserve positivity even on the free algebra, as the explicit p=I−2N² example shows. Since Banach-Alaoglu is applied to this sequence of purported positive functionals, the convergence argument as written fails. The theorem is plausibly true and repairable by a standard diagonal argument on finite-dimensional subspaces, but the current manuscript does not provide that argument. Thus the central claim is not yet established; the verdict should be UNVERDICTED rather than CONDITIONAL, or at minimum CONDITIONAL with the explicit condition that the convergence proof be repaired.","tokens_in":26869,"tokens_out":22327,"duration_ms":227865,"concrete_test":"Analytically verify the extension step: in the algebra of a single projection N (N²=N=N†), set d=1 and define φ(I)=1, φ(N)=1/2; this is positive on degree-≤2 polynomials. The proposed zero extension gives φ(N³)=0, contradicting N³=N, so the extension is not a functional on the PVM algebra. Independently, compute φ((I−2N²)†(I−2N²)) under the zero extension in the free algebra to see it equals −1, disproving positivity. Then attempt the standard repair: replace the extension by a diagonal subsequence over the increasing subspaces (AB,Y_PVM)≤D and check whether the limit functional is positive and satisfies the consistency/identity constraints; if so, the theorem survives as a revised proof.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The central convergence theorem (Theorem 4.2) is proved by applying Banach-Alaoglu to the sequence of truncated functionals φ^d_ax. As written (Section 4.2), the proof says: 'we can extend it to the whole of [the algebra] by defining φ^d_ax = 0 on monomials of degree strictly greater than 2d. This extended version of φ^d_ax is still positive semidefinite.' This is false. The PVM algebra has relations such as N_by² = N_by (and hence N_by³ = N_by); a functional that sets φ(N_by³)=0 while φ(N_by)=t cannot be a well-defined linear functional on the algebra. Even on the free algebra, the extension by zero fails positivity: for a single generator N, take φ(I)=1, φ(N)=φ(N²)=1/2 on the degree-≤2 subspace (a valid positive functional), and extend by zero to degrees ≥3. The element p=I−2N² satisfies p†p=I−4N²+4N⁴, giving φ(p†p)=1−2=−1<0. Hence the sequence to which Banach-Alaoglu is applied is not a sequence of positive functionals on the algebra, and the limit functional need not be positive. Consequently, the proof of convergence to ω*_qc(G) — and with it Theorem 4.3, the main compiled-soundness result — has a gap. A standard diagonal subsequence argument over finite-dimensional degree-≤D subspaces likely repairs the proof, but the manuscript as written does not establish the claim.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a framework for bounding the value of compiled nonlocal games via \"nice\" sum-of-squares certificates. It introduces a one-sided NPA hierarchy whose primal optimizes over truncated strongly non-signaling algebraic strategies and whose dual is claimed to search exclusively over nice SoS certificates. The main results are (i) convergence of this hierarchy to the quantum commuting value of the game (Theorem 4.2), which is then used to derive a quantitative soundness bound for compiled games (Theorem 4.3), and (ii) a degree-1 transformation showing that any NPA level-1 SoS certificate can be converted into a nice certificate of the same degree (Theorem 5.3), with corollaries for level-1 games. The paper also provides worked nice SoS decompositions for the B3 game and the bipartite matching game in the appendix.","tokens_in":27230,"tokens_out":18039,"duration_ms":165357,"significance":"If the central claims are established, the paper would provide the first general quantitative framework for compiled-game soundness, going beyond the qualitative result of Kulpe et al. and subsuming several prior ad hoc bounds. The one-sided NPA hierarchy is a natural object that may be of independent interest for nonlocal games, and the explicit nice decompositions in the appendix are useful data points. The paper is clearly situated in the literature and is honest about relying on the QHE-based framework of Natarajan--Zhang and the strong non-signaling equivalence of Kulpe et al. However, the manuscript currently contains load-bearing proof gaps: the convergence proof in Section 4.2 uses an invalid extension argument, and the claimed equivalence between the dual of the one-sided hierarchy and the nice SoS hierarchy is not adequately justified. These issues affect Theorems 4.2, 4.3, and 5.3, so the paper needs substantial revision before the main results can be considered established.","major_comments":[{"comment":"The proof extends the truncated functionals φ^d_ax to the whole PVM algebra by defining them to be zero on monomials of degree strictly greater than 2d, and claims the extension is still positive semidefinite. This is not valid. In the PVM algebra, N_by^3 = N_by, so any well-defined linear functional must satisfy φ(N_by^3) = φ(N_by); the proposed extension forces the left side to be 0 while the right side is generally nonzero. The extension also fails positivity even on the free algebra: for d=1, take φ(I)=1 and φ(N)=φ(N^2)=1/2, which is positive on polynomials of degree at most 2, but after extension by zero the element p = I − 2N^2 satisfies φ(p†p) = φ(I) − 4φ(N^2) + 4φ(N^4) = 1 − 2 = −1 < 0. Thus the Banach-Alaoglu step is applied to objects that are not positive linear functionals on the algebra, and the limit functional need not be positive. A diagonal subsequence argument over finite-dimensional degree-truncated subspaces would likely repair the proof, but as written Theorem 4.2 is not established.","section":"Sec. 4.2, proof of Theorem 4.2"},{"comment":"The claim that the dual matrix M_d is block-diagonal \"where each block is limited to only one question of Alice\" is not justified and appears in tension with the definition of B_{x,s,t}. The consistency constraints couple the (a,0) block with the (a,x) block for every x, so the dual matrix can contain entries connecting monomials associated with question 0 and question x within the same factor. A Cholesky row of such a matrix would generally involve Alice projectors for two different questions, which violates Definition 3.1. Consequently the asserted equivalence between the dual of the one-sided hierarchy and the nice SoS hierarchy is not established, and Theorem 4.3's use of an optimal dual solution as a nice certificate is unsupported. The proof should either exhibit a gauge transformation that eliminates the question-0 coupling, or redefine the hierarchy so that its dual genuinely searches over nice certificates. Strong duality and Slater conditions are also not discussed in the passage from primal optimal value to a dual optimal certificate.","section":"Sec. 4.1, standard form and dual"},{"comment":"The block structure of the matrix M in Eq. (5.19) is asserted rather than proved. For an arbitrary degree-1 SoS certificate for p1(G)I − P_G, the coefficient matrix M = S†S need not have vanishing off-diagonal Alice blocks between different questions: cross terms such as M_{ax} M_{a'x'} with x ≠ x' can appear in the individual squares and cancel only after summing over the whole certificate. Lemma 5.2 only provides a block-diagonal Cholesky decomposition for matrices that are already block-diagonal, and Lemma 5.1 only allows one to prescribe the factorization of a principal submatrix; together these lemmas do not force the cross-question blocks to vanish. The Gram-vector argument in Section 5.2 appears to prove equality of the level-1 values of the two hierarchies, assuming the duality issues above are resolved, but it does not, as written, transform a given SoS certificate into a nice certificate for the same bound. Thus Theorem 5.3 and Corollary 5.4 are not established by the present proofs.","section":"Sec. 5.1.4, Eq. (5.19) and Theorem 5.3"}],"minor_comments":[{"comment":"The lemma states that M_a is necessarily positive definite because it is a principal submatrix of a positive semidefinite matrix; it should say positive semidefinite. The unitary relation between two Cholesky factors requires a rank condition or a limiting argument when M_a is singular.","section":"Sec. 5.1.1, Lemma 5.1"},{"comment":"The text says the truncated functionals are extended to the whole of A_{A,X}^{PVM}, but the functionals are defined on the Bob algebra A_{B,Y}^{PVM}; this appears to be a typo and should be corrected.","section":"Sec. 4.2"},{"comment":"The displayed matrix in Eq. (5.19) is hard to parse because the row and column labels are typeset ambiguously. Clarifying which blocks correspond to Alice questions, Bob monomials, and the identity would improve readability.","section":"Eq. (5.19)"},{"comment":"The statement of Theorem 3.5 and the informal Theorem 1.1 say the negligible function depends arbitrarily on the certificate; it would be more precise to state the dependence on the degree and norm of the polynomials appearing in the certificate, since Lemma 3.4's error term depends on the specific polynomial S.","section":"Sec. 3.1.2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important question and contains several promising ideas, including the one-sided NPA hierarchy and the explicit nice decompositions in the appendix. However, the convergence proof in Section 4.2 has a genuine gap that is not merely cosmetic, and the claimed dual/nice-certificate correspondence in Section 4.1 needs a careful rework. The authors should be given the opportunity to repair these points; if the dual correspondence cannot be fixed, the main compiled-soundness theorem would need a different proof, possibly through the approximate primal feasibility route suggested by Lemmas 3.3 and 3.4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does two genuinely useful things. First, it defines a one-sided NPA hierarchy that searches only over nice SoS certificates, and shows this hierarchy converges to the commuting value of the game. Second, it proves that every degree-1 SoS certificate can be transformed into a nice degree-1 certificate, recovering the XOR-game results of Cui et al. with a more general argument. The explicit nice certificates for B3 and the bipartite matching game in the appendix are concrete and checkable. The writing is clear, the related work is honestly positioned, and the reliance on Kulpe et al. for the strong non-signaling equivalence is appropriate rather than circular.\n\nThe soft spot is real and load-bearing. The proof of Theorem 4.2 in Section 4.2 extends each truncated functional φ^d_ax to the whole Bob algebra by setting it to zero on monomials of degree greater than 2d. That is not a well-defined linear functional on the PVM algebra, because relations like N^2 = N imply N^3 = N, so the extension assigns different values to the same element. It also fails positivity even on the free algebra, as the stress-test note shows with the element p = I - 2N^2. The Banach-Alaoglu step is therefore applied to a sequence that is not a sequence of positive functionals on the algebra, and the claimed limit functional need not be positive. The theorem is probably true — a standard diagonal argument over finite-degree subspaces should repair the proof — but the manuscript as written does not establish convergence. Since Theorem 4.3 inherits this gap, the main compiled-soundness result is not yet proven.\n\nThe other issues are minor by comparison. The block structure in Equation (5.19) is asserted informally, and the Cholesky argument assumes positive definiteness where only semidefiniteness is guaranteed. The dependence of the final bound on unspecified negligible functions and on QHE security is inherent to this line of work, though it does limit the quantitative payoff.\n\nThis paper is for the compiled-nonlocal-games community and for anyone using SoS certificates to get quantitative soundness. It deserves a serious referee. I would send it to peer review with a clear request to fix the convergence proof, and I would expect the fix to be straightforward rather than fatal.","headline":"Real contribution in the hierarchy and level-1 transformation, but the convergence proof of Theorem 4.2 has a genuine gap that needs to be fixed before the main theorem is established.","tokens_in":27720,"tokens_out":1607,"would_cite":true,"duration_ms":18908,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P45","90C22","81P40"],"pacs":["03.67.-a","03.65.Ud"],"model":"deepseek-v4-flash","headline":"For any nonlocal game, the paper constructs a convergent hierarchy of semidefinite programs — the one-sided NPA hierarchy — whose feasible certificates give negligible-error upper bounds on the value of the compiled game.","keywords":["compiled nonlocal games","quantum homomorphic encryption","sum-of-squares certificates","NPA hierarchy","quantum commuting value","semidefinite programming hierarchy","nice SoS decomposition","pseudo-expectation"],"falsifier":"Exhibit a CPA-secure quantum homomorphic encryption scheme that fails correctness with auxiliary input for the circuits used in compiled strategies, together with a nonlocal game and a compiled strategy winning with probability above $\\omega_{\\mathrm{qc}}^*(G) + c$ for a constant $c$; this would contradict Theorem 4.3. Alternatively, find a nonlocal game where the one-sided NPA level-1 value strictly exceeds the standard NPA level-1 value, which would refute the level-1 equivalence (Theorem 5.3).","tokens_in":26692,"feed_emoji":"🎲","tokens_out":12232,"duration_ms":104766,"temperature":0.7,"pith_summary":"This paper claims that quantitative soundness for compiled nonlocal games — the single-prover setting where homomorphic encryption replaces the spatial separation between two provers — can be obtained uniformly across all games, not by ad-hoc analysis of individual cases. The vehicle is a new SDP hierarchy, the one-sided NPA hierarchy (a variant of the standard moment-matrix hierarchy for nonlocal games), whose feasible points are exactly 'nice' sum-of-squares certificates: certificates whose square terms involve Alice's POVM elements for a single question. The paper proves this hierarchy converges to the quantum-commuting value of the game from above, and that any certificate from it implying a bound $\\omega'$ also implies the bound $\\omega'+\\mathrm{negl}(\\lambda)$ on the compiled value for every computationally bounded prover. If correct, this gives a systematic computational template for extracting explicit compiled-game soundness rates, recovering all previously known special-case bounds and, whenever a finite level meets the commuting value, full negligible-error soundness.","feed_headline":"Convergent SDP hierarchy bounds every compiled nonlocal game","feed_subtitle":"One certificate yields a commuting-value bound plus a negligible term for the compiled value.","key_machinery":"The central objects are the generalized 'nice' sum-of-squares certificate (Definition 3.1) and its pseudo-expectation (Definition 3.2). A nice certificate writes $\\omega' I - P_G$ as a sum of squares of polynomials that each involve Alice's POVM elements for a single question $x$; the pseudo-expectation evaluates such monomials by substituting the compiled prover's encrypted-question measurement operators for Alice's abstract operators and the second-round measurements for Bob's, then averaging over ciphertexts and post-measurement states. Lemma 3.4 shows the pseudo-expectation of $S^\\dagger S$ is non-negative up to a negligible error, which is what lets a nice SoS bound transfer to the compiled value with only negligible loss. The one-sided NPA hierarchy (Definition 4.1) is the SDP whose dual searches exactly over these nice certificates; its convergence is proven via Banach-Alaoglu compactness together with the equality of strongly non-signaling algebraic and commuting-operator correlations (the paper's Theorem 2.10). The level-1-to-nice transformation is carried by the unitary freedom of SoS coefficient matrices (Cholesky/QR completion, Lemma 5.1) and by a Gram-vector argument (Lemma 5.5) that maps a one-sided feasible solution to an ordinary NPA feasible solution with the same objective value.","core_discovery":"The paper's central discovery is that the obstruction to quantitative compiled-game soundness is not intrinsic: a restricted, one-sided version of the NPA hierarchy — Alice's operators always degree-1 while Bob's operators may have unbounded degree — searches exclusively over nice SoS certificates and still converges to $\\omega_{\\mathrm{qc}}^*(G)$, the quantum-commuting value of the underlying nonlocal game. Because nice certificates have a pseudo-expectation that is a genuine expectation up to negligible error (Lemma 3.4), each level-$d$ feasible solution certifying an upper bound $\\omega'$ on the commuting value also certifies an upper bound $\\omega'+\\mathrm{negl}(\\lambda)$ on the value of the compiled game (Theorem 4.3). As a second result, the paper proves a level-1 equivalence: any degree-1 SoS certificate for $p_1(G)I - P_G$ can be re-expressed, via the unitary freedom of Cholesky/QR decompositions or via a Gram-vector transformation, as a degree-1 nice certificate with the same bound, so every game whose quantum value is certified at NPA level 1 compiles with negligible loss (Theorem 5.3, Corollary 5.4).","pith_inferences":["Because nice certificates have exactly the algebraic structure that self-testing proofs exploit, the one-sided hierarchy could serve as an automated search for the identities behind self-testing arguments, converting a proof of a value bound into a candidate algebraic proof of rigidity.","If the hierarchy's convergence is fast in practice, the framework becomes a numerical certification tool: solve level $d$, read off a certified $\\varepsilon$, then choose $\\lambda$ accordingly — a concrete route to instantiating compiled-game protocols with explicit security parameters.","The existence of a nice degree-2 certificate for $B_3$ suggests that a general 'make any certificate nice' transformation could hold at every NPA level; if so, compilation would preserve the NPA value at every finite level, giving a fully quantitative version of the asymptotic result for all games.","One testable extension: run the one-sided hierarchy on games with large alphabets (e.g., matching games with more vertices) and compare its level-$d$ values against the standard NPA hierarchy's; agreement across levels would indicate which families are likely to compile with negligible error."],"forward_implications":["For every nonlocal game $G$ and every $\\varepsilon>0$, some level $d(\\varepsilon)$ of the one-sided hierarchy yields an upper bound $\\omega_{\\mathrm{qc}}^*(G)+\\varepsilon+\\mathrm{negl}_{S,d}(\\lambda)$ on the compiled value for all computationally bounded strategies $S$.","The asymptotic statement that compiled success tends to the commuting value as $\\lambda\\to\\infty$ follows directly by taking $\\lambda\\to\\infty$ in Theorem 4.3, reproducing the best previously known general bound as a corollary.","Every nonlocal game whose quantum-commuting value is achieved at NPA level 1 compiles with negligible loss: the compiled value is at most $\\omega_{\\mathrm{qc}}^*(G)+\\mathrm{negl}_S(\\lambda)$ (Corollary 5.4).","The framework subsumes all prior quantitative bounds for specific games — compiled CHSH, binary XOR games, and d-outcome CHSH — since each was obtained by an ad-hoc nice certificate that the hierarchy now searches for systematically.","Explicit nice certificates are constructed for two new examples, a 3-answer generalization of CHSH ($B_3$, degree 2) and the bipartite matching game (degree 1), showing the method applies beyond NPA level 1 and beyond binary answer alphabets."],"supporting_citations":[{"why":"Defines the compiled-game model and the quantum homomorphic encryption scheme with correctness with auxiliary input and CPA security that the entire analysis is built on.","marker":"[Kal+23]"},{"why":"Supplies the equality of strongly non-signaling algebraic and commuting correlations (Theorem 2.10) and the asymptotic qualitative bound that Theorem 4.3 quantifies.","marker":"[Kul+24]"},{"why":"Introduced the nice SoS framework and the pseudo-expectation for the compiled CHSH game, whose definitions Section 3 generalizes.","marker":"[NZ23]"},{"why":"Extended the pseudo-expectation to arbitrary monomials with a fixed Alice question, a step Lemma 3.4's proof directly follows.","marker":"[MPW24]"},{"why":"Provides the block-encoding lemmas (2.17, 2.18, 2.20, 2.21) behind Theorem 2.14 and the earlier computational Tsirelson's theorem for compiled XOR games that Section 5 extends.","marker":"[Cui+24]"},{"why":"Supplies the original NPA moment-matrix hierarchy and its convergence theorem, the template for the one-sided hierarchy.","marker":"[NPA08]"},{"why":"Formulates the dual sum-of-squares hierarchy that the nice SoS hierarchy mirrors.","marker":"[Doh+08]"},{"why":"Supplies the standard theorem on unitary freedom of Gram/Cholesky decompositions used in Lemma 5.1 and Theorem 5.3.","marker":"[HJ13]"}],"fun_headline_variants":["Nice SoS certificates make compiled game bounds converge","One-sided NPA hierarchy reaches commuting value of any game","Level-1 SoS certificates compile with negligible loss","General compiled games bounded by nice SoS hierarchy","Quantitative soundness for compiled games via nice certificates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The quantitative transfer from nice SoS certificates to the compiled-game value rests on the cryptographic assumption that the underlying quantum homomorphic encryption scheme is CPA-secure and correct with auxiliary input; if a real scheme leaks information about the encrypted question or fails to evaluate circuits correctly on encrypted inputs, the negligible error term in the compiled bound no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["Nice SoS certificates make compiled game bounds converge","One-sided NPA hierarchy reaches commuting value of any game","Level-1 SoS certificates compile with negligible loss","General compiled games bounded by nice SoS hierarchy","Quantitative soundness for compiled games via nice certificates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000918,"raw_usage":{"total_tokens":4007,"prompt_tokens":1078,"completion_tokens":2929,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":2854}},"tokens_in":694,"tokens_out":2929,"duration_ms":22107,"temperature":1.0,"reasoning_tokens":2854,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:44:14.701752+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a CPA-secure quantum homomorphic encryption scheme that fails correctness with auxiliary input for the circuits used in compiled strategies, together with a nonlocal game and a compiled strategy winning with probability above $\\omega_{\\mathrm{qc}}^*(G) + c$ for a constant $c$; this would contradict Theorem 4.3. Alternatively, find a nonlocal game where the one-sided NPA level-1 value strictly exceeds the standard NPA level-1 value, which would refute the level-1 equivalence (Theorem 5.3).","supporting_citations":[],"review_version":1}