Quantum bounds for compiled XOR games and -outcome CHSH games
arXiv:2403.05502 · doi:10.22331/q-2025-10-28-1894
Abstract
Nonlocal games play a crucial role in quantum information theory and have numerous applications in certification and cryptographic protocols. Kalai et al. (STOC 2023) introduced a procedure to compile a nonlocal game into a single-prover interactive proof, using a quantum homomorphic encryption scheme, and showed that their compilation method preserves the classical bound of the game. Natarajan and Zhang (FOCS 2023) then showed that the quantum bound is preserved for the specific case of the CHSH game. Extending the proof techniques of Natarajan and Zhang, we show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games: XOR games and d-outcome CHSH games. We also establish that, for any pair of qubit measurements, there exists an XOR game such that its optimal winning probability serves as a self-test for that particular pair of measurements.
30 pages, corrected acknowledgements, published version
References in corpus (27)
- Bell nonlocality
- Device-independent security of quantum cryptography against collective attacks
- Random Numbers Certified by Bell's Theorem
- Bell inequalities for arbitrarily high dimensional systems
- Bounding the set of quantum correlations
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Fully device independent quantum key distribution
- Self-testing of quantum systems: a review
- Certified randomness in quantum physics
- A glance beyond the quantum model
- Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities
- Optimal randomness certification from one entangled bit
- Logical Bell Inequalities
- Self-testing of binary observables based on commutation
- Bell inequalities tailored to maximally entangled states
- Causality and Cirel'son bounds
- Reexamination of a multisetting Bell inequality for qudits
- Maximal nonlocality from maximal entanglement and mutually unbiased bases, and self-testing of two-qutrit quantum systems
- Semidefinite programming relaxations for quantum correlations
- Quantum Correlations in the Minimal Scenario
- Device-independent quantum key distribution with arbitrarily small nonlocality
- On the relation between Bell inequalities and nonlocal games
- Self testing quantum apparatus
- Generalized XOR games with outcomes and the task of non-local computation
- Custom Bell inequalities from formal sums of squares
- All tight correlation Bell inequalities have quantum violations
- A bound on the quantum value of all compiled nonlocal games