A Computational Tsirelson’s Theorem for the Value of Compiled XOR Games
Summarize this article with:
AbstractNonlocal 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.062121Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-27 14:59:07: Could not fetch cited-by data for 10.22331/q-2026-01-27-1987 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-27 14:59:08: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractNonlocal 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.062121Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-27 14:59:07: Could not fetch cited-by data for 10.22331/q-2026-01-27-1987 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-27 14:59:08: No response from ADS or unable to decode the received json data when getting the list of citing works.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.