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

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

Update to match published version, including a new background section on quantum correlation sets, fixes to the definition of pictures in Section 6 (the previous definition using smooth curves allowed some pathological behaviour), and other minor changes throughout. 66 pages, 36 figures

References in corpus (5)

• Hidden Variables and the Two Theorems of John Bell
• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Testing the Hilbert space dimension
• Connes' embedding problem and Tsirelson's problem
• Perfect Commuting-Operator Strategies for Linear System Games

Cited by in corpus (28)

• Self-testing of quantum systems: a review
• Security of device-independent quantum key distribution protocols: a review
• Bounding sets of sequential quantum correlations and device-independent randomness certification
• Graph-Theoretic Framework for Self-Testing in Bell Scenarios
• Distilling Nonlocality in Quantum Correlations
• Certifying long-range quantum correlations through routed Bell tests
• Naturally restricted subsets of nonsignaling correlations: typicality and convergence
• Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
• Operational Characterization of Multipartite Nonlocal Correlations
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• State convertibility in the von Neumann algebra framework
• Undecidability in Physics: a Review
• Many bounded versions of undecidable problems are NP-hard
• Noncommutative Nullstellensätze and Perfect Games
• Separation of quantum, spatial quantum, and approximate quantum correlations
• Unconditional quantum magic advantage in shallow circuit computation
• Quantum teleportation in the commuting operator framework
• A three-player coherent state embezzlement game
• A natural deduction system for orthomodular logic
• No quantum solutions to linear constraint systems in odd dimension from Pauli group and diagonal Cliffords
• Constant gap between conventional strategies and those based on C*-dynamics for self-embezzlement
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
• The membership problem for constant-sized quantum correlations is undecidable
• Commutative d-Torsion K-Theory and Its Applications
• The Interplay between Quantum Contextuality and Wigner Negativity
• Asymmetric graphs with quantum symmetry
• Transitive Nonlocal Games
• Uniqueness of purifications is equivalent to Haag duality