1Department of Mathematics, University of Toronto, Toronto, Canada.
2Department of Computer Science, University of Toronto, Toronto, Canada.
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
$textit{Self-testing}$ has been a rich area of study in quantum information theory. It allows an experimenter to interact classically with a black box quantum system and to test that a specific entangled state was present and a specific set of measurements were performed. Recently, self-testing has been central to high-profile results in complexity theory as seen in the work on entangled games PCP of Natarajan and Vidick [26], iterated compression by Fitzsimons et al. [16], and NEEXP in MIP* due to Natarajan and Wright [27]. The most studied self-test is the CHSH game which features a bipartite system with two isolated devices. This game certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. Most of the self-testing literature has focused on extending these results to self-test for tensor products of EPR states and tensor products of Pauli measurements.
In this work, we introduce an algebraic generalization of CHSH by viewing it as a linear constraint system (LCS) game, exhibiting self-testing properties that are qualitatively different. These provide the first example of LCS games that self-test non-Pauli operators resolving an open questions posed by Coladangelo and Stark [15]. Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal [11]. Additionally, our games have $1$ bit question and $log n$ bit answer lengths making them suitable candidates for complexity theoretic application. This work is the first step towards a general theory of self-testing arbitrary groups. In order to obtain our results, we exploit connections between sum of squares proofs, non-commutative ring theory, and the Gowers-Hatami theorem from approximate representation theory. A crucial part of our analysis is to introduce a sum of squares framework that generalizes the $textit{solution group}$ of Cleve, Liu, and Slofstra [10] to the non-pseudo-telepathic regime. Finally, we give the first example of a game that is not a self-test. Our results suggest a richer landscape of self-testing phenomena than previously considered.
► BibTeX data
► References
[1] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. Device-independent security of quantum cryptography against collective attacks. Phys. Rev. Lett., 98:230501, 2007. https://doi.org/10.1103/physrevlett.98.230501.
https://doi.org/10.1103/physrevlett.98.230501
[2] John Stewart Bell. On the einstein-podolsky-rosen paradox. Physics, 1:195, 1964. https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195.
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195
[3] Cédric Bamps and Stefano Pironio. Sum-of-squares decompositions for a family of clauser-horne-shimony-holt-like inequalities and their application to self-testing. Phys. Rev. A, 91(052111), 2015. https://doi.org/10.1103/PhysRevA.91.052111.
https://doi.org/10.1103/PhysRevA.91.052111
[4] Mohammad Bavarian and Peter W. Shor. Information causality, szemerédi-trotter and algebraic variants of chsh. In Conference on Innovations in Theoretical Computer Science, 2015. https://doi.org/10.1145/2688073.2688112.
https://doi.org/10.1145/2688073.2688112
[5] Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick. Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 247–277, Cham, 2019. Springer International Publishing. https://doi.org/10.1007/978-3-030-17659-4_9.
https://doi.org/10.1007/978-3-030-17659-4_9
[6] Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick. Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 247–277, Cham, 2019. Springer International Publishing. https://doi.org/10.1007/978-3-030-17659-4_9.
https://doi.org/10.1007/978-3-030-17659-4_9
[7] Andrea Coladangelo, Koon Tong Goh, and Valerio Scarani. All pure bipartite entangled states can be self-tested. Nature Communications, 8(15485), 2017. https://doi.org/10.1038/ncomms15485.
https://doi.org/10.1038/ncomms15485
[8] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23:880, 1969. https://doi.org/10.1103/PhysRevLett.23.880.
https://doi.org/10.1103/PhysRevLett.23.880
[9] Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC ’04, pages 236–249, Washington, DC, USA, 2004. IEEE Computer Society. https://doi.org/10.1109/CCC.2004.9.
https://doi.org/10.1109/CCC.2004.9
[10] Richard Cleve, Li Liu, and William Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics, 58(012202), 2017. https://doi.org/10.1063/1.4973422.
https://doi.org/10.1063/1.4973422
[11] Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In International Colloquium on Automata, Languages, and Programming (ICALP) 2012, pages 320–331, 2012. https://doi.org/10.1007/978-3-662-43948-7_27.
https://doi.org/10.1007/978-3-662-43948-7_27
[12] Isaac Chuang and Michael Nielsen. Quantum Computation and Quantum Information. Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[13] Matthew Coudron and Anand Natarajan. The parallel-repeated magic square game is rigid. arXiv:1609.06306 [quant-ph], 2016.
arXiv:1609.06306
[14] Andrea Coladangelo. Parallel self-testing of (tilted) epr pairs via copies of (tilted) chsh. Quantum Information and Computation, 17:35, 2016.
[15] Andrea Coladangelo and Jalex Stark. Robust self-testing for linear constraint system games. In QIP 2018, 2018. https://arxiv.org/abs/1709.09267.
arXiv:1709.09267
[16] 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, STOC 2019, pages 473–480, New York, NY, USA, 2019. ACM. https://doi.org/10.1145/3313276.3316343.
https://doi.org/10.1145/3313276.3316343
[17] William Timothy Gowers and Omid Hatami. Inverse and stability theorems for approximate representations of finite groups. Sbornik: Mathematics, 208(12):1784, 2017. https://doi.org/10.1070/SM8872.
https://doi.org/10.1070/SM8872
[18] Samuel J. Harris, Satish K. Pandey, and Vern Paulsen. Entanglement and non-locality. Available at https://www.math.uwaterloo.ca/ vpaulsen/EntanglementAndNonlocality_LectureNotes_7.pdf, 2016.
https://www.math.uwaterloo.ca/~vpaulsen/EntanglementAndNonlocality_LectureNotes_7.pdf
[19] 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. Available at https://arxiv.org/pdf/1807.03332.pdf, 2018. https://doi.org/10.22331/q-2019-10-24-198.
https://doi.org/10.22331/q-2019-10-24-198
https://arxiv.org/pdf/1807.03332.pdf
[20] Matthew Mckague. Self-testing in parallel with chsh. Quantum, 1, 2016. https://doi.org/10.22331/q-2017-04-25-1.
https://doi.org/10.22331/q-2017-04-25-1
[21] N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65(27):3373, 1990. https://doi.org/10.1103/PhysRevLett.65.3373.
https://doi.org/10.1103/PhysRevLett.65.3373
[22] Dominic Mayers and Andy Yao. Self testing quantum apparatus. Quantum Info. Comput., 4(4):273–286, 2004. https://doi.org/10.1007/11786986_8.
https://doi.org/10.1007/11786986_8
[23] Matthew McKague, Tzyh Haur Yang, and Valerio Scarani. Robust self-testing of the singlet. Journal of Mathematical Physics, 45:455304, 2012. http://doi.org/10.1088/1751-8113/45/45/455304.
https://doi.org/10.1088/1751-8113/45/45/455304
[24] Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, 2008. https://doi.org/10.1088/1367-2630/10/7/073013.
https://doi.org/10.1088/1367-2630/10/7/073013
[25] Anand Natarajan and Thomas Vidick. Robust self-testing of many-qubit states. In STOC, 2017. https://doi.org/10.1038/s41534-018-0120-0.
https://doi.org/10.1038/s41534-018-0120-0
[26] Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games pcp for qma. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 731–742, 2018. https://doi.org/10.1109/focs.2018.00075.
https://doi.org/10.1109/focs.2018.00075
[27] Anand Natarajan and John Wright. Neexp in mip. ArXiv, abs/1904.05870, 2019. https://doi.org/10.1109/focs.2019.00039.
https://doi.org/10.1109/focs.2019.00039
[28] Ivan Supić and Joseph Bowles. Self-testing of quantum systems: a review. https://doi.org/10.22331/q-2020-09-30-337, 2019.
https://doi.org/10.22331/q-2020-09-30-337
[29] William Slofstra. The set of quantum correlations is not closed. Forum of Mathematics, Pi, 7:e1, 2019. https://doi.org/10.1017/fmp.2018.3.
https://doi.org/10.1017/fmp.2018.3
[30] Stephen J. Summers and Reinhard Werner. Maximal violation of bell’s inequalities is generic in quantum field theory. Comm. Math. Phys., 110(2):247–259, 1987. https://doi.org/10.1007/BF01207366.
https://doi.org/10.1007/BF01207366
[31] Boris Tsirelson. Some results and problems on quantum bell-type inequalities. Hadronis Journal Supplement, 8:320–331, 1993.
[32] Thomas Vidick. A simplified analysis on robust self-testing of $n$ epr pairs. Available at http://users.cms.caltech.edu/ vidick/, 2018.
http://users.cms.caltech.edu/~vidick/
[33] Umesh Vazirani and Thomas Vidick. Certifiable quantum dice: Or, true random number generation secure against quantum adversaries. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC ’12, pages 61–76, New York, NY, USA, 2012. ACM. https://doi.org/10.1145/2213977.2213984.
https://doi.org/10.1145/2213977.2213984
[34] Umesh Vazirani and Thomas Vidick. Fully device-independent quantum key distribution. Phys. Rev. Lett., 113:140501, Sep 2014. https://doi.org/10.1145/3310974.
https://doi.org/10.1145/3310974
[35] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. https://doi.org/10.1017/9781316848142.
https://doi.org/10.1017/9781316848142
[36] Xingyao Wu, Jean-Daniel Bancal, Matthew Mckague, and Valerio Scarani. Device-independent parallel self-testing of two singlets. Physical Review A, 93, 2015. https://doi.org/10.1103/PhysRevA.93.062121.
https://doi.org/10.1103/PhysRevA.93.062121
Cited by
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.
Source: https://quantum-journal.org/papers/q-2020-10-21-346/
