Noncommutative Nullstellensätze and Perfect Games
arXiv:2111.14928 · doi:10.1007/s00023-022-01262-1
Abstract
The foundations of classical Algebraic Geometry and Real Algebraic Geometry are the Nullstellensatz and Positivstellensatz. Over the last two decades the basic analogous theorems for matrix and operator theory (noncommutative variables) have emerged. This paper concerns commuting operator strategies for nonlocal games, recalls NC Nullstellensatz which are helpful, extends these, and applies them to a very broad collection of games. In the process it brings together results spread over different literatures, hence rather than being terse, our style is fairly expository. The main results of this paper are two characterizations, based on Nullstellensatz, which apply to games with perfect commuting operator strategies. The first applies to all games and reduces the question of whether or not a game has a perfect commuting operator strategy to a question involving left ideals and sums of squares. Previously, Paulsen and others translated the study of perfect synchronous games to problems entirely involving a -algebra.The characterization we present is analogous, but works for all games. The second characterization is based on a new Nullstellensatz we derive in this paper. It applies to a class of games we call torically determined games, special cases of which are XOR and linear system games. For these games we show the question of whether or not a game has a perfect commuting operator strategy reduces to instances of the subgroup membership problem and, for linear systems games, we further show this subgroup membership characterization is equivalent to the standard characterization of perfect commuting operator strategies in terms of solution groups. Both the general and torically determined games characterizations are amenable to computer algebra techniques, which we also develop.
arXiv comment58 pages
References in corpus (16)
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Connes' embedding problem and Tsirelson's problem
- Tsirelson's problem and Kirchberg's conjecture
- Connes' embedding conjecture and sums of hermitian squares
- Estimating quantum chromatic numbers
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Perfect Commuting-Operator Strategies for Linear System Games
- A synchronous game for binary constraint systems
- Tsirelson's Problem
- A Non-commutative Real Nullstellensatz Corresponds to a Non-commutative Real Ideal; Algorithms
- Algebras, Synchronous Games and Chromatic Numbers of Graphs
- Perfect strategies for non-signalling games
- On real one-sided ideals in a free algebra
- A generalization of CHSH and the algebraic structure of optimal strategies
- Synchronous linear constraint system games
- 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time