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

• URL: http://arxiv.org/abs/2507.17006v1
• Date: Tue, 22 Jul 2025 20:31:41 GMT
• Title: Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy
• Authors: Igor Klep, Connor Paddock, Marc-Olivier Renou, Simon Schmidt, Lucas Tendick, Xiangling Xu, Yuming Zhao,
• Abstract summary: We show the first quantitative quantum soundness bounds for every bipartite compiled Bell game.<n>More generally, for all bipartite games we show that the compiled score cannot significantly exceed the bounds given by a newly formalized sequential Navascu'es-Pironio-Ac'in hierarchy.
• Score: 3.34301287453961
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Compiling Bell games under cryptographic assumptions replaces the need for physical separation, allowing nonlocality to be probed with a single untrusted device. While Kalai et al. (STOC'23) showed that this compilation preserves quantum advantages, its quantitative quantum soundness has remained an open problem. We address this gap with two primary contributions. First, we establish the first quantitative quantum soundness bounds for every bipartite compiled Bell game whose optimal quantum strategy is finite-dimensional: any polynomial-time prover's score in the compiled game is negligibly close to the game's ideal quantum value. More generally, for all bipartite games we show that the compiled score cannot significantly exceed the bounds given by a newly formalized sequential Navascu\'es-Pironio-Ac\'in (NPA) hierarchy. Second, we provide a full characterization of this sequential NPA hierarchy, establishing it as a robust numerical tool that is of independent interest. Finally, for games without finite-dimensional optimal strategies, we explore the necessity of NPA approximation error for quantitatively bounding their compiled scores, linking these considerations to the complexity conjecture $\mathrm{MIP}^{\mathrm{co}}=\mathrm{coRE}$ and open challenges such as quantum homomorphic encryption correctness for "weakly commuting" quantum registers.

Related papers

• A convergent sum-of-squares hierarchy for compiled nonlocal games [1.5029560229270191]
  We study "compiled" nonlocal games played between a classical verifier and a single quantum prover.<n>We show that the success probability of a quantum prover in the compiled game is bounded by the game's quantum commuting-operator value.<n>We extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates.
  arXiv  Detail & Related papers  (2025-07-23T15:16:38Z)
• Bounding the asymptotic quantum value of all multipartite compiled non-local games [0.0]
  Non-local games are a powerful tool to distinguish between correlations possible in classical and quantum worlds.<n> Kalai et al. (STOC'23) proposed a compiler that converts multipartite non-local games into interactive protocols with a single prover.<n>We prove Kalai et al.'s compiler indeed achieves quantum soundness for all multipartite non-local games.
  arXiv  Detail & Related papers  (2025-07-16T16:58:39Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover.<n>We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography [0.0]
  We show that if one extends such games by considering constraints and loss, the convergence of the SDPs to the optimal value still holds.<n>We give applications of this result, and we compute SDPs that show tighter security of protocols for relativistic bit commitment, quantum key distribution, and quantum position verification.
  arXiv  Detail & Related papers  (2024-05-22T15:09:30Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.<n>This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  We study multi-party computation for classical functionalities (in the plain model) with security against malicious-time quantum adversaries. We assume superpolynomial quantum hardness of learning with errors (LWE), and quantum hardness of an LWE-based circular security assumption. Along the way, we develop cryptographic primitives that may be of independent interest.
  arXiv  Detail & Related papers  (2020-05-23T00:42:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.