Tsirelson’s problem and an embedding theorem for groups arising from non-local games

Slofstra, William

doi:10.1090/jams/929

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