Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1606.03140 · Journal of the American Mathematical Society

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

William Slofstra

Published Jun 28, 2019• 122 citations
arXivHTMLPDF

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.

DOI
10.1090/jams/929

Related papers

THE SET OF QUANTUM CORRELATIONS IS NOT CLOSED

William Slofstra

We construct a linear system nonlocal game which can be played perfectly using a limit of finite-dimensional quantum strategies, but which cannot be played perfectly on any finite-dimensional Hilbert space, or even with any tensor-product strategy. In particular, this shows that the set of (tensor-product) quantum correlations is not closed. The constructed nonlocal game provides another counterexample to the ‘middle’ Tsirelson problem, with a shorter proof than our previous paper (though at the loss of the universal embedding theorem). We also show that it is undecidable to determine if a linear system game can be played perfectly with a finite-dimensional strategy, or a limit of finite-dimensional quantum strategies.

arXiv:1703.08618•Forum of Mathematics Pi•Jan 1, 2019•177 citations

Quantum correlation matrices and Tsirelson’s problem: Previous work and three-player considerations

Gerrit Vos

Tsirelson once claimed that the set of quantum correlations, defined by strategies of non-local two-player games, does not depend on which of two possible models is chosen: the tensor product model or the commuting operator model. He later came back from this claim, and the resulting conjecture is now known as Tsirelson’s problem. The problem has since been proven equivalent to notoriously hard problems in operator theory, such as the Connes’ Embedding Problem and the QWEP conjecture. In this master thesis, we look at the finite dimensional case of Tsirelson’s problem, working out all the details of an existing proof and giving a new, shorter proof which also extends to the nuclear case. Moreover, we give an overview of the equivalence of Tsirelson’s problem and two of Kirchberg’s conjectures, including the QWEP conjecture. Finally, we give some results and considerations for the three-player case of Tsirelson’s problem. The appendix contains proofs of many related results used throughout the thesis, and also a beginner’s introduction to quantum mechanics.

•Jan 1, 2019•0 citations

Connes’ embedding problem and winning strategies for quantum XOR games

Samuel J. Harris

We consider quantum XOR games, defined in the work of Regev and Vidick [ACM Trans. Comput. Theory 7, 43 (2015)], from the perspective of unitary correlations defined in the work of Harris and Paulsen [Integr. Equations Oper. Theory 89, 125 (2017)]. We show that the winning bias of a quantum XOR game in the tensor product model (respectively, the commuting model) is equal to the norm of its associated linear functional on the unitary correlation set from the appropriate model. We show that Connes’ embedding problem has a positive answer if and only if every quantum XOR game has entanglement bias equal to the commuting bias. In particular, the embedding problem is equivalent to determining whether every quantum XOR game G with a winning strategy in the commuting model also has a winning strategy in the approximate finite-dimensional model.

arXiv:1706.02349•Journal of Mathematical Physics•Dec 1, 2017•5 citations

Perfect commuting-operator strategies for linear system games

Richard Cleve, Li Liu, William Slofstra

Linear system games are a generalization of Mermin’s magic square game introduced by Cleve and Mittal. They show that perfect strategies for linear system games in the tensor-product model of entanglement correspond to finite-dimensional operator solutions of a certain set of non-commutative equations. We investigate linear system games in the commuting-operator model of entanglement, where Alice and Bob’s measurement operators act on a joint Hilbert space, and Alice’s operators must commute with Bob’s operators. We show that perfect strategies in this model correspond to possibly infinite-dimensional operator solutions of the non-commutative equations. The proof is based around a finitely presented group associated with the linear system which arises from the non-commutative equations.

arXiv:1606.02278•Journal of Mathematical Physics•Jan 1, 2017•47 citations

An Explicit Counterexample to Tsirelson's Problem via a Linear System Game

Minbo Gao, Tianshi Yu, Lihong Zhi

We construct an explicit binary linear system game that separates $C_{qa}$, the closure of the set of finite dimensional quantum correlations, from $C_{qc}$, the set of commuting operator correlations. The game admits a perfect commuting operator strategy, while every correlation in $C_{qa}$ has a success probability strictly less than 1. This provides a concrete counterexample to Tsirelson's problem in its approximation form. The defining system has 1417152 equations in 1889684 variables, with exactly three nonzero coefficients per equation and a single nonzero entry on the right hand side. We also compute the classical value exactly. The complete system is specified in Lean 4, and the separation and exact classical value are formalized using Mathlib.

quant-pharXiv:2610.10248•Oct 8, 2026•0 citations

Tsirelson's problems and entanglement breaking rank

Jitendra Prakash

There are two main themes of this thesis. In the first part, we study the various sets of correlations arising in the study of non-local games and Tsirelson's problems. In the second part we introduce the notion of entanglement breaking rank and study its connection with the SIC POVM existence problem. \n \nTsirelson's problems have been open for quite some time and continue to be an active area of research. These problems seek to identify relationships between different sets of quantum correlations arising from different quantum models and their relaxations. One of the goals of this thesis is to show that the set of correlations arising from the tensor product model is not topologically closed, and hence is distinct from the set of correlations arising from the commuting tensor model. \n \nWe begin our investigation in Chapter 3 by working through an example of a non-local game with three inputs and binary outputs. While this toy example does not help in showing the distinction between the aforementioned sets of correlations, it still provides valuable insights and motivation for a more abstract approach which we take up in the next chapter and which turns out to be fruitful. \n \nIn Chapter 4, we observe that given a graph we can associate functions (of a real variable) corresponding to different correlation sets. We study the properties of these functions. We show that for the complete graph on five vertices, the assumption that the correlation set obtained through tensor model is closed forces its corresponding function to be piecewise linear on an interval, while the function corresponding to the commuting model is not. This shows that the quantum correlation set is not closed hence solving one of Tsirelson's problem and also improves the results of Slofstra by reducing the number of experiments and outcomes to five and two, respectively. \n \nFinally, for the second part of the thesis, we introduce the notion of entanglement breaking rank of an entanglement breaking channel. While technically this notion is not new, this point of view helps us in showing that the entanglement breaking rank of a particular channel on $\\mathbb{M}_d$ being $d^2$ is equivalent to the existence of a SIC POVM in dimension $d$. This opens up another approach to tackle this existence problem.

•Aug 13, 2018•0 citations
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.
We construct a linear system nonlocal game which can be played perfectly using a limit of finite-dimensional quantum strategies, but which cannot be played perfectly on any finite-dimensional Hilbert space, or even with any tensor-product strategy. In particular, this shows that the set of (tensor-product) quantum correlations is not closed. The constructed nonlocal game provides another counterexample to the ‘middle’ Tsirelson problem, with a shorter proof than our previous paper (though at the loss of the universal embedding theorem). We also show that it is undecidable to determine if a linear system game can be played perfectly with a finite-dimensional strategy, or a limit of finite-dimensional quantum strategies.
Tsirelson once claimed that the set of quantum correlations, defined by strategies of non-local two-player games, does not depend on which of two possible models is chosen: the tensor product model or the commuting operator model. He later came back from this claim, and the resulting conjecture is now known as Tsirelson’s problem. The problem has since been proven equivalent to notoriously hard problems in operator theory, such as the Connes’ Embedding Problem and the QWEP conjecture. In this master thesis, we look at the finite dimensional case of Tsirelson’s problem, working out all the details of an existing proof and giving a new, shorter proof which also extends to the nuclear case. Moreover, we give an overview of the equivalence of Tsirelson’s problem and two of Kirchberg’s conjectures, including the QWEP conjecture. Finally, we give some results and considerations for the three-player case of Tsirelson’s problem. The appendix contains proofs of many related results used throughout the thesis, and also a beginner’s introduction to quantum mechanics.
We consider quantum XOR games, defined in the work of Regev and Vidick [ACM Trans. Comput. Theory 7, 43 (2015)], from the perspective of unitary correlations defined in the work of Harris and Paulsen [Integr. Equations Oper. Theory 89, 125 (2017)]. We show that the winning bias of a quantum XOR game in the tensor product model (respectively, the commuting model) is equal to the norm of its associated linear functional on the unitary correlation set from the appropriate model. We show that Connes’ embedding problem has a positive answer if and only if every quantum XOR game has entanglement bias equal to the commuting bias. In particular, the embedding problem is equivalent to determining whether every quantum XOR game G with a winning strategy in the commuting model also has a winning strategy in the approximate finite-dimensional model.
Linear system games are a generalization of Mermin’s magic square game introduced by Cleve and Mittal. They show that perfect strategies for linear system games in the tensor-product model of entanglement correspond to finite-dimensional operator solutions of a certain set of non-commutative equations. We investigate linear system games in the commuting-operator model of entanglement, where Alice and Bob’s measurement operators act on a joint Hilbert space, and Alice’s operators must commute with Bob’s operators. We show that perfect strategies in this model correspond to possibly infinite-dimensional operator solutions of the non-commutative equations. The proof is based around a finitely presented group associated with the linear system which arises from the non-commutative equations.
We construct an explicit binary linear system game that separates CqaC_{qa}Cqa​, the closure of the set of finite dimensional quantum correlations, from CqcC_{qc}Cqc​, the set of commuting operator correlations. The game admits a perfect commuting operator strategy, while every correlation in CqaC_{qa}Cqa​ has a success probability strictly less than 1. This provides a concrete counterexample to Tsirelson's problem in its approximation form. The defining system has 1417152 equations in 1889684 variables, with exactly three nonzero coefficients per equation and a single nonzero entry on the right hand side. We also compute the classical value exactly. The complete system is specified in Lean 4, and the separation and exact classical value are formalized using Mathlib.
There are two main themes of this thesis. In the first part, we study the various sets of correlations arising in the study of non-local games and Tsirelson's problems. In the second part we introduce the notion of entanglement breaking rank and study its connection with the SIC POVM existence problem. \n \nTsirelson's problems have been open for quite some time and continue to be an active area of research. These problems seek to identify relationships between different sets of quantum correlations arising from different quantum models and their relaxations. One of the goals of this thesis is to show that the set of correlations arising from the tensor product model is not topologically closed, and hence is distinct from the set of correlations arising from the commuting tensor model. \n \nWe begin our investigation in Chapter 3 by working through an example of a non-local game with three inputs and binary outputs. While this toy example does not help in showing the distinction between the aforementioned sets of correlations, it still provides valuable insights and motivation for a more abstract approach which we take up in the next chapter and which turns out to be fruitful. \n \nIn Chapter 4, we observe that given a graph we can associate functions (of a real variable) corresponding to different correlation sets. We study the properties of these functions. We show that for the complete graph on five vertices, the assumption that the correlation set obtained through tensor model is closed forces its corresponding function to be piecewise linear on an interval, while the function corresponding to the commuting model is not. This shows that the quantum correlation set is not closed hence solving one of Tsirelson's problem and also improves the results of Slofstra by reducing the number of experiments and outcomes to five and two, respectively. \n \nFinally, for the second part of the thesis, we introduce the notion of entanglement breaking rank of an entanglement breaking channel. While technically this notion is not new, this point of view helps us in showing that the entanglement breaking rank of a particular channel on mathbbMd\\mathbb{M}_dmathbbMd​ being d2d^2d2 is equivalent to the existence of a SIC POVM in dimension ddd. This opens up another approach to tackle this existence problem.