Pith. sign in

REVIEW 3 major objections 4 minor 3 references

A convergent sum-of-squares hierarchy for compiled nonlocal games

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2507.17581 v1 pith:CFCYWL26 submitted 2025-07-23 quant-ph

David Cui , Chirag Falor , Anand Natarajan , Tina Zhang This is my paper · ORCID
classification quant-ph MSC 81P4590C2281P40 PACS 03.67.-a03.65.Ud
keywords compilednonlocalgamesquantumhomomorphicencryptionsum-of-squarescertificatesNPAhierarchycommutingvaluesemidefiniteprogrammingniceSoSdecompositionpseudo-expectation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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).

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Sec. 4.2, proof of Theorem 4.2] 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.
  2. [Sec. 4.1, standard form and dual] 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.
  3. [Sec. 5.1.4, Eq. (5.19) and Theorem 5.3] 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.
minor comments (4)
  1. [Sec. 5.1.1, Lemma 5.1] 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.
  2. [Sec. 4.2] 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.
  3. [Eq. (5.19)] 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.
  4. [Sec. 3.1.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the one-sided hierarchy and compiled-soundness transfer are defined independently of the claims they support; the main dependency on prior work is an external, parameter-free technical lemma, while the Banach-Alaoglu issue in Theorem 4.2 is a correctness gap rather than a circularity.

full rationale

The central objects are defined independently of the results they are used to prove. The one-sided NPA hierarchy (Definition 4.1) searches over truncated strongly non-signaling algebraic functionals on Bob's PVM algebra, with objective equal to the SNS correlation value. Its convergence to the quantum commuting value is argued via the external equality omega*_sns = omega*_qc of Kulpe et al. (Theorem 2.10, no author overlap with the present paper) plus a compactness argument, not by assuming the compiled bound. The compiled-soundness transfer (Theorem 3.5) follows from the pseudo-expectation (Definition 3.2), which is defined directly from a compiled strategy; the key lemma E[S^dagger S] >= -negl (Lemma 3.4) is obtained by reducing S^dagger S to a sum of manifestly nonnegative expectation terms and applying Theorem 2.14. Although Theorem 2.14 is quoted from [Cui+24] with overlapping authors, it is an external, parameter-free lemma about block encodings and QPT-implementable measurements under QHE; it does not assume the hierarchy convergence or the existence of nice certificates, so it is independent support rather than circular self-citation. Theorem 5.3 is a self-contained Cholesky-decomposition argument. The correctness caveat is the extension-by-zero step in Theorem 4.2: defining phi^d_ax = 0 on monomials of degree greater than 2d does not preserve the PVM relations or positivity, so the Banach-Alaoglu argument as written is questionable. This is a proof gap, not a circularity: the theorem's conclusion is not an input to the construction, and no fitted value or prediction is being renamed. Accordingly, no circular step is exhibited.

Assumptions & free parameters 1 free parameters · 4 assumptions · 1 invented entities

The paper introduces the one-sided NPA hierarchy as a new construct. It relies on standard cryptographic assumptions, prior results from Kulpe et al., and known matrix analysis lemmas. No hidden free parameters are fitted to data.

free parameters (1)
  • Quantum homomorphic encryption scheme parameters
    The terms negl(λ) are not concrete and depend on the unspecified QHE. This is not fitted to data, but the proofs depend on the existence of such a scheme with security properties.
assumptions (4)
  • domain assumption Quantum homomorphic encryption with correctness with auxiliary input and CPA security exists.
    Required for Theorem 2.14 and all compiled-game bounds. Standard cryptographic assumption, not proved in this paper.
  • standard math Theorem 2.10 from Kulpe et al.: correlations from strongly non-signaling algebraic strategies equal commuting operator correlations.
    Used in Theorem 4.2 to equate p_d limit with ω_qc. Accepted as prior result.
  • standard math Banach-Alaoglu theorem and weak-* compactness for bounded sequences of linear functionals.
    Used in convergence proof of the one-sided NPA hierarchy.
  • standard math Block-encoding lemmas from Cui et al. [Cui+24] for QPT measurability of polynomials.
    Invoked in Theorem 2.14 proof sketch; accepted as prior technical result.
invented entities (1)
  • One-sided NPA hierarchy independent evidence
    purpose: SDP hierarchy that searches over nice sum-of-squares certificates
    New mathematical object with definition and convergence proof; its feasibility corresponds to strongly non-signaling algebraic strategies, not a free entity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A convergent sum-of-squares hierarchy for compiled nonlocal games." pith.science (2026). https://pith.science/paper/CFCYWL26

@misc{pith2026250717581,
  author       = {Pith},
  title        = {Pith review of: A convergent sum-of-squares hierarchy for compiled nonlocal games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CFCYWL26}},
  note         = {Machine review of arXiv:2507.17581}
}
read the original abstract

We continue the line of work initiated by Kalai et al. (STOC '23), studying "compiled" nonlocal games played between a classical verifier and a single quantum prover, with cryptography simulating the spatial separation between the players. The central open question in this area is to understand the soundness of this compiler against quantum strategies, and apart from results for specific games, all that is known is the recent "qualitative" result of Kulpe et al. (STOC '25) showing that the success probability of a quantum prover in the compiled game is bounded by the game's quantum commuting-operator value in the limit as the cryptographic security parameter goes to infinity. In this work, we make progress towards a quantitative understanding of quantum soundness for general games, by giving a concrete framework to bound the quantum value of compiled nonlocal games. Building on the result of Kulpe et al. together with the notion of "nice" sum-of-squares certificates, introduced by Natarajan and Zhang (FOCS '23) to bound the value of the compiled CHSH game, we extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates. We show that this hierarchy converges to the optimal quantum value of the game. Additionally, we present a transformation to make any degree-1 sum-of-squares certificate nice. This approach provides a systematic method to reproduce all known bounds for special classes of games together with Kulpe et al.'s bound for general games from the same framework.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 1 canonical work pages

  1. [1]

    (A.5) The game polynomial of B3 has an optimal quantum value of 6

    (A.3) In this paper, we will look at the symmetrized version of the game polynomial with the transforma- tions B2 0→B0,ω 2→ω to get the following, PB3 =A0B0 +A2 0B2 0 +A0B1 +A2 0B2 1 +A1B0 +A2 1B2 0 +ωA1B1 +ω2A2 1B2 1, (A.4) whereω = −1+i √ 3 2 andA0,A 1,B 0,B 1 are Alice and Bob unitary operators which satisfy the following relations, A3 x = 1 =⇒ A† x =A...

    work page 1976

  2. [267]

    A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device

    doi: 10.1109/FOCS.2018.00033. arXiv: 1804.01082 [quant-ph]. [Bra+18] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. “A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device”. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . 2018, pp. 320–331. doi: 10.1...

    arXiv 2018

  3. [2024]

    A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations

    arXiv: 2403.05502 [quant-ph]. url: https://arxiv.org/abs/2403.05502. [MPW24] Arthur Mehta, Connor Paddock, and Lewis Wooltorton. Self-testing in the compiled setting via tilted-CHSH inequalities . 2024. arXiv: 2406.04986 [quant-ph]. url: https: //arxiv.org/abs/2406.04986. [NPA08] Miguel Navascu´ es, Stefano Pironio, and Antonio Ac´ ın. “A convergent hiera...

    arXiv 2024

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.