Quantum bounds for compiled XOR games and $d$-outcome CHSH games

Matilde Baroni; Quoc-Huy Vu; Boris Bourdoncle; Eleni Diamanti; Damian Markham; Ivan Šupić

doi:10.22331/q-2025-10-28-1894

Quantum bounds for compiled XOR games and $d$-outcome CHSH games

Matilde Baroni¹, Quoc-Huy Vu², Boris Bourdoncle³, Eleni Diamanti¹, Damian Markham¹, and Ivan Šupić¹

¹Sorbonne Université, CNRS, LIP6, 4 place Jussieu, 75005 Paris, France
²De Vinci Higher Education, De Vinci Research Center, Paris, France
³Quandela, 7 Rue Léonard de Vinci, 91300 Massy, France

Published:	2025-10-28, volume 9, page 1894
Editor:	Remigiusz Augusiak
Eprint:	arXiv:2403.05502v4
Doi:	https://doi.org/10.22331/q-2025-10-28-1894
Citation:	Quantum 9, 1894 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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: bipartite XOR games and a higher dimensional generalization of CHSH (the SATWAP inequality), that we refer to as d-outcome CHSH games. We also establish that, for any pair of qubit measurements, there exists a compiled XOR game such that its near-optimal winning probability serves as a robust selftest for that particular pair of measurements. Finally, we derive computational self-testing of three anticommuting qubit observables, based on the compilation of the nonlocal game corresponding to the so-called elegant Bell inequality.

Popular summary

Non-local games are a cornerstone of quantum information, providing a concrete way to distinguish classical, quantum, and post-quantum correlations. These games involve at least two non-communicating players, with the no-communication constraint typically enforced via space-like separation.

Recent work by Kalai et al. showed that this constraint can be relaxed using cryptographic techniques, mapping any non-local game to a single-prover interactive proof that preserves classical performance and at least matches the quantum advantage. While they did not fully characterize the quantum power of the single prover, subsequent work by Natarajan and Zhang developed methods demonstrating that the quantum bound is indeed preserved in the simplest non-local game, the CHSH game.

In this paper, we extend these techniques to a broader class of games, including all XOR games and $d$-outcome CHSH games. We show that in these cases the quantum bound survives compilation to the single-prover setting, and, for some XOR games, the compiled versions can serve as self-tests, certifying measurements with a single, untrusted quantum device.

► BibTeX data

@article{Baroni2025quantumbounds,
  doi = {10.22331/q-2025-10-28-1894},
  url = {https://doi.org/10.22331/q-2025-10-28-1894},
  title = {Quantum bounds for compiled {XOR} games and {$d$}-outcome {CHSH} games},
  author = {Baroni, Matilde and Vu, Quoc-Huy and Bourdoncle, Boris and Diamanti, Eleni and Markham, Damian and {\v{S}}upi{\'{c}}, Ivan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1894},
  month = oct,
  year = {2025}
}

► References

[1] J. S. Bell. ``On the Einstein Podolsky Rosen paradox''. Physics Physique Fizika 1, 195–200 (1964).
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195

[2] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. ``Proposed experiment to test local hidden-variable theories''. Phys. Rev. Lett. 23, 880 (1969).
https://doi.org/10.1103/PhysRevLett.23.880

[3] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. ``Bell nonlocality''. Rev. Mod. Phys. 86, 419–478 (2014).
https://doi.org/10.1103/RevModPhys.86.419

[4] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. ``Device-independent security of quantum cryptography against collective attacks''. Phys. Rev. Lett. 98, 230501 (2007).
https://doi.org/10.1103/PhysRevLett.98.230501

[5] Umesh Vazirani and Thomas Vidick. ``Fully Device-Independent Quantum Key Distribution''. Phys. Rev. Lett. 113, 140501 (2014).
https://doi.org/10.1103/PhysRevLett.113.140501

[6] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick. ``Practical device-independent quantum cryptography via entropy accumulation''. Nature Communications 9, 459 (2018).
https://doi.org/10.1038/s41467-017-02307-4

[7] Roger Colbeck. ``Quantum and relativistic protocols for secure multi-party computation''. PhD thesis. University of Cambridge. (2007).
https://doi.org/10.48550/arXiv.0911.3814

[8] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe. ``Random numbers certified by Bell's theorem''. Nature 464, 1021–1024 (2010).
https://doi.org/10.1038/nature09008

[9] Antonio Acín and Lluis Masanes. ``Certified randomness in quantum physics''. Nature 540, 213–219 (2016).
https://doi.org/10.1038/nature20119

[10] Dominic Mayers and Andrew Yao. ``Self testing quantum apparatus''. Quantum Info. Comput. 4, 273–286 (2004).
https://doi.org/10.48550/arXiv.quant-ph/0307205
arXiv:quant-ph/0307205

[11] Ivan Šupić and Joseph Bowles. ``Self-testing of quantum systems: a review''. Quantum 4, 337 (2020).
https://doi.org/10.22331/q-2020-09-30-337

[12] Ben W Reichardt, Falk Unger, and Umesh Vazirani. ``Classical command of quantum systems''. Nature 496, 456–460 (2013).
https://doi.org/10.1038/nature12035

[13] Andrea Coladangelo, Alex B Grilo, Stacey Jeffery, and Thomas Vidick. ``Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources''. In Annual international conference on the theory and applications of cryptographic techniques. Pages 247–277. Springer (2019). arXiv:1708.07359.
https://doi.org/10.1007/978-3-030-17659-4_9
arXiv:1708.07359

[14] László Babai, Lance Fortnow, and Carsten Lund. ``Non-deterministic exponential time has two-prover interactive protocols''. Computational complexity 1, 3–40 (1991).
https://doi.org/10.1007/BF01200056

[15] Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. ``Delegation for bounded space''. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th Annual ACM Symposium on Theory of Computing. Pages 565–574. ACM Press (2013).
https://doi.org/10.1145/2488608.2488679

[16] Tony Metger, Anand Natarajan, and Tina Zhang. ``Succinct arguments for QMA from standard assumptions via compiled nonlocal games''. In 65th Annual Symposium on Foundations of Computer Science. Pages 1193–1201. IEEE Computer Society Press (2024).
https://doi.org/10.1109/FOCS61266.2024.00078

[17] William Aiello, Sandeep Bhatt, Rafail Ostrovsky, and S Raj Rajagopalan. ``Fast verification of any remote procedure call: Short witness-indistinguishable one-round proofs for NP''. In International Colloquium on Automata, Languages, and Programming. Pages 463–474. Springer (2000).
https://doi.org/10.1007/3-540-45022-X_39

[18] Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. ``How to delegate computations: the power of no-signaling proofs''. In David B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing. Pages 485–494. ACM Press (2014).
https://doi.org/10.1145/2591796.2591809

[19] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. ``Quantum advantage from any non-local game''. In Barna Saha and Rocco A. Servedio, editors, 55th Annual ACM Symposium on Theory of Computing. Pages 1617–1628. ACM Press (2023).
https://doi.org/10.1145/3564246.3585164

[20] Urmila Mahadev. ``Classical homomorphic encryption for quantum circuits''. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science. Pages 332–338. IEEE Computer Society Press (2018).
https://doi.org/10.1109/FOCS.2018.00039

[21] Zvika Brakerski. ``Quantum FHE (almost) as secure as classical''. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part III. Volume 10993 of Lecture Notes in Computer Science, pages 67–95. Springer, Cham (2018).
https://doi.org/10.1007/978-3-319-96878-0_3

[22] Anand Natarajan and Tina Zhang. ``Bounding the quantum value of compiled nonlocal games: From CHSH to BQP verification''. In 64th Annual Symposium on Foundations of Computer Science. Pages 1342–1348. IEEE Computer Society Press (2023).
https://doi.org/10.1109/FOCS57990.2023.00081

[23] Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Porat, and Thomas Vidick. ``Simple tests of quantumness also certify qubits''. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part V. Volume 14085 of Lecture Notes in Computer Science, pages 162–191. Springer, Cham (2023).
https://doi.org/10.1007/978-3-031-38554-4_6

[24] Alexia Salavrakos, Remigiusz Augusiak, Jordi Tura, Peter Wittek, Antonio Acín, and Stefano Pironio. ``Bell inequalities tailored to maximally entangled states''. Phys. Rev. Lett. 119, 040402 (2017).
https://doi.org/10.1103/PhysRevLett.119.040402

[25] Shubhayan Sarkar, Debashis Saha, Jędrzej Kaniewski, and Remigiusz Augusiak. ``Self-testing quantum systems of arbitrary local dimension with minimal number of measurements''. npj Quantum Information 7 (2021).
https://doi.org/10.1038/s41534-021-00490-3

[26] David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, and Tina Zhang. ``A computational Tsirelson's theorem for the value of compiled XOR games'' (2024). arXiv:2402.17301.
arXiv:2402.17301

[27] Arthur Mehta, Connor Paddock, and Lewis Wooltorton. ``Self-testing in the compiled setting via tilted-chsh inequalities'' (2025). arXiv:2406.04986.
https://doi.org/10.4230/LIPIcs.TQC.2025.8
arXiv:2406.04986

[28] Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, and Michael Walter. ``A bound on the quantum value of all compiled nonlocal games'' (2024). arXiv:2408.06711.
https://doi.org/10.1145/3717823.3718237
arXiv:2408.06711

[29] Arthur Fine. ``Hidden variables, joint probability, and the Bell inequalities''. Phys. Rev. Lett. 48, 291–295 (1982).
https://doi.org/10.1103/PhysRevLett.48.291

[30] J. Silman, S. Machnes, and N. Aharon. ``On the relation between Bell's inequalities and nonlocal games''. Physics Letters A 372, 3796–3800 (2008).
https://doi.org/10.1016/j.physleta.2008.03.001

[31] Samson Abramsky and Lucien Hardy. ``Logical Bell inequalities''. Phys. Rev. A 85, 062114 (2012).
https://doi.org/10.1103/PhysRevA.85.062114

[32] Boris Tsirelson. ``Quantum analogues of the Bell inequalities. the case of two spatially separated domains''. Journal of Soviet Mathematics 36, 557–570 (1987).
https://doi.org/10.1007/BF01663472

[33] Llorenç Escolà, John Calsamiglia, and Andreas Winter. ``All tight correlation Bell inequalities have quantum violations''. Phys. Rev. Res. 2, 012044 (2020).
https://doi.org/10.1103/PhysRevResearch.2.012044

[34] Stephanie Wehner. ``Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities''. Phys. Rev. A 73, 022110 (2006).
https://doi.org/10.1103/PhysRevA.73.022110

[35] Miguel Navascués, Stefano Pironio, and Antonio Acín. ``Bounding the set of quantum correlations''. Phys. Rev. Lett. 98, 010401 (2007).
https://doi.org/10.1103/PhysRevLett.98.010401

[36] Miguel Navascués and Harald Wunderlich. ``A glance beyond the quantum model''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 466, 881–890 (2010).
https://doi.org/10.1098/rspa.2009.0453

[37] Monique Laurent. ``Sums of squares, moment matrices and optimization over polynomials''. Emerging applications of algebraic geometryPages 157–270 (2009).
https://doi.org/10.1007/978-0-387-09686-5_7

[38] Armin Tavakoli, Alejandro Pozas-Kerstjens, Peter Brown, and Mateus Araújo. ``Semidefinite programming relaxations for quantum correlations''. Reviews of Modern Physics 96 (2024).
https://doi.org/10.1103/revmodphys.96.045006

[39] Dimiter Ostrev. ``The structure of nearly-optimal quantum strategies for the non-local xor games''. Quantum Information & Computation 16, 1191–1211 (2016).
https://doi.org/10.26421/QIC16.13-14-6

[40] Ronald L Rivest, Len Adleman, and Michael L Dertouzos. ``On data banks and privacy homomorphisms''. Foundations of secure computation 4, 169–180 (1978). url: https://api.semanticscholar.org/CorpusID:6905087.
https://api.semanticscholar.org/CorpusID:6905087

[41] Ronald L Rivest, Adi Shamir, and Leonard Adleman. ``A method for obtaining digital signatures and public-key cryptosystems''. Communications of the ACM 21, 120–126 (1978).
https://doi.org/10.1145/359340.359342

[42] Craig Gentry. ``Fully homomorphic encryption using ideal lattices''. In Michael Mitzenmacher, editor, 41st Annual ACM Symposium on Theory of Computing. Pages 169–178. ACM Press (2009).
https://doi.org/10.1145/1536414.1536440

[43] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. ``(Leveled) fully homomorphic encryption without bootstrapping''. In Shafi Goldwasser, editor, ITCS 2012: 3rd Innovations in Theoretical Computer Science. Pages 309–325. Association for Computing Machinery (2012).
https://doi.org/10.1145/2090236.2090262

[44] Zvika Brakerski and Vinod Vaikuntanathan. ``Efficient fully homomorphic encryption from (standard) LWE''. SIAM Journal on computing 43, 831–871 (2014).
https://doi.org/10.1109/FOCS.2011.12

[45] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Moses Charikar and Edith Cohen, editors, 51st Annual ACM Symposium on Theory of Computing. Pages 193–204. ACM Press (2019).
https://doi.org/10.1145/3313276.3316366

[46] Jędrzej Kaniewski, Ivan Šupić, Jordi Tura, Flavio Baccari, Alexia Salavrakos, and Remigiusz Augusiak. ``Maximal nonlocality from maximal entanglement and mutually unbiased bases, and self-testing of two-qutrit quantum systems''. Quantum 3, 198 (2019).
https://doi.org/10.22331/q-2019-10-24-198

[47] H. Buhrman and S. Massar. ``Causality and tsirelson's bounds''. Phys. Rev. A 72, 052103 (2005).
https://doi.org/10.1103/PhysRevA.72.052103

[48] Mohammad Bavarian and Peter W. Shor. ``Information causality, szemerédi-trotter and algebraic variants of chsh'' (2014). arXiv:1311.5186.
arXiv:1311.5186

[49] Yeong-Cherng Liang, Chu-Wee Lim, and Dong-Ling Deng. ``Reexamination of a multisetting bell inequality for qudits''. Phys. Rev. A 80, 052116 (2009).
https://doi.org/10.1103/PhysRevA.80.052116

[50] Ravishankar Ramanathan, Remigiusz Augusiak, and Gláucia Murta. ``Generalized xor games with $d$ outcomes and the task of nonlocal computation''. Phys. Rev. A 93, 022333 (2016).
https://doi.org/10.1103/PhysRevA.93.022333

[51] Daniel Collins, Nicolas Gisin, Noah Linden, Serge Massar, and Sandu Popescu. ``Bell inequalities for arbitrarily high-dimensional systems''. Physical review letters 88, 040404 (2002).
https://doi.org/10.1103/PhysRevLett.88.040404

[52] Thinh P. Le, Chiara Meroni, Bernd Sturmfels, Reinhard F. Werner, and Timo Ziegler. ``Quantum correlations in the minimal scenario''. Quantum 7, 947 (2023).
https://doi.org/10.22331/q-2023-03-16-947

[53] Victor Barizien, Pavel Sekatski, and Jean-Daniel Bancal. ``Custom bell inequalities from formal sums of squares''. Quantum 8, 1333 (2024).
https://doi.org/10.22331/q-2024-05-02-1333

[54] Lewis Wooltorton, Peter Brown, and Roger Colbeck. ``Device-independent quantum key distribution with arbitrarily small nonlocality''. Phys. Rev. Lett. 132, 210802 (2024).
https://doi.org/10.1103/PhysRevLett.132.210802

[55] Ivan Šupić, Jean-Daniel Bancal, Yu Cai, and Nicolas Brunner. ``Genuine network quantum nonlocality and self-testing''. Physical Review A 105 (2022).
https://doi.org/10.1103/physreva.105.022206

[56] Jędrzej Kaniewski. ``Self-testing of binary observables based on commutation''. Phys. Rev. A 95, 062323 (2017).
https://doi.org/10.1103/PhysRevA.95.062323

[57] Nicolas Gisin. ``Bell inequalities: Many questions, a few answers''. Pages 125–138. Springer Netherlands. Dordrecht (2009).
https://doi.org/10.1007/978-1-4020-9107-0_9

[58] Antonio Acín, Stefano Pironio, Tamás Vértesi, and Peter Wittek. ``Optimal randomness certification from one entangled bit''. Physical Review A 93 (2016).
https://doi.org/10.1103/physreva.93.040102

Cited by

[1] O. V. Zubko, "Evolution of scientific concepts of change management in the activities of industrial enterprises", Management of Economy: Theory and Practice. Chumachenko’s Annals 2025, 287 (2025).

[2] David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, and Tina Zhang, "A Computational Tsirelson's Theorem for the Value of Compiled XOR Games", Quantum 10, 1987 (2026).

[3] Matilde Baroni, Eleni Diamanti, Damian Markham, and Ivan Šupić, "Translating Bell nonlocality to prepare-and-measure scenarios under dimensional constraints", Physical Review A 112 6, 062220 (2025).

[4] Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, and Michael Walter, "A bound on the quantum value of all compiled nonlocal games", arXiv:2408.06711, (2024).

[5] Arthur Mehta, Connor Paddock, and Lewis Wooltorton, "Self-testing in the compiled setting via tilted-CHSH inequalities", arXiv:2406.04986, (2024).

[6] Igor Klep, Connor Paddock, Marc-Olivier Renou, Simon Schmidt, Lucas Tendick, Xiangling Xu, and Yuming Zhao, "Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy", arXiv:2507.17006, (2025).

[7] Pierre Botteron, "Nonlocal Games Through Communication Complexity and Quantum Cryptography", arXiv:2510.09457, (2025).

[8] David Cui, Chirag Falor, Anand Natarajan, and Tina Zhang, "A convergent sum-of-squares hierarchy for compiled nonlocal games", arXiv:2507.17581, (2025).

[9] Uta Isabella Meyer, Ivan Šupić, Frédéric Grosshans, and Damian Markham, "Robustly self-testing all maximally entangled states in every finite dimension", arXiv:2508.01071, (2025).

[10] Kim Vallée and Damian Markham, "Formalizing contextuality in sequential scenarios", arXiv:2509.14125, (2025).

[11] Yuki Takeuchi and Duo Xu, "Computational Certified Deletion Property of Magic Square Game and its Application to Classical Secure Key Leasing", arXiv:2510.04529, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 22:03:31) and SAO/NASA ADS (last updated successfully 2026-08-17 22:03:32). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.