The word ‘stable’ is used to describe a situation when mathematical objects that almost satisfy an equation are close to objects satisfying it exactly. We study operator-algebraic forms of stability for unitary representations of groups and quantum synchronous strategies for non-local games. We observe in particular that simple spectral gap estimates can lead to strong quantitative forms of stability. For example, we prove that the direct product of two (flexibly) Hilbert-Schmidt stable groups is again (flexibly) Hilbert-Schmidt stable, provided that one of them has Kazhdan’s property (T). We also provide a simple form and simple analysis of a non-local game with few questions, with the property that synchronous strategies with large value are close to perfect strategies involving large Pauli matrices. This simplifies one of the steps (the question reduction) in the recent announced resolution of Connes’ embedding problem by Ji, Natarajan, Vidick, Wright and Yuen.
We review the correspondence between synchronous games and their associated
∗-algebra. Building upon the work of (Helton et al., New York J. Math. 2017), we propose results on algebraic and locally commuting graph identities. Based on the noncommutative Nullstellensätze (Watts, Helton and Klep, Annales Henri Poincaré 2023), we build computational tools that check the non-existence of perfect
C∗ and algebraic strategies of synchronous games using Gröbner basis methods and semidefinite programming. We prove the equivalence between the hereditary and
C∗ models questioned in (Helton et al., New York J. Math. 2017). We also extend the quantum-version NP-hardness reduction
3-SAT∗≤p3-Coloring∗ due to (Ji, arXiv 2013) by exhibiting another instance of such reduction
3-SAT∗≤pClique∗.
We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is
NP-complete to decide whether the classical value of a non-local game is 1 or
1−ε. Furthermore, as long as
ε is small enough, this result does not depend on the gap
ε. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap
ε decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of
MIPco(2,1,1,s) (proofs with two provers, one round, completeness probability
1, soundness probability
s, and commuting-operator strategies) can increase without bound as the gap
1−s gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class
PZK-
MIPδco(2,1,1,s) of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap
1−s gets arbitrarily small. While we do not know any computable time upper bound on the class
MIPco, a result of the first author and Vidick shows that for
s=1−1/poly(f(n)) and
δ=1/poly(f(n)), the class
MIPδco(2,1,1,s), with constant communication from the provers, is contained in
TIME(exp(poly(f(n)))). We give a lower bound of
coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.
In the past few decades, the connections between non-local games arising in quantum information theory and the theory of operator algebras have undergone a phase of significant development. Operator algebras provide a particularly fruitful framework for approaching questions of non-locality in quantum systems, as the input-output behavior of measurements on bipartite quantum systems can be encoded through noncommutative operator algebras and their state spaces. This thesis is the compilation of a series of papers, written by the author in collaboration with Ivan G. Todorov, utilizing this framework by using the theory of operator algebras and completely positive maps to study questions involving non-local games. ☐ Using the simulation paradigm from information theory, we define a quantized version of homomorphisms and isomorphisms between classical hypergraphs, generalizing quantum homomorphisms and isomorphisms of graphs from the literature. We show that these quantum homomorphisms and isomorphisms constitute pre-orders and equivalence relations, respectively. We use quantum homomorphisms of hypergraphs to provide multiple examples of strict separation between correlation classes of varying types. Specializing to the case when our underlying hypergraphs arise from classical non-local games, we define quantum non-local game homomorphisms and isomorphisms. We also show how the existence of a homomorphism or isomorphism of some fixed type between games is reflected in a comparison of optimal and asymptotic game values with respect to this type. These non-local game homomorphisms are defined via a new class of non-signalling correlations which we introduce here. We develop the multivariate tensor product theory in the category of operator systems, which we then use to provide a characterization of game homomorphisms in terms of state spaces for various tensor products of canonically associated operator systems. We then apply these results to the study of synchronous non-local games, defining jointly synchronous correlations and showing how they correspond to tracial states of tensor products of C*-algebras canonically associated to each game party. ☐ We then move to a second level of quantization by proposing a "quantized" notion of hypergraphs (where "quantum" here is in the sense of a non-commutative analogue for a discrete combinatorial object), and introduce quantum homomorphisms between these quantum objects. We provide an initial foray into the properties quantum morphisms between quantum hypergraphs display, showing they satisfy analogous properties to quantum homomorphisms between classical hypergraphs. We also indicate initial connections these quantum homomorphisms between quantum hypergraphs have to the study of quantum input-output games. We end the thesis showing that homomorphisms of a local type between quantum hypergraphs is closely related, and in some cases identical, to the TRO equivalence of finite-dimensionally acting operator spaces canonically associated with each hypergraph. This suggests a quantum information theoretic approach to Morita equivalence in the category of operator spaces.
In the work of Paulsen et al. [J. Funct. Anal. (in press); preprint arXiv:1407.6918], the concept of synchronous quantum correlation matrices was introduced and these were shown to correspond to traces on certain C*-algebras. In particular, synchronous correlation matrices arose in their study of various versions of quantum chromatic numbers of graphs and other quantum versions of graph theoretic parameters. In this paper, we develop these ideas further, focusing on the relations between synchronous correlation matrices and microstates. We prove that Connes’ embedding conjecture is equivalent to the equality of two families of synchronous quantum correlation matrices. We prove that if Connes’ embedding conjecture has a positive answer, then the tracial rank and projective rank are equal for every graph. We then apply these results to more general non-local games.
Mermin and Peres showed that there are Boolean constraint systems (BCSs) that are not satisfiable but are satisfiable with quantum observables. This has led to a burgeoning theory of quantum satisfiability for constraint systems, connected to nonlocal games and quantum contextuality. In this theory, different types of quantum satisfying assignments can be understood as representations of the BCS algebra of the system. This theory is closely related to the theory of synchronous games and algebras, and every synchronous algebra is a BCS algebra and vice versa. The purpose of this paper is to further develop the role of BCS algebras in this theory and tie up some loose ends: We give a new presentation of BCS algebras in terms of joint spectral projections and show that it is equivalent to the standard definition. We construct a constraint system that is C∗-satisfiable but not tracially satisfiable. We show that certain reductions between constraint systems lead to ∗-homomorphisms between the BCS algebras of the systems, and we use this to streamline and strengthen several results of Atserias, Kolaitis, and Severini on analogues of Schaefer’s dichotomy theorem. In particular, we show that the question of whether or not there is a nonhyperlinear group is linked to dichotomy theorems for RU-satisfiability.