{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T10:42:31Z","timestamp":1769596951319,"version":"3.49.0"},"reference-count":58,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:00:00Z","timestamp":1761609600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"QuantEdu France","award":["ANR-22-CMAS-0001"],"award-info":[{"award-number":["ANR-22-CMAS-0001"]}]},{"name":"Horizon-CL4 program","award":["101135288"],"award-info":[{"award-number":["101135288"]}]},{"name":"PEPR integrated project EPiQ","award":["ANR22-PETQ-0007"],"award-info":[{"award-number":["ANR22-PETQ-0007"]}]},{"name":"QNSP","award":["101114043"],"award-info":[{"award-number":["101114043"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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.<\/jats:p>","DOI":"10.22331\/q-2025-10-28-1894","type":"journal-article","created":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T14:57:21Z","timestamp":1761663441000},"page":"1894","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Quantum bounds for compiled XOR games and\n \n d<\/mml:mi>\n <\/mml:math>\n -outcome CHSH games"],"prefix":"10.22331","volume":"9","author":[{"given":"Matilde","family":"Baroni","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, 4 place Jussieu, 75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quoc-Huy","family":"Vu","sequence":"additional","affiliation":[{"name":"De Vinci Higher Education, De Vinci Research Center, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Bourdoncle","sequence":"additional","affiliation":[{"name":"Quandela, 7 Rue L\u00e9onard de Vinci, 91300 Massy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eleni","family":"Diamanti","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, 4 place Jussieu, 75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damian","family":"Markham","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, 4 place Jussieu, 75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"\u0160upi\u0107","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, 4 place Jussieu, 75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2025,10,28]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"J. S. Bell. ``On the Einstein Podolsky Rosen paradox''. Physics Physique Fizika 1, 195\u2013200 (1964).","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. ``Bell nonlocality''. Rev. Mod. Phys. 86, 419\u2013478 (2014).","DOI":"10.1103\/RevModPhys.86.419"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Antonio Ac\u00edn, 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).","DOI":"10.1103\/PhysRevLett.98.230501"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Umesh Vazirani and Thomas Vidick. ``Fully Device-Independent Quantum Key Distribution''. Phys. Rev. Lett. 113, 140501 (2014).","DOI":"10.1103\/PhysRevLett.113.140501"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Rotem Arnon-Friedman, Fr\u00e9d\u00e9ric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick. ``Practical device-independent quantum cryptography via entropy accumulation''. Nature Communications 9, 459 (2018).","DOI":"10.1038\/s41467-017-02307-4"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Roger Colbeck. ``Quantum and relativistic protocols for secure multi-party computation''. PhD thesis. University of Cambridge. (2007).","DOI":"10.48550\/arXiv.0911.3814"},{"key":"7","doi-asserted-by":"publisher","unstructured":"S. Pironio, A. Ac\u00edn, 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\u20131024 (2010).","DOI":"10.1038\/nature09008"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Antonio Ac\u00edn and Lluis Masanes. ``Certified randomness in quantum physics''. Nature 540, 213\u2013219 (2016).","DOI":"10.1038\/nature20119"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Dominic Mayers and Andrew Yao. ``Self testing quantum apparatus''. Quantum Info. Comput. 4, 273\u2013286 (2004).","DOI":"10.48550\/arXiv.quant-ph\/0307205"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Ivan \u0160upi\u0107 and Joseph Bowles. ``Self-testing of quantum systems: a review''. Quantum 4, 337 (2020).","DOI":"10.22331\/q-2020-09-30-337"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Ben W Reichardt, Falk Unger, and Umesh Vazirani. ``Classical command of quantum systems''. Nature 496, 456\u2013460 (2013).","DOI":"10.1038\/nature12035"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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\u2013277. Springer (2019). arXiv:1708.07359.","DOI":"10.1007\/978-3-030-17659-4_9"},{"key":"13","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, and Carsten Lund. ``Non-deterministic exponential time has two-prover interactive protocols''. Computational complexity 1, 3\u201340 (1991).","DOI":"10.1007\/BF01200056"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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\u2013574. ACM Press (2013).","DOI":"10.1145\/2488608.2488679"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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\u20131201. IEEE Computer Society Press (2024).","DOI":"10.1109\/FOCS61266.2024.00078"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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\u2013474. Springer (2000).","DOI":"10.1007\/3-540-45022-X_39"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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\u2013494. ACM Press (2014).","DOI":"10.1145\/2591796.2591809"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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\u20131628. ACM Press (2023).","DOI":"10.1145\/3564246.3585164"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Urmila Mahadev. ``Classical homomorphic encryption for quantum circuits''. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science. Pages 332\u2013338. IEEE Computer Society Press (2018).","DOI":"10.1109\/FOCS.2018.00039"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski. ``Quantum FHE (almost) as secure as classical''. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology \u2013 CRYPTO 2018, Part III. Volume 10993 of Lecture Notes in Computer Science, pages 67\u201395. Springer, Cham (2018).","DOI":"10.1007\/978-3-319-96878-0_3"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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\u20131348. IEEE Computer Society Press (2023).","DOI":"10.1109\/FOCS57990.2023.00081"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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 \u2013 CRYPTO 2023, Part V. Volume 14085 of Lecture Notes in Computer Science, pages 162\u2013191. Springer, Cham (2023).","DOI":"10.1007\/978-3-031-38554-4_6"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Alexia Salavrakos, Remigiusz Augusiak, Jordi Tura, Peter Wittek, Antonio Ac\u00edn, and Stefano Pironio. ``Bell inequalities tailored to maximally entangled states''. Phys. Rev. Lett. 119, 040402 (2017).","DOI":"10.1103\/PhysRevLett.119.040402"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Shubhayan Sarkar, Debashis Saha, J\u0119drzej Kaniewski, and Remigiusz Augusiak. ``Self-testing quantum systems of arbitrary local dimension with minimal number of measurements''. npj Quantum Information 7 (2021).","DOI":"10.1038\/s41534-021-00490-3"},{"key":"25","unstructured":"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."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Arthur Mehta, Connor Paddock, and Lewis Wooltorton. ``Self-testing in the compiled setting via tilted-chsh inequalities'' (2025). arXiv:2406.04986.","DOI":"10.4230\/LIPIcs.TQC.2025.8"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/3717823.3718237"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Arthur Fine. ``Hidden variables, joint probability, and the Bell inequalities''. Phys. Rev. Lett. 48, 291\u2013295 (1982).","DOI":"10.1103\/PhysRevLett.48.291"},{"key":"29","doi-asserted-by":"publisher","unstructured":"J. Silman, S. Machnes, and N. Aharon. ``On the relation between Bell's inequalities and nonlocal games''. Physics Letters A 372, 3796\u20133800 (2008).","DOI":"10.1016\/j.physleta.2008.03.001"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Samson Abramsky and Lucien Hardy. ``Logical Bell inequalities''. Phys. Rev. A 85, 062114 (2012).","DOI":"10.1103\/PhysRevA.85.062114"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Boris Tsirelson. ``Quantum analogues of the Bell inequalities. the case of two spatially separated domains''. Journal of Soviet Mathematics 36, 557\u2013570 (1987).","DOI":"10.1007\/BF01663472"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Lloren\u00e7 Escol\u00e0, John Calsamiglia, and Andreas Winter. ``All tight correlation Bell inequalities have quantum violations''. Phys. Rev. Res. 2, 012044 (2020).","DOI":"10.1103\/PhysRevResearch.2.012044"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Stephanie Wehner. ``Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities''. Phys. Rev. A 73, 022110 (2006).","DOI":"10.1103\/PhysRevA.73.022110"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Miguel Navascu\u00e9s, Stefano Pironio, and Antonio Ac\u00edn. ``Bounding the set of quantum correlations''. Phys. Rev. Lett. 98, 010401 (2007).","DOI":"10.1103\/PhysRevLett.98.010401"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Miguel Navascu\u00e9s and Harald Wunderlich. ``A glance beyond the quantum model''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 466, 881\u2013890 (2010).","DOI":"10.1098\/rspa.2009.0453"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Monique Laurent. ``Sums of squares, moment matrices and optimization over polynomials''. Emerging applications of algebraic geometryPages 157\u2013270 (2009).","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Armin Tavakoli, Alejandro Pozas-Kerstjens, Peter Brown, and Mateus Ara\u00fajo. ``Semidefinite programming relaxations for quantum correlations''. Reviews of Modern Physics 96 (2024).","DOI":"10.1103\/revmodphys.96.045006"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Dimiter Ostrev. ``The structure of nearly-optimal quantum strategies for the non-local xor games''. Quantum Information & Computation 16, 1191\u20131211 (2016).","DOI":"10.26421\/QIC16.13-14-6"},{"key":"39","unstructured":"Ronald L Rivest, Len Adleman, and Michael L Dertouzos. ``On data banks and privacy homomorphisms''. Foundations of secure computation 4, 169\u2013180 (1978). url: https:\/\/api.semanticscholar.org\/CorpusID:6905087."},{"key":"40","doi-asserted-by":"publisher","unstructured":"Ronald L Rivest, Adi Shamir, and Leonard Adleman. ``A method for obtaining digital signatures and public-key cryptosystems''. Communications of the ACM 21, 120\u2013126 (1978).","DOI":"10.1145\/359340.359342"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Craig Gentry. ``Fully homomorphic encryption using ideal lattices''. In Michael Mitzenmacher, editor, 41st Annual ACM Symposium on Theory of Computing. Pages 169\u2013178. ACM Press (2009).","DOI":"10.1145\/1536414.1536440"},{"key":"42","doi-asserted-by":"publisher","unstructured":"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\u2013325. Association for Computing Machinery (2012).","DOI":"10.1145\/2090236.2090262"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski and Vinod Vaikuntanathan. ``Efficient fully homomorphic encryption from (standard) LWE''. SIAM Journal on computing 43, 831\u2013871 (2014).","DOI":"10.1109\/FOCS.2011.12"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, 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\u2013204. ACM Press (2019).","DOI":"10.1145\/3313276.3316366"},{"key":"45","doi-asserted-by":"publisher","unstructured":"J\u0119drzej Kaniewski, Ivan \u0160upi\u0107, 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).","DOI":"10.22331\/q-2019-10-24-198"},{"key":"46","doi-asserted-by":"publisher","unstructured":"H. Buhrman and S. Massar. ``Causality and tsirelson's bounds''. Phys. Rev. A 72, 052103 (2005).","DOI":"10.1103\/PhysRevA.72.052103"},{"key":"47","doi-asserted-by":"crossref","unstructured":"Mohammad Bavarian and Peter W. Shor. ``Information causality, szemer\u00e9di-trotter and algebraic variants of chsh'' (2014). arXiv:1311.5186.","DOI":"10.1145\/2688073.2688112"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Yeong-Cherng Liang, Chu-Wee Lim, and Dong-Ling Deng. ``Reexamination of a multisetting bell inequality for qudits''. Phys. Rev. A 80, 052116 (2009).","DOI":"10.1103\/PhysRevA.80.052116"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Ravishankar Ramanathan, Remigiusz Augusiak, and Gl\u00e1ucia Murta. ``Generalized xor games with $d$ outcomes and the task of nonlocal computation''. Phys. Rev. A 93, 022333 (2016).","DOI":"10.1103\/PhysRevA.93.022333"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Daniel Collins, Nicolas Gisin, Noah Linden, Serge Massar, and Sandu Popescu. ``Bell inequalities for arbitrarily high-dimensional systems''. Physical review letters 88, 040404 (2002).","DOI":"10.1103\/PhysRevLett.88.040404"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Thinh P. Le, Chiara Meroni, Bernd Sturmfels, Reinhard F. Werner, and Timo Ziegler. ``Quantum correlations in the minimal scenario''. Quantum 7, 947 (2023).","DOI":"10.22331\/q-2023-03-16-947"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Victor Barizien, Pavel Sekatski, and Jean-Daniel Bancal. ``Custom bell inequalities from formal sums of squares''. Quantum 8, 1333 (2024).","DOI":"10.22331\/q-2024-05-02-1333"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Lewis Wooltorton, Peter Brown, and Roger Colbeck. ``Device-independent quantum key distribution with arbitrarily small nonlocality''. Phys. Rev. Lett. 132, 210802 (2024).","DOI":"10.1103\/PhysRevLett.132.210802"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Ivan \u0160upi\u0107, Jean-Daniel Bancal, Yu Cai, and Nicolas Brunner. ``Genuine network quantum nonlocality and self-testing''. Physical Review A 105 (2022).","DOI":"10.1103\/physreva.105.022206"},{"key":"55","doi-asserted-by":"publisher","unstructured":"J\u0119drzej Kaniewski. ``Self-testing of binary observables based on commutation''. Phys. Rev. A 95, 062323 (2017).","DOI":"10.1103\/PhysRevA.95.062323"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Nicolas Gisin. ``Bell inequalities: Many questions, a few answers''. Pages 125\u2013138. Springer Netherlands. Dordrecht (2009).","DOI":"10.1007\/978-1-4020-9107-0_9"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Antonio Ac\u00edn, Stefano Pironio, Tam\u00e1s V\u00e9rtesi, and Peter Wittek. ``Optimal randomness certification from one entangled bit''. Physical Review A 93 (2016).","DOI":"10.1103\/physreva.93.040102"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-28-1894\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T14:57:25Z","timestamp":1761663445000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-28-1894\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,28]]},"references-count":58,"URL":"https:\/\/doi.org\/10.22331\/q-2025-10-28-1894","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,28]]},"article-number":"1894"}}