{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T03:30:38Z","timestamp":1769571038732,"version":"3.49.0"},"reference-count":28,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T00:00:00Z","timestamp":1769472000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["EXC\\ 2092\\ CASA - 390781972"],"award-info":[{"award-number":["EXC\\ 2092\\ CASA - 390781972"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC Starting Grant","award":["No.~101077455, ObfusQation"],"award-info":[{"award-number":["No.~101077455, ObfusQation"]}]},{"name":"ERC Starting Grant","award":["No.~101040907, SYMOPTIC"],"award-info":[{"award-number":["No.~101040907, SYMOPTIC"]}]},{"name":"NWO","award":["OCENW.KLEIN.267"],"award-info":[{"award-number":["OCENW.KLEIN.267"]}]},{"name":"German Federal Ministry of Research, Technology and Space","award":["QuBRA, 13N16135; QuSol, 13N17173"],"award-info":[{"award-number":["QuBRA, 13N16135; QuSol, 13N17173"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["556164098"],"award-info":[{"award-number":["556164098"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["Alliance Consortia Quantum ALLRP 578455 - 22"],"award-info":[{"award-number":["Alliance Consortia Quantum ALLRP 578455 - 22"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 &amp;apos;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 &amp;apos;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 \u201cnice&amp;apos;&amp;apos; sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.<\/jats:p>","DOI":"10.22331\/q-2026-01-27-1987","type":"journal-article","created":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T15:23:14Z","timestamp":1769527394000},"page":"1987","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["A Computational Tsirelson&amp;apos;s Theorem for the Value of Compiled XOR Games"],"prefix":"10.22331","volume":"10","author":[{"given":"David","family":"Cui","sequence":"first","affiliation":[{"name":"Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, United States"}]},{"given":"Giulio","family":"Malavolta","sequence":"additional","affiliation":[{"name":"Department of Computing Sciences, Bocconi University, 20136 Milano MI, Italy"}]},{"given":"Arthur","family":"Mehta","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON K1N 6N5, Canada"}]},{"given":"Anand","family":"Natarajan","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, United States"}]},{"given":"Connor","family":"Paddock","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON K1N 6N5, Canada"},{"name":"Department of Computer Science, University of Calgary, Calgary, AB T2N 1N4, Canada"}]},{"given":"Simon","family":"Schmidt","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Ruhr University Bochum, 44801 Bochum, Germany"}]},{"given":"Michael","family":"Walter","sequence":"additional","affiliation":[{"name":"Faculty of Physics and Faculty of Mathematics, Computer Science and Statistics, Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen, 80539 M\u00fcnchen, Germany"},{"name":"Faculty of Computer Science, Ruhr University Bochum, 44801 Bochum, Germany"},{"name":"Korteweg-de Vries Institute for Mathematics and QuSoft, University of Amsterdam, 1012 WP Amsterdam, Netherlands"}]},{"given":"Tina","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, United States"}]}],"member":"9598","published-online":{"date-parts":[[2026,1,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"P. Aravind. A simple demonstration of Bell&apos;s theorem involving two observers and no probabilities or inequalities. 07 2002. doi:10.48550\/arXiv.quant-ph\/0206070.","DOI":"10.48550\/arXiv.quant-ph\/0206070"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, and Ivan \u0160upi\u0107. Quantum bounds for compiled xor games and $ d $-outcome chsh games. Quantum, 9:1894, 2025. doi:10.22331\/q-2025-10-28-1894.","DOI":"10.22331\/q-2025-10-28-1894"},{"key":"2","doi-asserted-by":"publisher","unstructured":"John S Bell. On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1(3):195, 1964. doi:10.1103\/PhysicsPhysiqueFizika.1.195.","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski. Quantum FHE (almost) as secure as classical. In Annual International Cryptology Conference, pages 67\u201395. Springer, 2018. doi:10.1007\/978-3-319-96878-0_3.","DOI":"10.1007\/978-3-319-96878-0_3"},{"key":"4","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. Physical review letters, 23(15):880, 1969. doi:10.1103\/PhysRevLett.23.880.","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u2013249, 2004. doi:10.1109\/CCC.2004.1313847.","DOI":"10.1109\/CCC.2004.1313847"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay. Perfect parallel repetition theorem for quantum XOR proof systems. Computational Complexity, 17:282\u2013299, 2008. doi:10.1007\/s00037-008-0250-4.","DOI":"10.1007\/s00037-008-0250-4"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013277. Springer, 2019. doi:10.1007\/978-3-030-17659-4_9.","DOI":"10.1007\/978-3-030-17659-4_9"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. i-hop homomorphic encryption and rerandomizable yao circuits. In Advances in Cryptology\u2013CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30, pages 155\u2013172. Springer, 2010. doi:10.1007\/978-3-642-14623-7_9.","DOI":"10.1007\/978-3-642-14623-7_9"},{"key":"9","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 Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019), pages 193\u2013204, 2019. doi:10.1145\/3313276.3316366.","DOI":"10.1145\/3313276.3316366"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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\u201328:13. doi:10.4230\/LIPIcs.ICALP.2019.28.","DOI":"10.4230\/LIPIcs.ICALP.2019.28"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Roger A Horn and Fuzhen Zhang. Basic properties of the schur complement. In The Schur complement and its applications, pages 17\u201346. Springer, 2005. doi:10.1007\/0-387-24273-2_2.","DOI":"10.1007\/0-387-24273-2_2"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE. Communications of the ACM, 64(11):131\u2013138, 2021. doi:10.1145\/3485628.","DOI":"10.1145\/3485628"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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\u20131628, 2023. doi:10.1145\/3564246.3585164.","DOI":"10.1145\/3564246.3585164"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Urmila Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259\u2013267. IEEE, 2018. doi:10.1109\/FOCS.2018.00033.","DOI":"10.1109\/FOCS.2018.00033"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Urmila Mahadev. Classical homomorphic encryption for quantum circuits. SIAM Journal on Computing, pages FOCS18\u2013189, 2020. doi:10.1137\/18M1231055.","DOI":"10.1137\/18M1231055"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2312.05617"},{"key":"17","doi-asserted-by":"publisher","unstructured":"N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65:3373\u20133376, Dec 1990. doi:10.1103\/PhysRevLett.65.3373.","DOI":"10.1103\/PhysRevLett.65.3373"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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\u20131348, 2023. doi:10.1109\/FOCS57990.2023.00081.","DOI":"10.1109\/FOCS57990.2023.00081"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Narutaka Ozawa. About the connes embedding conjecture. Japanese Journal of Mathematics, 8(1):147\u2013183, 2013. doi:10.1007\/s11537-013-1280-5.","DOI":"10.1007\/s11537-013-1280-5"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3):107\u2013108, 1990. doi:10.1016\/0375-9601(90)90172-K.","DOI":"10.1016\/0375-9601(90)90172-K"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. Nature, 496(7446):456\u2013460, 2013. doi:10.1038\/nature12035.","DOI":"10.1038\/nature12035"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Konrad Schm\u00fcdgen. 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.","DOI":"10.1007\/978-3-030-46366-3"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1063\/1.3652924"},{"key":"24","doi-asserted-by":"publisher","unstructured":"William Slofstra. Tsirelson\u2019s problem and an embedding theorem for groups arising from non-local games. Journal of the American Mathematical Society, 2016. doi:10.1090\/jams\/929.","DOI":"10.1090\/jams\/929"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Boris Tsirelson. Quantum generalizations of Bell&apos;s inequality. Letters in Mathematical Physics, 4:93\u2013100, 1980. doi:10.1007\/BF00417500.","DOI":"10.1007\/BF00417500"},{"key":"26","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.","DOI":"10.1007\/BF01663472"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.93.062121"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-27-1987\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T15:23:18Z","timestamp":1769527398000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-27-1987\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,27]]},"references-count":28,"URL":"https:\/\/doi.org\/10.22331\/q-2026-01-27-1987","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,27]]},"article-number":"1987"}}