Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy".

Mira: Here's the gist of the paper. The gist: The authors establish quantitative quantum soundness bounds for bipartite compiled Bell games by formalizing and characterizing a sequential Navascu´es-Pironio-Ac´ın (NPA) hierarchy, showing that the compiled score is provably close to the game’s ideal quantum score when the hierarchy converges.

Kai: The paper addresses the gap in understanding quantitative quantum soundness for compiled Bell games, where replacing physical separation with cryptographic assumptions allows probing nonlocality with a single untrusted device Since Bell’s groundbreaking work

Bel64: , understanding and utilizing quantum nonlocality has been pivotal for both the conceptual foundations and practical applications of quantum theory The standard Bell game setup involves multiple, spatially separated provers who cannot communicate during the game However, verifying spatial separations between multiple untrusted quantum devices can be practically challenging Homomorphic encryption (HE) offers a natural solution by allowing the verifier to encrypt Alice’s question and ask for an encrypted answer, satisfying a correctness functionality that enables the prover to compute an outcome as if they knew x despite never being given x in the plain (i.e., never given a decrypted x) To allow for quantum strategies, conventional HE will not suffice because the player strategies involve quantum computations and entanglement Quantum homomorphic encryption (QHE) schemes were established based on the learning with errors (LWE) problem to enable the compilation of Bell games

Bra18; Mah20: This approach was used by Kalai et al.

Kal+23: , establishing the first compiled Bell games, but the quantum soundness remained an open problem Quantitative Bounds via Sequential NPA Hierarchy The primary contribution is establishing quantitative quantum soundness bounds for bipartite compiled Bell games via a newly formalized convergent sequential Navascu´es-Pironio-Ac´ın (NPA) hierarchy Any polynomial-time prover’s score is controlled by a finite-level hierarchy value, and finite-level convergence gives a negligible gap to the commuting quantum value, or to the tensor-product quantum value under flat optimality The first main result upper-bounds the score ωλ(Gcomp, S) achievable by any QPT strategy S as ωqc(G) plus two error terms: an approximation term ε(n) arising from level n of the sequential NPA hierarchy and a negligible cryptographic term (from the QHE scheme and the implementation of S) When the sequential NPA hierarchy attains the commuting score at some finite level n0, or even admits a flat optimal solution at level n0, then ε(n0) = 0 and we obtain a negligible gap to the quantum value This result provides an explicit upper bound on the maximal score that a dishonest prover can obtain at the compiled game Gcomp with some QPT strategy S Characterization of the Sequential NPA Hierarchy The sequential NPA hierarchy is formally introduced and characterized as a robust numerical tool Its two most important theoretical properties are a stopping criterion based on the flatness condition (aka.

Kai: rank-loop) and its asymptotic convergence to the commuting score Theorem B guarantees that the sequential NPA hierarchy is guaranteed to converge to the commuting score as n → ∞ Moreover, if the hierarchy for a bipartite Bell game G admits a flat optimal solution at some finite level n, then this solution yields a finite-dimensional GNS representation (H, π, omega⟩) of B and an optimal commuting quantum strategy (Aˆax, π(Bby), omega⟩) satisfying ωn seqNPA(G) = ωqc(G) = ωq(G) Signaling Decomposition and Score Bounds The analysis employs a decomposition of the measurement operators into no-signaling and signaling components using group representation theory inspired by

Ren+17: This leads to Proposition 2.7, which decomposes the measurement operators Aˆλ,n ax into Aˆλ,n ax(NS), Aˆλ,n ax(SI), and Aˆλ,n ax(res) This decomposition allows for bounding the advantage of signaling with negligible functions The main quantitative soundness theorem (Theorem 2.8) states that for every n > 0 there exists a negligible function ηS,n(λ) such that ωλ(Gcomp, S) ≤ ωn seqNPA(G) + ηS,n(λ) = ωqc(G) + ε(n) + ηS,n(λ), where ε(n) → 0 as n → ∞ Necessity of Game-Specific Approximation Errors The paper explores whether game-specific NPA approximation error ε(n) is fundamentally necessary for quantitative quantum soundness to games G without a finite convergence of the sequential NPA hierarchy By relying on the standard complexity conjecture MIPco = coRE (Conjecture 4.2), Proposition 4.3 establishes the existence of a family of Bell games G(n) where ωqc(G(n)) ≤ 1/4 while the n-th level of the standard NPA hierarchy gives a bound ωn NPA(G(n)) ≥ 3/4 This implies that no universal computable rate of convergence ε(k) → 0 for the NPA hierarchy holds for all games G and all levels k The central challenge is to compile these high-scoring strategies into a QPT cheating strategy S(λ)comp for the family of compiled games G(n(λ))comp The analysis reveals practical limits on the tightness of the bound in Theorem 2.8, as a verifier limited to a poly(λ)-sized computer can only feasibly solve the hierarchy up to level n = log(λ) Furthermore, if Conjecture 4.2 holds, then Proposition 4.3 implies the existence of games where the sequential NPA hierarchy converges arbitrarily slowly, whence upper bounds by Theorem 2.8 becomes trivial A useful sufficient certificate for such finite convergence is the existence of a flat optimal solution Future Directions Future research is motivated by exploring whether a more universal statement of the form ωλ(Gcomp, S) ≤ ωqc(G) + ηu(λ), where ηu(λ) is some negligible function that is universal for all games G, can be proven This involves overcoming obstacles related to signaling properties and QHE correctness for almost commuting strategies The paper suggests a unified mathematical framework that translates protocols from the “space-like separation world” into the “compiled single-prover world” quantitatively The work contributes to this broader effort by providing quantitative soundness bounds for all bipartite compiled Bell games Acknowledgments The authors thank Matilde Baroni, Dominik Leichtle, Ivan Supi´c, Thomas Vidick, and Michael Walter for the helpful discussions Connor Paddock and Simon Schmidt want to thank Alexander Kulpe, Guilio Malavolta, and Michael Walter for discussions about compilation in the commuting operator framework and its relation to the conjecture MIPco = coRE MOR, LT and XX acknowledge funding by the ANR for the JCJC grant LINKS (ANR-23-CE47-0003) and T-ERC QNET (ANR-24-ERCS-0008), by INRIA and CIEDS in the Action Exploratoire project DEPARTURE MOR, IK, LT and XX acknowledge support by the European Union’s Horizon 2020 Research and Innovation Programme under QuantERA Grant Agreement no.

Paper summary: Kai: So, this paper, "Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy," it's about taking those Bell games and compiling them under cryptographic assumptions. Basically, it replaces needing multiple physically separate devices with just one untrusted device that can be probed.

Mira: Right. The core idea is that this compilation allows you to test nonlocality using only a single piece of hardware, which is something really practical for experiments because building those spatially separated setups is hard.

Kai: But the paper points out that while Kalai et al., in STOC'twenty-three showed this compilation preserves quantum advantages, the quantitative quantum soundness part remained an open question <ref:2507.17006#pg1>.

Mira: Exactly. They figured out *if* you could preserve the advantage, but they didn't nail down exactly how much of that advantage you could expect to see under a dishonest prover.

Kai: This paper tackles that gap by establishing the first quantitative quantum soundness bounds for all bipartite compiled Bell games using something they call a newly formalized convergent sequential Navascués-Pironio-Acín hierarchy.

Mira: It claims that any polynomial-time prover's score is controlled by a finite-level hierarchy value, and when that hierarchy converges, the gap between that score and the commuting quantum value is negligible, or even zero under flat optimality.

Kai: So what does this mean for us practically? It gives us an explicit upper bound on the maximal score a dishonest prover can get in the compiled game Gcomp with some quantum polynomial-time strategy S.

Mira: The analysis uses a decomposition of measurement operators into no-signaling, signaling, and residual components to show how they bound the advantage of signaling with negligible functions.

Kai: It also characterizes this sequential NPA hierarchy itself as a computational tool. They show it has a stopping criterion based on flatness and that it asymptotically converges to the commuting score as n goes to infinity.

Mira: If you find a flat optimal solution at some finite level n, then that solution gives you an optimal commuting quantum strategy, meaning the error term ε(n) becomes zero for that specific level.

Conclusion: Kai: So, looking at "Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy," it really boils down to getting a concrete number on how much cheating is possible when you use cryptography to simulate a setup that was originally designed for physical separation.

Mira: It’s about translating those abstract notions of nonlocality, which used to require separate locations, into a measurable quantity constrained by the sequential NPA hierarchy.

Kai: The main implication here is that we can now say precisely how close any dishonest prover can get to the ideal quantum score when they use this compiled game setup.

Mira: It suggests that for many games, if you just run your sequential NPA hierarchy up to a certain finite level, you get a bound that’s essentially equal to the actual quantum value.

Kai: And Lev is concerned about what this means for real hardware, because the paper discusses how the error terms are structured based on complexity conjectures like MIPco equals coRE.

Mira: That's right. The authors point out that if those complexity conjectures hold, then you might never find a universal convergence rate ε(k) going to zero for every single game G at every level k.

Kai: If that’s true, the bound from Theorem two point eight becomes trivial because there are games where the sequential NPA hierarchy converges arbitrarily slowly <ref:2507.17006#pg1>.

Mira: So, the practical limit is that a verifier with a limited computer can only feasibly check up to a level n equal to log(lambda). And you still rely on finding that flat optimal solution for any guaranteed zero error gap.

Kai: It's not about solving the problem entirely, but it gives us the roadmap for where we need to look next, which is trying to find a universal statement like ωλ(Gcomp, S) less than or equal to ωqc(G) plus some negligible function ηu(λ).