Tsirelson’s problem and an embedding theorem for groups arising from non-local games
HTML articles powered by AMS MathViewer
- by William Slofstra
- J. Amer. Math. Soc. 33 (2020), 1-56
- DOI: https://doi.org/10.1090/jams/929
- Published electronically: September 27, 2019
- HTML | PDF | Request permission
Abstract:
Tsirelson’s problem asks whether the commuting operator model for two-party quantum correlations is equivalent to the tensor-product model. We give a negative answer to this question by showing that there are non-local games which have perfect commuting-operator strategies, but do not have perfect tensor-product strategies. The weak Tsirelson problem, which is known to be equivalent to the Connes embedding problem, remains open.
The examples we construct are instances of (binary) linear system games. For such games, previous results state that the existence of perfect strategies is controlled by the solution group of the linear system. Our main result is that every finitely-presented group embeds in some solution group. As an additional consequence, we show that the problem of determining whether a linear system game has a perfect commuting-operator strategy is undecidable.
References
- Alain Aspect, Philippe Grangier, and Gérard Roger, Experimental Realization of Einstein-Podolsky-Rosen-Bohm gedankenexperiment : A New Violation of Bell’s Inequalities, Physical Review Letters 49 (1982), no. 2, 91–94.
- Alex Arkhipov, Extending and Characterizing Quantum Magic Games, arXiv:1209.3819 [quant-ph].
- J. S. Bell, On the Einstein Podolsky Rosen paradox, Phys. Phys. Fiz. 1 (1964), no. 3, 195–200. MR 3790629, DOI 10.1103/PhysicsPhysiqueFizika.1.195
- A. J. Berrick, Groups with no nontrivial linear representations, Bull. Austral. Math. Soc. 50 (1994), no. 1, 1–11. MR 1285653, DOI 10.1017/S0004972700009503
- Nicolas Brunner, Stefano Pironio, Antonio Acin, Nicolas Gisin, André Allan Méthot, and Valerio Scarani, Testing the dimension of Hilbert spaces, Phys. Rev. Lett. 100 (2008), no. 21, 210503, 4. MR 2410803, DOI 10.1103/PhysRevLett.100.210503
- John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt, Proposed Experiment to Test Local Hidden-Variable Theories, Physical Review Letters 23 (1969), no. 15, 880–884.
- R. Cleve, P. Høyer, B. Toner, and J. Watrous, Consequences and limits of nonlocal strategies, 19th IEEE Annual Conference on Computational Complexity, 2004. Proceedings, 2004, pp. 236–249.
- B. S. Cirel′son, Quantum generalizations of Bell’s inequality, Lett. Math. Phys. 4 (1980), no. 2, 93–100. MR 577178, DOI 10.1007/BF00417500
- Richard Cleve, Li Liu, and William Slofstra, Perfect commuting-operator strategies for linear system games, J. Math. Phys. 58 (2017), no. 1, 012202, 7. MR 3596609, DOI 10.1063/1.4973422
- Richard Cleve and Rajat Mittal, Characterization of binary constraint system games, Automata, languages, and programming. Part I, Lecture Notes in Comput. Sci., vol. 8572, Springer, Heidelberg, 2014, pp. 320–331. MR 3238632, DOI 10.1007/978-3-662-43948-7_{2}7
- Andrea Coladangelo and Jalex Stark, Unconditional separation of finite and infinite-dimensional quantum correlations, arXiv:1804.05116.
- Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner, The quantum moment problem and bounds on entangled multi-prover games, Twenty-Third Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2008, pp. 199–210. MR 2513501, DOI 10.1109/CCC.2008.26
- Kenneth J. Dykema and Vern Paulsen, Synchronous correlation matrices and Connes’ embedding conjecture, J. Math. Phys. 57 (2016), no. 1, 015214, 12. MR 3432742, DOI 10.1063/1.4936751
- Ken Dykema, Vern I. Paulsen, and Jitendra Prakash, Non-closure of the set of quantum correlations via graphs, Comm. Math. Phys. 365 (2019), no. 3, 1125–1142. MR 3916992, DOI 10.1007/s00220-019-03301-1
- Stuart J. Freedman and John F. Clauser, Experimental Test of Local Hidden-Variable Theories, Physical Review Letters 28 (1972), no. 14, 938–941.
- Tobias Fritz, Tsirelson’s problem and Kirchberg’s conjecture, Rev. Math. Phys. 24 (2012), no. 5, 1250012, 67. MR 2928100, DOI 10.1142/S0129055X12500122
- Tobias Fritz, On infinite-dimensional state spaces, J. Math. Phys. 54 (2013), no. 5, 052107, 8. MR 3098919, DOI 10.1063/1.4807079
- Tobias Fritz, Quantum logic is undecidable, arXiv:1607.05870.
- Li Gao, Samuel J. Harris, and Marius Junge, Quantum Teleportation and Super-dense Coding in Operator Algebras, International Mathematics Research Notices (2019), rnz095.
- Samuel J. Harris, Bipartite matrix-valued tensor product correlations that are not finitely representable, arXiv:1806.08745.
- B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, and R. Hanson, Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres, Nature 526 (2015), no. 7575, 682–686.
- Graham Higman, A finitely generated infinite simple group, J. London Math. Soc. 26 (1951), 61–64. MR 38348, DOI 10.1112/jlms/s1-26.1.61
- Rudolf Haag and Daniel Kastler, An algebraic approach to quantum field theory, J. Mathematical Phys. 5 (1964), 848–861. MR 165864, DOI 10.1063/1.1704187
- Zhengfeng Ji, Binary Constraint System Games and Locally Commutative Reductions, arXiv:1310.3794 [quant-ph].
- M. Junge, M. Navascues, C. Palazuelos, D. Perez-Garcia, V. B. Scholz, and R. F. Werner, Connes embedding problem and Tsirelson’s problem, J. Math. Phys. 52 (2011), no. 1, 012102, 12. MR 2790067, DOI 10.1063/1.3514538
- M. Junge, C. Palazuelos, D. Pérez-García, I. Villanueva, and M. M. Wolf, Unbounded violations of bipartite Bell inequalities via operator space theory, Comm. Math. Phys. 300 (2010), no. 3, 715–739. MR 2736960, DOI 10.1007/s00220-010-1125-5
- Eberhard Kirchberg, On nonsemisplit extensions, tensor products and exactness of group $C^*$-algebras, Invent. Math. 112 (1993), no. 3, 449–489. MR 1218321, DOI 10.1007/BF01232444
- Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick, Entangled games are hard to approximate, SIAM J. Comput. 40 (2011), no. 3, 848–877. MR 2823510, DOI 10.1137/090751293
- Julia Kempe and Thomas Vidick, Parallel repetition of entangled games [extended abstract], STOC’11—Proceedings of the 43rd ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 353–362. MR 2931985, DOI 10.1145/1993636.1993684
- Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
- Debbie Leung, Ben Toner, and John Watrous, Coherent state exchange in multi-prover quantum interactive proof systems, Chic. J. Theoret. Comput. Sci. , posted on (2013), Article 11, 18. MR 3091714, DOI 10.4086/cjtcs.2013.011
- N. David Mermin, Simple unified form for the major no-hidden-variables theorems, Phys. Rev. Lett. 65 (1990), no. 27, 3373–3376. MR 1084329, DOI 10.1103/PhysRevLett.65.3373
- N. David Mermin, Hidden variables and the two theorems of John Bell, Rev. Modern Phys. 65 (1993), no. 3, 803–815. MR 1252609, DOI 10.1103/RevModPhys.65.803
- Laura Mančinska and Thomas Vidick, Unbounded entanglement can be needed to achieve the optimal success probability, Automata, languages, and programming. Part I, Lecture Notes in Comput. Sci., vol. 8572, Springer, Heidelberg, 2014, pp. 835–846. MR 3238674, DOI 10.1007/978-3-662-43948-7_{6}9
- M. Navascués, T. Cooney, D. Pérez-García, and N. Villanueva, A physical approach to Tsirelson’s problem, Found. Phys. 42 (2012), no. 8, 985–995. MR 2946619, DOI 10.1007/s10701-012-9641-0
- 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 (2008), no. 7, 073013.
- Narutaka Ozawa, About the Connes embedding conjecture: algebraic approaches, Jpn. J. Math. 8 (2013), no. 1, 147–183. MR 3067294, DOI 10.1007/s11537-013-1280-5
- Asher Peres, Incompatible results of quantum measurements, Phys. Lett. A 151 (1990), no. 3-4, 107–108. MR 1082070, DOI 10.1016/0375-9601(90)90172-K
- Vern I. Paulsen, Simone Severini, Daniel Stahlke, Ivan G. Todorov, and Andreas Winter, Estimating quantum chromatic numbers, J. Funct. Anal. 270 (2016), no. 6, 2188–2222. MR 3460238, DOI 10.1016/j.jfa.2016.01.010
- Vern I. Paulsen and Ivan G. Todorov, Quantum chromatic numbers via operator systems, Q. J. Math. 66 (2015), no. 2, 677–692. MR 3356844, DOI 10.1093/qmath/hav004
- Neil Robertson and Paul Seymour, Graph minors XXIII. Nash-Williams’ immersion conjecture, J. Combin. Theory Ser. B 100 (2010), no. 2, 181–205. MR 2595703, DOI 10.1016/j.jctb.2009.07.003
- Oded Regev and Thomas Vidick, Quantum XOR games, ACM Trans. Comput. Theory 7 (2015), no. 4, Art. 15, 43. MR 3414675, DOI 10.1145/2799560
- Hamish Short, Diagrams and groups, The Geometry of the Word Problem for Finitely Generated Groups, Birkhäuser Basel, Basel, 2007.
- William Slofstra, The set of quantum correlations is not closed, Forum Math. Pi 7 (2019), e1, 41. MR 3898717, DOI 10.1017/fmp.2018.3
- V. B. Scholz and R. F. Werner, Tsirelson’s Problem, arXiv:0812.4305.
- B. S. Tsirelson, Some results and problems on quantum Bell-type inequalities, Hadronic J. Suppl. 8 (1993), no. 4, 329–345. MR 1254597
- B. S. Tsirelson, Bell inequalities and operator algebras, problem statement for website of open problems at TU Braunschweig (2006), available at http://web.archive.org/web/20090414083019/http://www.imaph.tu-bs.de/qi/problems/33.html.
- Egbert R. Van Kampen, On Some Lemmas in the Theory of Groups, Amer. J. Math. 55 (1933), no. 1-4, 268–273. MR 1506963, DOI 10.2307/2371129
Bibliographic Information
- William Slofstra
- Affiliation: Institute for Quantum Computing and Department of Pure Mathematics, University of Waterloo, Canada
- MR Author ID: 841088
- Email: weslofst@uwaterloo.ca
- Received by editor(s): July 1, 2016
- Received by editor(s) in revised form: July 23, 2018
- Published electronically: September 27, 2019
- Additional Notes: This research was partially supported by NSERC grant number 2018-03968.
- © Copyright 2019 American Mathematical Society
- Journal: J. Amer. Math. Soc. 33 (2020), 1-56
- MSC (2010): Primary 20F06, 20F10, 81P40; Secondary 81P13, 81R15
- DOI: https://doi.org/10.1090/jams/929
- MathSciNet review: 4066471