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

William Slofstra

Published 2016-06-09Version 1

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 examples we construct are instances of (binary) linear system games. For such games, theorems of Cleve and Mittal and Cleve, Liu, and the author 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.