{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T15:49:45Z","timestamp":1698335385734},"reference-count":34,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T00:00:00Z","timestamp":1689033600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union's Horizon 2020","award":["101030346"],"award-info":[{"award-number":["101030346"]}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["101078107"],"award-info":[{"award-number":["101078107"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100008398","name":"VILLUM FONDEN","doi-asserted-by":"crossref","award":["10059"],"award-info":[{"award-number":["10059"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100008398","name":"VILLUM FONDEN","doi-asserted-by":"crossref","award":["37532"],"award-info":[{"award-number":["37532"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union's Horizon 2020","award":["01017733"],"award-info":[{"award-number":["01017733"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"In the recent years self-testing has grown into a rich and active area of study with applications ranging from practical verification of quantum devices to deep complexity theoretic results. Self-testing allows a classical verifier to deduce which quantum measurements and on what state are used, for example, by provers Alice and Bob in a nonlocal game. Hence, self-testing as well as its noise-tolerant cousin \u2013 robust self-testing \u2013 are desirable features for a nonlocal game to have.Contrary to what one might expect, we have a rather incomplete understanding of if and how self-testing could fail to hold. In particular, could it be that every 2-party nonlocal game or Bell inequality with a quantum advantage certifies the presence of a specific quantum state? Also, is it the case that every self-testing result can be turned robust with enough ingeniuty and effort? We answer these questions in the negative by providing simple and fully explicit counterexamples. To this end, given two nonlocal games G<\/mml:mi><\/mml:mrow>1<\/mml:mn><\/mml:msub><\/mml:math> and G<\/mml:mi><\/mml:mrow>2<\/mml:mn><\/mml:msub><\/mml:math>, we introduce the (<\/mml:mo>G<\/mml:mi><\/mml:mrow>1<\/mml:mn><\/mml:msub>&#x2228;<\/mml:mo>G<\/mml:mi><\/mml:mrow>2<\/mml:mn><\/mml:msub>)<\/mml:mo><\/mml:math>-game, in which the players get pairs of questions and choose which game they want to play. The players win if they choose the same game and win it with the answers they have given. Our counterexamples are based on this game and we believe this class of games to be of independent interest.<\/jats:p>","DOI":"10.22331\/q-2023-07-11-1051","type":"journal-article","created":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T09:47:55Z","timestamp":1689068875000},"page":"1051","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Counterexamples in self-testing"],"prefix":"10.22331","volume":"7","author":[{"given":"Laura","family":"Man\u010dinska","sequence":"first","affiliation":[{"name":"QMATH, Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen \u00d8, Denmark"}]},{"given":"Simon","family":"Schmidt","sequence":"additional","affiliation":[{"name":"QMATH, Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen \u00d8, Denmark"}]}],"member":"9598","published-online":{"date-parts":[[2023,7,11]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Flavio Baccari, Remigiusz Augusiak, Ivan \u0160upi\u0107, and Antonio Ac\u00edn. Device-independent certification of genuinely entangled subspaces. Physical Review Letters, 125(26):260507, 2020. doi:10.1103\/physrevlett.125.260507.","DOI":"10.1103\/physrevlett.125.260507"},{"key":"1","doi-asserted-by":"publisher","unstructured":"John S. Bell. On the Einstein Podolsky Rosen paradox. Phys. Phys. Fiz., 1(3):195\u2013200, 1964. doi:10.1103\/PhysicsPhysiqueFizika.1.195.","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"2","doi-asserted-by":"publisher","unstructured":"John S. Bell. On the problem of hidden variables in quantum mechanics. Rev. Mod. Phys., 38:447\u2013452, Jul 1966. doi:10.1103\/RevModPhys.38.447.","DOI":"10.1103\/RevModPhys.38.447"},{"key":"3","doi-asserted-by":"publisher","unstructured":"B. Blackadar. Operator algebras, volume 122 of Encyclopaedia of Mathematical Sciences. Springer-Verlag, Berlin, 2006. Theory of $C^*$-algebras and von Neumann algebras, Operator Algebras and Non-commutative Geometry, III. doi:10.1007\/3-540-28517-2.","DOI":"10.1007\/3-540-28517-2"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Anne Broadbent, and Alain Tapp. Quantum Pseudo-Telepathy. Foundations of Physics, 35(11):1877\u20131907, Nov 2005. doi:10.1007\/s10701-005-7353-4.","DOI":"10.1007\/s10701-005-7353-4"},{"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":"David Cui, Arthur Mehta, Hamoon Mousavi, and Seyed Sajjad Nezhadi. A generalization of CHSH and the algebraic structure of optimal strategies. Quantum, 4:346, 2020. doi:10.22331\/q-2020-10-21-346.","DOI":"10.22331\/q-2020-10-21-346"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. Quantum proof systems for iterated exponential time, and beyond. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 473\u2013480, 2019. doi:10.1145\/3313276.3316343.","DOI":"10.1145\/3313276.3316343"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Ir\u00e9n\u00e9e Fr\u00e9rot and Antonio Ac\u00edn. Coarse-grained self-testing. Physical Review Letters, 127(24), 2021. doi:10.1103\/physrevlett.127.240401.","DOI":"10.1103\/physrevlett.127.240401"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Koon Tong Goh, Jedrzej Kaniewski, Elie Wolfe, Tam\u00e1s V\u00e9rtesi, Xingyao Wu, Yu Cai, Yeong-Cherng Liang, and Valerio Scarani. Geometry of the set of quantum correlations. Physical Review A, 97(2), 2018. doi:10.1103\/PhysRevA.97.022104.","DOI":"10.1103\/PhysRevA.97.022104"},{"key":"10","doi-asserted-by":"publisher","unstructured":"William Timothy Gowers and Omid Hatami. Inverse and stability theorems for approximate representations of finite groups. Sbornik: Mathematics, 208(12):1784, 2017. doi:10.4213\/sm8872.","DOI":"10.4213\/sm8872"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE, 2020. doi:10.48550\/arXiv.2001.04383.","DOI":"10.48550\/arXiv.2001.04383"},{"key":"12","doi-asserted-by":"publisher","unstructured":"J\u0119drzej Kaniewski. Weak form of self-testing. Physical Review Research, 2(3):033420, 2020. doi:10.1103\/PhysRevResearch.2.033420.","DOI":"10.1103\/PhysRevResearch.2.033420"},{"key":"13","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.","DOI":"10.22331\/q-2019-10-24-198"},{"key":"14","doi-asserted-by":"publisher","unstructured":"S Kochen and EP Specker. The problem of hidden variables in quantum mechanics. J. Math. Mech., 17:59\u201387, 1967. doi:10.1512\/iumj.1968.17.17004.","DOI":"10.1512\/iumj.1968.17.17004"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Laura Man\u010dinska, Thor Gabelgaard Nielsen, and Jitendra Prakash. Glued magic games self-test maximally entangled states, 2021. doi:10.48550\/arXiv.2105.10658.","DOI":"10.48550\/arXiv.2105.10658"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Laura Man\u010dinska and David E. Roberson. Quantum homomorphisms. J. Combin. Theory Ser. B, 118:228\u2013267, 2016. doi:10.1016\/j.jctb.2015.12.009.","DOI":"10.1016\/j.jctb.2015.12.009"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Laura Man\u010dinska, Giannicola Scarpa, and Simone Severini. New separations in zero-error channel capacity through projective Kochen-Specker sets and quantum coloring. IEEE Trans. Inform. Theory, 59(6):4025\u20134032, 2013. doi:10.1109\/TIT.2013.2248031.","DOI":"10.1109\/TIT.2013.2248031"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Laura Man\u010dinska, Jitendra Prakash, and Christopher Schafhauser. Constant-sized robust self-tests for states and measurements of unbounded dimension, 2021. doi:10.48550\/arXiv.2103.01729.","DOI":"10.48550\/arXiv.2103.01729"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Dominic Mayers and Andrew Yao. Self testing quantum apparatus. Quantum Information & Computation, 4(4):273\u2013286, 2004. doi:10.26421\/QIC4.4-3.","DOI":"10.26421\/QIC4.4-3"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 731\u2013742, 2018. doi:10.1109\/focs.2018.00075.","DOI":"10.1109\/focs.2018.00075"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Anand Natarajan and John Wright. NEEXP is contained in MIP. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 510\u2013518, 2019. doi:10.1109\/FOCS.2019.00039.","DOI":"10.1109\/FOCS.2019.00039"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Vern I Paulsen, Simone Severini, Daniel Stahlke, Ivan G Todorov, and Andreas Winter. Estimating quantum chromatic numbers. Journal of Functional Analysis, 270(6):2188\u20132222, 2016. doi:10.1016\/j.jfa.2016.01.010.","DOI":"10.1016\/j.jfa.2016.01.010"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Asher Peres. Two simple proofs of the Kochen-Specker theorem. J. Phys. A, 24(4):L175\u2013L178, 1991. doi:10.1088\/0305-4470\/24\/4\/003.","DOI":"10.1088\/0305-4470\/24\/4\/003"},{"key":"24","doi-asserted-by":"publisher","unstructured":"R. Renner and S. Wolf. Quantum Pseudo-Telepathy and the Kochen-Specker Theorem. In International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., pages 322\u2013322, 2004. doi:10.1109\/ISIT.2004.1365359.","DOI":"10.1109\/ISIT.2004.1365359"},{"key":"25","unstructured":"Giannicola Scarpa. Quantum entanglement in non-local games, graph parameters and zero-error information theory. PhD thesis, The University of Amsterdam, 2013. URL: https:\/\/eprints.illc.uva.nl\/id\/eprint\/2121."},{"key":"26","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":"27","doi-asserted-by":"publisher","unstructured":"William Slofstra. The set of quantum correlations is not closed. Forum Math. Pi, 7:e1, 41, 2019. doi:10.1017\/fmp.2018.3.","DOI":"10.1017\/fmp.2018.3"},{"key":"28","unstructured":"Sigurd Storgaard. Certification of quantum systems through self testing. Master's thesis at the University of Copenhagen, 2022."},{"key":"29","doi-asserted-by":"publisher","unstructured":"Ivan \u0160upi\u0107 and Joseph Bowles. Self-testing of quantum systems: a review. Quantum, 4:337, September 2020. doi:10.22331\/q-2020-09-30-337.","DOI":"10.22331\/q-2020-09-30-337"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Armin Tavakoli, M\u00e1t\u00e9 Farkas, Denis Rosset, Jean-Daniel Bancal, and Jedrzej Kaniewski. Mutually unbiased bases and symmetric informationally complete measurements in bell experiments. Science advances, 7(7):eabc3847, 2021. doi:10.1126\/sciadv.abc3847.","DOI":"10.1126\/sciadv.abc3847"},{"key":"31","unstructured":"The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.9), 2019. URL: https:\/\/www.sagemath.org."},{"key":"32","unstructured":"Thomas Vidick. A simplified analysis of robust self-testing for $n$ EPR pairs, 2018. Available at http:\/\/users.cms.caltech.edu\/ vidick."},{"key":"33","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), Jun 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-2023-07-11-1051\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T09:48:12Z","timestamp":1689068892000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-07-11-1051\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,11]]},"references-count":34,"URL":"https:\/\/doi.org\/10.22331\/q-2023-07-11-1051","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,11]]},"article-number":"1051"}}