Counterexamples in self-testing

Laura Mančinska and Simon Schmidt

QMATH, Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen Ø, Denmark

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


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 – robust self-testing – 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 $\mathcal{G}_1$ and $\mathcal{G}_2$, we introduce the $(\mathcal{G}_1 \lor \mathcal{G}_2)$-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.

► BibTeX data

► References

[1] Flavio Baccari, Remigiusz Augusiak, Ivan Šupić, and Antonio Acín. Device-independent certification of genuinely entangled subspaces. Physical Review Letters, 125(26):260507, 2020. doi:10.1103/​physrevlett.125.260507.

[2] John S. Bell. On the Einstein Podolsky Rosen paradox. Phys. Phys. Fiz., 1(3):195–200, 1964. doi:10.1103/​PhysicsPhysiqueFizika.1.195.

[3] John S. Bell. On the problem of hidden variables in quantum mechanics. Rev. Mod. Phys., 38:447–452, Jul 1966. doi:10.1103/​RevModPhys.38.447.

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

[5] Gilles Brassard, Anne Broadbent, and Alain Tapp. Quantum Pseudo-Telepathy. Foundations of Physics, 35(11):1877–1907, Nov 2005. doi:10.1007/​s10701-005-7353-4.

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

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

[8] 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–480, 2019. doi:10.1145/​3313276.3316343.

[9] Irénée Frérot and Antonio Acín. Coarse-grained self-testing. Physical Review Letters, 127(24), 2021. doi:10.1103/​physrevlett.127.240401.

[10] Koon Tong Goh, Jedrzej Kaniewski, Elie Wolfe, Tamás Vértesi, 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.

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

[12] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE, 2020. doi:10.48550/​arXiv.2001.04383.

[13] Jędrzej Kaniewski. Weak form of self-testing. Physical Review Research, 2(3):033420, 2020. doi:10.1103/​PhysRevResearch.2.033420.

[14] Jędrzej Kaniewski, Ivan Šupić, 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.

[15] S Kochen and EP Specker. The problem of hidden variables in quantum mechanics. J. Math. Mech., 17:59–87, 1967. doi:10.1512/​iumj.1968.17.17004.

[16] Laura Mančinska, Thor Gabelgaard Nielsen, and Jitendra Prakash. Glued magic games self-test maximally entangled states, 2021. doi:10.48550/​arXiv.2105.10658.

[17] Laura Mančinska and David E. Roberson. Quantum homomorphisms. J. Combin. Theory Ser. B, 118:228–267, 2016. doi:10.1016/​j.jctb.2015.12.009.

[18] Laura Mančinska, 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–4032, 2013. doi:10.1109/​TIT.2013.2248031.

[19] Laura Mančinska, Jitendra Prakash, and Christopher Schafhauser. Constant-sized robust self-tests for states and measurements of unbounded dimension, 2021. doi:10.48550/​arXiv.2103.01729.

[20] Dominic Mayers and Andrew Yao. Self testing quantum apparatus. Quantum Information & Computation, 4(4):273–286, 2004. doi:10.26421/​QIC4.4-3.

[21] 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–742, 2018. doi:10.1109/​focs.2018.00075.

[22] Anand Natarajan and John Wright. NEEXP is contained in MIP. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 510–518, 2019. doi:10.1109/​FOCS.2019.00039.

[23] Vern I Paulsen, Simone Severini, Daniel Stahlke, Ivan G Todorov, and Andreas Winter. Estimating quantum chromatic numbers. Journal of Functional Analysis, 270(6):2188–2222, 2016. doi:10.1016/​j.jfa.2016.01.010.

[24] Asher Peres. Two simple proofs of the Kochen-Specker theorem. J. Phys. A, 24(4):L175–L178, 1991. doi:10.1088/​0305-4470/​24/​4/​003.

[25] R. Renner and S. Wolf. Quantum Pseudo-Telepathy and the Kochen-Specker Theorem. In International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., pages 322–322, 2004. doi:10.1109/​ISIT.2004.1365359.

[26] Giannicola Scarpa. Quantum entanglement in non-local games, graph parameters and zero-error information theory. PhD thesis, The University of Amsterdam, 2013. URL: https:/​/​​id/​eprint/​2121.

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

[28] William Slofstra. The set of quantum correlations is not closed. Forum Math. Pi, 7:e1, 41, 2019. doi:10.1017/​fmp.2018.3.

[29] Sigurd Storgaard. Certification of quantum systems through self testing. Master's thesis at the University of Copenhagen, 2022.

[30] Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review. Quantum, 4:337, September 2020. doi:10.22331/​q-2020-09-30-337.

[31] Armin Tavakoli, Máté 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.

[32] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.9), 2019. URL: https:/​/​

[33] Thomas Vidick. A simplified analysis of robust self-testing for $n$ EPR pairs, 2018. Available at http:/​/​​ vidick.

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

Cited by

[1] Pavel Sekatski, Jean-Daniel Bancal, Marie Ioannou, Mikael Afzelius, and Nicolas Brunner, "Toward the Device-Independent Certification of a Quantum Memory", Physical Review Letters 131 17, 170802 (2023).

[2] Connor Paddock, William Slofstra, Yuming Zhao, and Yangchen Zhou, "An operator-algebraic formulation of self-testing", arXiv:2301.11291, (2023).

[3] Anne Broadbent, Arthur Mehta, and Yuming Zhao, "Quantum delegation with an off-the-shelf device", arXiv:2304.03448, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-12 03:38:40) and SAO/NASA ADS (last updated successfully 2024-04-12 03:38:41). The list may be incomplete as not all publishers provide suitable and complete citation data.