A Computational Tsirelson's Theorem for the Value of Compiled XOR Games

David Cui; Giulio Malavolta; Arthur Mehta; Anand Natarajan; Connor Paddock; Simon Schmidt; Michael Walter; Tina Zhang

doi:10.22331/q-2026-01-27-1987

A Computational Tsirelson’s Theorem for the Value of Compiled XOR Games

David Cui¹, Giulio Malavolta², Arthur Mehta³, Anand Natarajan⁴, Connor Paddock^3,5, Simon Schmidt⁶, Michael Walter^7,6,8, and Tina Zhang⁴

¹Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, United States
²Department of Computing Sciences, Bocconi University, 20136 Milano MI, Italy
³Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON K1N 6N5, Canada
⁴Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, United States
⁵Department of Computer Science, University of Calgary, Calgary, AB T2N 1N4, Canada
⁶Faculty of Computer Science, Ruhr University Bochum, 44801 Bochum, Germany
⁷Faculty of Physics and Faculty of Mathematics, Computer Science and Statistics, Ludwig-Maximilians-Universität München, 80539 München, Germany
⁸Korteweg-de Vries Institute for Mathematics and QuSoft, University of Amsterdam, 1012 WP Amsterdam, Netherlands

Published:	2026-01-27, volume 10, page 1987
Editor:	Paul Skrzypczyk
Eprint:	arXiv:2402.17301v3
Doi:	https://doi.org/10.22331/q-2026-01-27-1987
Citation:	Quantum 10, 1987 (2026).

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

Abstract

Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a “nice'' sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.

► BibTeX data

@article{Cui2026computational,
  doi = {10.22331/q-2026-01-27-1987},
  url = {https://doi.org/10.22331/q-2026-01-27-1987},
  title = {A {C}omputational {T}sirelson's {T}heorem for the {V}alue of {C}ompiled {XOR} {G}ames},
  author = {Cui, David and Malavolta, Giulio and Mehta, Arthur and Natarajan, Anand and Paddock, Connor and Schmidt, Simon and Walter, Michael and Zhang, Tina},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {1987},
  month = jan,
  year = {2026}
}

► References

[1] P. Aravind. A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities. 07 2002. doi:10.48550/arXiv.quant-ph/0206070.
https://doi.org/10.48550/arXiv.quant-ph/0206070
arXiv:quant-ph/0206070

[2] Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, and Ivan Šupić. Quantum bounds for compiled xor games and $ d $-outcome chsh games. Quantum, 9:1894, 2025. doi:10.22331/q-2025-10-28-1894.
https://doi.org/10.22331/q-2025-10-28-1894

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

[4] Zvika Brakerski. Quantum FHE (almost) as secure as classical. In Annual International Cryptology Conference, pages 67–95. Springer, 2018. doi:10.1007/978-3-319-96878-0_3.
https://doi.org/10.1007/978-3-319-96878-0_3

[5] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. Proposed experiment to test local hidden-variable theories. Physical review letters, 23(15):880, 1969. doi:10.1103/PhysRevLett.23.880.
https://doi.org/10.1103/PhysRevLett.23.880

[6] R. Cleve, P. Hoyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 236–249, 2004. doi:10.1109/CCC.2004.1313847.
https://doi.org/10.1109/CCC.2004.1313847

[7] Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay. Perfect parallel repetition theorem for quantum XOR proof systems. Computational Complexity, 17:282–299, 2008. doi:10.1007/s00037-008-0250-4.
https://doi.org/10.1007/s00037-008-0250-4

[8] Andrea Coladangelo, Alex 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. doi:10.1007/978-3-030-17659-4_9.
https://doi.org/10.1007/978-3-030-17659-4_9

[9] Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. i-hop homomorphic encryption and rerandomizable yao circuits. In Advances in Cryptology–CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30, pages 155–172. Springer, 2010. doi:10.1007/978-3-642-14623-7_9.
https://doi.org/10.1007/978-3-642-14623-7_9

[10] 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 Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019), pages 193–204, 2019. doi:10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[11] Alex B Grilo. A simple protocol for verifiable delegation of quantum computation in one round. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pages 28:1–28:13. doi:10.4230/LIPIcs.ICALP.2019.28.
https://doi.org/10.4230/LIPIcs.ICALP.2019.28

[12] Roger A Horn and Fuzhen Zhang. Basic properties of the schur complement. In The Schur complement and its applications, pages 17–46. Springer, 2005. doi:10.1007/0-387-24273-2_2.
https://doi.org/10.1007/0-387-24273-2_2

[13] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE. Communications of the ACM, 64(11):131–138, 2021. doi:10.1145/3485628.
https://doi.org/10.1145/3485628

[14] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1617–1628, 2023. doi:10.1145/3564246.3585164.
https://doi.org/10.1145/3564246.3585164

[15] Urmila Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259–267. IEEE, 2018. doi:10.1109/FOCS.2018.00033.
https://doi.org/10.1109/FOCS.2018.00033

[16] Urmila Mahadev. Classical homomorphic encryption for quantum circuits. SIAM Journal on Computing, pages FOCS18–189, 2020. doi:10.1137/18M1231055.
https://doi.org/10.1137/18M1231055

[17] Arthur Mehta, William Slofstra, and Yuming Zhao. Positivity is undecidable in tensor products of free algebras. arXiv preprint arXiv:2312.05617, 2023. doi:10.48550/arXiv.2312.05617.
https://doi.org/10.48550/arXiv.2312.05617
arXiv:2312.05617

[18] N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65:3373–3376, Dec 1990. doi:10.1103/PhysRevLett.65.3373.
https://doi.org/10.1103/PhysRevLett.65.3373

[19] Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1342–1348, 2023. doi:10.1109/FOCS57990.2023.00081.
https://doi.org/10.1109/FOCS57990.2023.00081

[20] Narutaka Ozawa. About the connes embedding conjecture. Japanese Journal of Mathematics, 8(1):147–183, 2013. doi:10.1007/s11537-013-1280-5.
https://doi.org/10.1007/s11537-013-1280-5

[21] Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3):107–108, 1990. doi:10.1016/0375-9601(90)90172-K.
https://doi.org/10.1016/0375-9601(90)90172-K

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

[23] Konrad Schmüdgen. An Invitation to Unbounded Representations of $\ast$-Algebras on Hilbert Space. Lecture Notes in Mathematics. Springer Cham, Cham, 2020. Published 28 July 2020. doi:10.1007/978-3-030-46366-3.
https://doi.org/10.1007/978-3-030-46366-3

[24] William Slofstra. Lower bounds on the entanglement needed to play XOR non-local games. Journal of Mathematical Physics, 52(10):102202, 2011. doi:10.1063/1.3652924.
https://doi.org/10.1063/1.3652924

[25] William Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-local games. Journal of the American Mathematical Society, 2016. doi:10.1090/jams/929.
https://doi.org/10.1090/jams/929

[26] Boris Tsirelson. Quantum generalizations of Bell's inequality. Letters in Mathematical Physics, 4:93–100, 1980. doi:10.1007/BF00417500.
https://doi.org/10.1007/BF00417500

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

[28] Xingyao Wu, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani. Device-independent parallel self-testing of two singlets. Physical Review A, 93(6), June 2016. doi:10.1103/physreva.93.062121.
https://doi.org/10.1103/physreva.93.062121

Cited by

[1] Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, and Ivan Šupić, "Quantum bounds for compiled XOR games and d-outcome CHSH games", Quantum 9, 1894 (2025).

[2] Marco Fanizza, Larissa Kroell, Arthur Mehta, Connor Paddock, Denis Rochette, William Slofstra, and Yuming Zhao, "The NPA hierarchy does not always attain the commuting operator value", arXiv:2510.04943, (2025).

[3] Pete Rigas, "Error correction, authentication, and false acceptance, probabilities for communication over noisy quantum channels: converse upper bounds on the bit transmission rate", arXiv:2507.03035, (2025).

[4] Pete Rigas, "Parallel repetition of expanded, and multiplayer, Quantum games: anchoring, optimal values, generalized error bounds, dependency-breaking as symmetry-breaking", arXiv:2508.09380, (2025).

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

[6] Pete Rigas, "Quantum Optimality in the Odd-Cycle game: the topological odd-blocker, marked connected components of the giant, consistency of pearls, vanishing homotopy", arXiv:2511.21774, (2025).

[7] 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).

[8] Itay Shalit, "Clifford Strategies in Interactive Protocols are Classically Simulatable", arXiv:2410.12030, (2024).

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

[10] Pete Rigas, "Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, $\mathrm{XOR}^{*}$, compiled XOR, $\mathrm{XOR}^{*}$, and strong parallel repetiton of XOR, $\mathrm{XOR}^{*}$, and FFL games", arXiv:2505.06322, (2025).

[11] 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).

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

[13] Tony Metger, Anand Natarajan, and Tina Zhang, "Succinct arguments for QMA from standard assumptions via compiled nonlocal games", arXiv:2404.19754, (2024).

[14] 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).

[15] Pete Rigas, "Probability distributions over CSS codes: two-universality, QKD hashing, collision bounds, security", arXiv:2510.02402, (2025).

[16] Pete Rigas, "Composable, unconditional security without a Quantum secret key: public broadcast channels and their conceptualizations, adaptive bit transmission rates, fidelity pruning under wiretaps", arXiv:2512.19759, (2025).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-09 01:24:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-09 01:24:40).

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.