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

Arriving in Banff, Alberta on Sunday, July 14 and departing Friday July 19, 2019
Sunday, July 14
16:00 - 17:30 Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre)
17:30 - 19:30 Dinner
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.
(Vistas Dining Room)
20:00 - 22:00 Informal gathering (Corbett Hall Lounge (CH 2110))
Monday, July 15
07:00 - 08:45 Breakfast
Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
08:45 - 09:00 Introduction and Welcome by BIRS Staff
A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.
(TCPL 201)
09:00 - 10:00 Reinhard Werner: Tsirelson's Problem and some background
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.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:30 Vern Paulsen: Slofstra’s Contributions to the Connes Embedding Problem
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.
(TCPL 201)
11:45 - 13:15 Lunch
Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
13:00 - 14:00 Guided Tour of The Banff Centre
Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.
(Corbett Hall Lounge (CH 2110))
14:20 - 15:20 Thomas Vidick: A complexity-theoretic approach to disproving Connes' Embedding Problem
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.
(TCPL 201)
15:20 - 15:50 Coffee Break (TCPL Foyer)
15:50 - 16:35 Ivan Todorov: Perfect strategies for imitation and reflexive games
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.
(TCPL 201)
16:35 - 17:30 Matthew Coudron: On the Complexity of Entangled Non-Local Games at High Precision
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.
(TCPL 201)
17:30 - 19:30 Dinner
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.
(Vistas Dining Room)
Tuesday, July 16
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Henry Yuen: Compression of non-local games via self-testing
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.
(TCPL 201)
10:00 - 10:45 Coffee Break / Group Photo (TCPL Foyer)
10:45 - 11:45 Anand Natarajan: You must have n qubits or more to win: efficient self-tests for high-dimensional entanglement
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.
(TCPL 201)
11:30 - 13:30 Lunch (Vistas Dining Room)
14:00 - 14:45 John Wright: Nonlocal games are harder to approximate than we thought!
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.
(TCPL 201)
14:45 - 15:30 Adam Bene Watts: An Algebraic Framework for XOR Games
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.
(TCPL 201)
15:30 - 16:00 Coffee Break (TCPL Foyer)
16:00 - 17:00 Thomas Sinclair: Kirchberg's contributions to Connes' Embedding Problem
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.
(TCPL 201)
17:30 - 19:30 Dinner (Vistas Dining Room)
Wednesday, July 17
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Michael Brannan: Matrix models for quantum permutations
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.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Travis Russell: Geometry of the set of synchronous quantum correlations
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.
(TCPL 201)
11:00 - 11:30 Adam Dor-On: Matrix convexity, Choquet boundaries and Tsirelson problems
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.
(TCPL 201)
11:30 - 13:30 Lunch (Vistas Dining Room)
13:30 - 17:30 Free Afternoon (Banff National Park)
17:30 - 19:30 Dinner (Vistas Dining Room)
Thursday, July 18
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Jop Briët: Multiplayer XOR games and tensor norms
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.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:15 Richard Cleve: Embezzlement and non-local games
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.
(TCPL 201)
11:15 - 12:00 TBA (TCPL 201)
12:00 - 13:30 Lunch (Vistas Dining Room)
14:00 - 15:00 Magdalena Musat: Operator algebras meet Quantum information theory: a survey on factorizable channels and their applications
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.
(TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 16:15 45 min Slot- TBA (TCPL 201)
16:15 - 17:00 Open Problems or Discussion ?? (TCPL 201)
17:30 - 19:30 Dinner (Vistas Dining Room)
Friday, July 19
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 09:45 Mikael Rordam: A new viewpoint on factorizable maps and connections to the Connes Embedding Problem
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.
(TCPL 201)
09:45 - 10:30 Dan Voiculescu: Topological free entropy
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,
(TCPL 201)
10:30 - 11:00 Coffee Break (TCPL Foyer)
11:30 - 12:00 Checkout by Noon
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.
(Front Desk - Professional Development Centre)
12:00 - 13:30 Lunch from 11:30 to 13:30 (Vistas Dining Room)