Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy
This work solves a key open problem in quantum cryptography by providing quantitative soundness for compiled Bell games, which is crucial for single-device nonlocality testing.
The paper establishes the first quantitative quantum soundness bounds for bipartite compiled Bell games using a newly formalized sequential NPA hierarchy, showing that any polynomial-time prover's score is controlled by a finite-level hierarchy value with negligible gap to the commuting quantum value. It also provides a full characterization of this hierarchy as a robust numerical tool.
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 bipartite compiled Bell games via a newly formalized convergent sequential Navascués-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. 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 such finite-level certificates, 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.