Schedule for: 19w5163 - The Many Faceted Connes Embedding Problem

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

I will review the history of Tsirelon's Problem, its relation to the NPA hierarchy, and its connection to von Neumann algebraic quantum information and quantum field theory. The main issue is how we should understand and formalize the separated labs scenario.

We will start with an expository overview of various approaches and equivalences to the Connes Embedding Problem and then focus on three of Slofstra’s contributions.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Tsirelson's problem asks a question about modeling locality in quantum mechanics; roughly speaking, whether the tensor product and commuting models for specifying bipartite correlations are equivalent. Ozawa showed that Tsirelson's problem is equivalent to Connes' Embedding Problem In the talk I will start from Tsirelson's problem and outline a possible approach to its resolution that goes through the theory of nonlocal games in quantum information and interactive proofs in complexity theory. The talk will be introductory and largely based on the work of others, including Navascues, Pironio and Acin, and Doherty, Liang, Toner, and Wehner. I will not assume any background in complexity theory.

We consider a large class of non-local games, which includes all synchronous, unique, BCS system and variable assignments games, and provide a description of various classes of perfect non-signalling strategies in terms of a C*-algebra associated with the game. We revisit the description of perfect strategies of general non-local games, and specialise it to the class of reflexive non-local games, which can be thought of as the hardest non-local games that can be won using a certain class of correlations. Finally, we provide an algebraic, Hilbert space-free approach to the description of the perfect strategies of a subclass of imitation games.

I will discuss a concrete proof that the complexity of computing the entangled value of non-local games to high precision becomes arbitrarily high as the precision becomes arbitrarily small. This contrasts sharply with the behavior of the classical value of non-local games, which can be computed precisely in exponential time with (essentially) no dependence on the precision. I will then discuss an "Algebrization Barrier" for complexity lower bounds of this sort, showing that they cannot be improved under certain conditions. This barrier happens to apply in a particularly "tight" manner to the complexity lower bound discussed in this talk, thus motivating its potential usefulness. Finally, time permitting, I will discuss how our complexity lower bound extends very naturally to the setting of zero-knowledge multi-prover interactive proofs, as well as various other connections to related work. This talk is based on joint work with William Slofstra.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

First, I will discuss the idea of compressing non-local games in order to obtain better and better lower bounds on the complexity of estimating the value of non-local games. Then, I will switch gears and give a brief overview of the concept of self-testing and rigidity in games. Finally, I will sketch how self-testing can be used to implement a compression procedure.

How much, and what sort of entanglement is needed to win a non-local game? In many ways this is the central question in the study of non-local games, and as we've seen in the previous talks, a full understanding of this question could resolve such conundrums as Tsirelson's problem, the complexity of MIP*, and Connes' embedding conjecture. One approach to this question which has proved fruitful is to design *self-tests*: games for which players who wish to play almost optimally must share a quantum state that is close to a specific entangled state. In this talk I'll present a self-test for high-dimensional maximally entangled states that is *efficient* and *robust*: to test n qubits of entanglement requires a game of poly(n) size, and the test gives guarantees even for strategies that are constant far from optimal. These properties are motivated by the complexity-theoretic goal of showing that the entangled value of a nonlocal game is strictly harder to approximate than the classical value. Based on joint work with Thomas Vidick.

One of the most confounding open problems in quantum computing is whether we can approximate the quantum value of a nonlocal game, and, if so, how quickly. So far, our progress has been dismal: in spite of decades of work on this problem, we still have not even devised a *finite* time algorithm to solve it! Recent results have hinted that this might not be due to a failing of our imagination, but rather that this problem might be intrinsically hard, even undecidable (which would imply the Connes embedding conjecture is false). Thomas Vidick showed that this problem is NP-hard, and, in follow-up work with Anand Natarajan, strengthened this lower bound to QMA-hard. In this talk, I will discuss joint work with Anand, incomparable to the QMA-hardness result, which strictly improves on Thomas' original NP-hardness result. In the language of computational complexity theory, we show that NEEXP is contained in MIP*. Our result crucially uses self-testing. in particular the quantum low-degree test introduced by Anand in his previous talk.

One promising technique for understanding features of nonlocal games is to study constraints placed on the players' measurement operators using techniques from algebraic combinatorics. In this talk, I will show an XOR game has commuting operator value 1 iff an instance of the subgroup membership problem on a finitely presented group corresponding to the game has a solution. This relationship can be used to show that the value one question is decidable for interesting sub-cases of XOR games. It also gives an algebraic framing of some open questions concerning XOR games. Based on joint work with Aram Harrow, Anand Natarajan, and Gurtej Kanwar.

I will give a treatment of tensor norms of C*-algebras and operator systems with the goal of explaining the major ideas behind Kirchberg's famous tensor product reformulation of Connes' Embedding Problem.

A quantum permutation (or magic unitary) is given by a square matrix whose entries are self-adjoint projections acting on a common Hilbert space $H$ with the property that the row and column sums each add up to the identity operator. Quantum permutations are operator-valued analogues of ordinary permutation matrices and they arise naturally in both quantum group theory and also in the study of quantum strategies for certain non-local games. From the perspective of non-local games, it is often of great importance to know whether or not a quantum permutation (possibly satisfying some additional algebraic relations among its entries) admits a matrix model. I.e., can it be realized via operators on a finite-dimensional Hilbert space $H$? In this talk, I will explain how in the case of ``generic'' quantum permutations, matrix models abound. More precisely, the universal unital $\ast$-algebra $A(N)$ generated by the coefficients of an $N\times N$ quantum permutation is always residually finite dimensional (RFD). Our arguments are based on quantum group and subfactor techniques. As an application, we deduce that the II$_1$-factors associated to quantum permutation groups satisfy the Connes Embedding Conjecture. This is joint work with Alex Chirvasitu and Amaury Freslon.

We provide a complete geometric description of the set of synchronous quantum correlations for the three experiment two outcome scenario. We show that these correlations form a closed set. Moreover, every correlation in this set can be realized using projection valued measures on a Hilbert space of dimension no more than 16. Along the way we discuss potential implications for Connes' embedding conjecture.

Following works of Evert, Helton, Klep and McCullough on free LMI domains, we ask when matrix convex sets are the closed convex hull of their Choquet points. This turns out to be a difficult problem because for certain correlation sets studied by Tsirelson (which are matrix convex sets) this question is equivalent to Connes embedding problem. In this talk I will explain how in some cases we can still provide a positive (or negative) answer to this question in matrix convexity. Our approach provides new geometric variants of Tsirelson type problems for convex polytopes, which are often related to CEP. *This is work in progress joint with Roy Araiza and Thomas Sinclair.

In this expository talk I will explain the model of multiplayer XOR games with entanglement and some connections with communication complexity and quantum query algorithms. Pertaining to these connections, I will explain the relevance of various forms of the famous Grothendieck inequality, tensor norms, and variants of the Gowers uniformity norms from additive combinatorics.

We explain embezzlement and survey some non-local games based on the idea of embezzlement. These games have the property that they have optimal strategies only in the limit of infinite entanglement.

Factorizable quantum channels, introduced by C. Anantharaman-Delaroche within the framework of operator algebras, have proven to have important applications in the analysis of quantum information theory, leading also to reformulations of the Connes Embedding Problem. I will survey these results, and address the question whether (infinite dimensional) von Neumann algebras are really needed to describe such channels.

We show that the convex set of factorizable quantum channels which factor through finite dimensional C*-algebras is non-closed in each dimension greater than 11, and that there exist factorizable quantum channels that require an ancilla of type II_1. The proof uses analysis of correlation matrices arising from projections, respectively, unitaries, in tracial von Neumann algebras. In recent work, we relate factorizable quantum channels to traces on a certain free product C*-algebra, via their Choi matrices. This new viewpoint leads to central questions in C*-algebra theory and to yet another formulation of the Connes Embedding Problem.

Free entropy is the analogue of entropy in the setting of free probability. I will take a look back at the topoloical version of free entropy based on norm-microstates. This will include a discussion of the associated topological free entropy dimension, some connections with potential theory, random matrices and some problems,

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.