<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>The Connes embedding problem: A guided tour</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>10/01/2022</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10410828</idno>
					<idno type="doi">10.1090/bull/1768</idno>
					<title level='j'>Bulletin of the American Mathematical Society</title>
<idno>0273-0979</idno>
<biblScope unit="volume">59</biblScope>
<biblScope unit="issue">4</biblScope>					

					<author>Isaac Goldbring</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[The Connes embedding problem (CEP) is a problem in the theory of tracial von Neumann algebras and asks whether or not every tracial von Neumann algebra embeds into an ultrapower of the hyperfinite II                                                                                                                1                                        _1                                                              factor. The CEP has had interactions with a wide variety of areas of mathematics, including                                                                                                                  C                                                                    ∗                                                                                      \mathrm {C}^*                                                              -algebra theory, geometric group theory, free probability, and noncommutative real algebraic geometry, to name a few. After remaining open for over 40 years, a negative solution was recently obtained as a corollary of a landmark result in quantum complexity theory known as                                                                                                                  MIP                                                  ∗                                                                                              =                      RE                                        \operatorname {MIP}^*=\operatorname {RE}                                                              . In these notes, we introduce all of the background material necessary to understand the proof of the negative solution of the CEP from                                                                                                                  MIP                                                  ∗                                                                                              =                      RE                                        \operatorname {MIP}^*=\operatorname {RE}                                                              . In fact, we outline two such proofs, one following the “traditional” route that goes via Kirchberg’s QWEP problem in                                                                                                                  C                                                                    ∗                                                                                      \mathrm {C}^*                                                              -algebra theory and Tsirelson’s problem in quantum information theory and a second that uses basic ideas from logic.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">Introduction</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.1.">What is this all about?</head><p>The story told in this tour is (in this author's humble opinion) absolutely fascinating! It can also be completely confusing and terrifying to an outsider. It contains a seemingly infinite number of acronyms (CEP, WEP, QWEP, LLP, MIP*, RE, . . . ), all sorts of tensor products p b, b max , b min q, entangled particles, and even good friends Einstein and G&#246;del both make an appearance (the latter twice).</p><p>At one end of the story is the Connes embedding problem (CEP), a problem in the field of von Neumann algebras first posed by Alain Connes in his famous 1976 paper "Classification of Injective Factors" <ref type="bibr">[15]</ref> (the paper mainly responsible for his being awarded the Fields Medal in 1982). Roughly speaking, a von Neumann algebra is a collection of bounded operators on a Hilbert space containing the identity operator, closed under addition, composition, scalar multiplication, and adjoint, and which is closed in a certain topology known as the weak operator topology. The von Neumann algebras Connes was considering came equipped with a trace functional that shares many of the nice properties enjoyed by the (normalized) trace functional on matrices.</p><p>Here is the passage from <ref type="bibr">[15]</ref> which led to the establishment of the CEP:</p><p>We now construct an approximate imbedding of N in R. Apparently such an imbedding ought to exist for all II 1 factors because it does for the regular representation of free groups. However, the construction below relies on condition 6.</p><p>What is this quote trying to convey? R is the hyperfinite II 1 factor, arguably the most important tracial von Neumann algebra. For now, one should just think of R as an appropriate limit of matrix algebras M n pCq of increasing sizes. We will have much to say about this algebra throughout this paper. A II 1 factor is just a particular kind of tracial von Neumann algebra, and the N appearing in the passage is a particular II 1 factor satisfying a certain list of properties. By an approximate imbedding of N in R, Connes means that any finite amount of information about elements of N (that is, the trace of finitely many &#730;-polynomials with elements from N plugged in) can be simulated by appropriate elements of R. Connes later shows that such approximate imbeddings correspond to actual embeddings of N into a socalled ultrapower of R, denoted R U . He comments that such an embedding "ought" to always exist since it does for a particular von Neumann algebra, namely the group von Neumann algebra associated to the free group, denoted LpF 2 q (see Subsection 3.7). Why that embedding "ought to exist" is not quite clear. Nevertheless, Connes is only able to show that the N under consideration can be embedded in R U using one of the conditions (namely the sixth one) he has assumed about this particular algebra.</p><p>Thus, the Connes embedding problem (CEP) states: every tracial von Neumann algebra embeds (in a trace-preserving way) in an ultrapower R U of R. We will say this slightly more precisely in Subsection 3.6. Many prefer to call this a "problem" rather than a "conjecture" since "ought to" is not a very strong sentiment.</p><p>The robustness of the CEP lies in its many reformulations and from the many areas of mathematics it has touched upon; see Section 2 for some examples.</p><p>At the other end of this story (and seemingly a world far, far away) is a landmark theorem in quantum complexity theory known as MIP &#730;" RE <ref type="bibr">[39]</ref>. Like most theorems in complexity theory, it compares two complexity classes. Roughly speaking, a complexity class consists of a collection of problems that all share some common level of difficulty with which one can solve or verify these problems. The class RE denotes those problems for which there is a computer program so that, if you left the program running long enough, would list all instances for which the problem has a positive answer (but you would never know about instances with a negative answer). Usually, complexity theorists are more interested in levels of efficiency, and the class RE is hardly ever discussed. The other complexity class in the above equation is MIP &#730;, which denotes those problems for which a verifier interacting with multiple cooperating (but noncommunicating) provers who share a source of quantum entanglement can reliably verify a positive instance of a problem. The result MIP &#730;" RE states that these two classes coincide! This is a monumental result, for it shows the power of quantum ideas in computational complexity. One particular instance of this result is that the (in)famous halting problem, which asks if a particular computer program will halt on, say, the empty input (which is known to be an undecidable problem), can actually be efficiently and reliably verified by two provers sharing some quantum entanglement. Here, "efficiently" means in polynomial time and "reliably" means that if the machine halts, then the verifier will accept the provers' proof of that fact with probability 1, while if it does not halt, then only half the time will they accept a (necessarily incorrect) proof purporting to show that the machine halts. (An execution of the protocol has a probabilistic outcome, whence here the condition is that there is acceptance with probability at most 1  2 over the verifiers' and provers' random choices in the case of a Turing machine that does not halt. If making a mistake half of the time seems unacceptable, the reader will find comfort in knowing that the chance of mistake can be made as close to 0 as one wishes upon repetition of the protocol.) This is an astounding result! Even more amazing than the sheer statement of the result is that the equality MIP &#730;" RE actually yields a negative solution to CEP! 1.2. Connecting the dots. But how could these seemingly unrelated topics be so tightly connected? The answer lies within a series of previously known connections. First, in a fundamental paper of Kirchberg <ref type="bibr">[44]</ref>, it was shown that CEP is equivalent to an important problem (Kirchberg even used the word conjecture) in the theory of C &#730;-algebras stemming from the complexity of C &#730;-tensor products known now as Kirchberg's QWEP problem (see <ref type="bibr">Subsection 3.8)</ref>. Later, Fritz <ref type="bibr">[24]</ref> and, independently, Junge et al. <ref type="bibr">[41]</ref> demonstrated that a positive answer to the QWEP problem would yield a positive answer to a problem in quantum information theory known as Tsirelson's problem which, roughly speaking, asks whether the usual quantum mechanical framework and that coming from quantum field theory yield the same set of quantum correlations corresponding to Bell experiments. While the jump from the QWEP problem to Tsirelson's problem might seem like quite a leap, once one unravels the definitions, this is actually a fairly straightforward argument, which will be given in Subsection 6.1. Both sets of authors almost proved that the Kirchberg and Tsirelson problems were actually equivalent; Ozawa succeded in connecting the last dots in <ref type="bibr">[47]</ref>.</p><p>Now we are at least in the same arena: quantum information theory and quantum complexity theory (both areas at least have "quantum" in their names). The last step in the puzzle is to use a result of Fritz, Netzer, and Thom <ref type="bibr">[25]</ref> about the computability of the operator norm for universal group C &#730;-algebras and the analysis leading to the equivalence of QWEP and Tsirelson to show that if Tsirelson's problem has a positive answer, then every language in MIP &#730;would actually be decidable, contradicting MIP &#730;" RE. (See Subsection 6.1 for the complete argument.)</p><p>Okay, so that was a mouthful! 1.3. Why another treatment of CEP? Numerous accounts of the CEP and its many equivalents can be found in the literature. In fact, Pisier <ref type="bibr">[52]</ref> recently wrote a fascinating account (coming in just shy of 500 pages) on the CEP and its equivalences with QWEP and Tsirelson (and so, so much more). Much trimmer accounts were given by Ozawa <ref type="bibr">[47,</ref><ref type="bibr">48]</ref> and Capraro and Lupini <ref type="bibr">[13]</ref>.</p><p>So if there are so many accounts of the CEP, why write another? We have several good reasons:</p><p>First, all of the above accounts were written pre-MIP &#730;" RE, so none of them actually explain how the story resolves itself.</p><p>Second, all of the above accounts go into an extreme amount of detail and assume a fair amount of background knowledge in operator algebras. We envision the reader in, say, quantum physics or complexity theory wanting to understand the main thread of the story and being overburdened by the overhead needed to enter the fray. In this survey, we try very hard to at least state all of the necessary definitions. On the other hand, we offer very few details or proofs in the interest of space and refer the reader to the above references if they are interested in the gritty details. Also, since we are focusing on the one-way implications (as opposed to the equivalences the other accounts present), we save ourselves some complications.</p><p>Third, the operator algebra community may know very little quantum theory or complexity theory, so we offer brief introductions to these areas to at least paint the picture for them.</p><p>Finally, and most certainly gratuitously, we offer an alternative and, in this author's biased opinion, simpler path from MIP &#730;" RE to the failure of CEP than that outlined above using basic methods from mathematical logic. This path also offers some extra bells and whistles to the failure of CEP, including a G&#246;delian refutation of the CEP and a proof of the existence of many counterexamples to the CEP. While we have our logician hats on, we take advantage of the fact that we have the readers' attention to describe a model-theoretic weakening of the CEP that is still open and quite fascinating (at least to us!). <ref type="bibr">1.4</ref>. A quick guide to this guide. In Section 2, we briefly describe some of the known equivalents of the CEP. The reader may benefit from coming back to this section after having read some of the definitions, but this is supposed to whet the reader's appetite and convince them that the rest of the paper is worth reading.</p><p>Section 3 is a crash course in operator algebras, assuming some basic functional analysis that someone in quantum physics should probably be familiar with. We cover both the C &#730;and von Neumann algebra background needed as well as topics such as states and traces, the ultrapower construction, operator algebras arising from groups, and finally, what is so darn complicated about C &#730;-algebra tensor products, culiminating in a discussion of why a positive solution to the CEP implies a positive solution to the QWEP problem.</p><p>Section 4 is a similar crash course but this time in complexity theory. We start from the definition of Turing machines, defining some of the basic complexity classes, and then work our way up to the class MIP of languages verifiable by a verifier interacting with multiple cooperating provers.</p><p>In Section 5, we make a quantum detour for those unfamiliar with the basic tenets of quantum mechanics and even take a digression on superdense coding just for fun (and to indicate the power of entanglement). This section culminates with the definition of the complexity class MIP &#730;, the analogue of MIP where the provers are allowed to share quantum entanglement as a resource, and the precise statement of the result MIP &#730;" RE.</p><p>Section 6 contains the details of the proof of the failure of the QWEP problem from MIP &#730;" RE by first showing how the latter yields a negative solution to Tsirelson's problem and then by establishing how a negative solution to Tsirelson's problem yields a negative solution to the QWEP problem. Combined with our derivation of a positive solution of the QWEP problem from a positive solution to the CEP, this completes the proof of the negative solution to the CEP from MIP &#730;" RE.</p><p>Section 7 offers the alternative proof alluded to above using basic ideas from logic. We present the appropriate logic for studying tracial von Neumann algebras and discuss the main contribution from logic, namely G&#246;del's completeness theorem. We also describe the extra information about the CEP gleamed from the logical perspective mentioned above, including a completely operator-algebraic reformulation of our main model-theoretic contribution in terms of the undecidability of a certain moment approximation problem. We also offer an alternative proof of the failure of Tsirelson from MIP &#730;" RE using the completeness theorem. Most of the material in this section represents joint work with Bradd Hart <ref type="bibr">[31,</ref><ref type="bibr">32]</ref>.</p><p>Finally, in Section 8, we discuss the open problem around the existence of the so-called enforceable factor, which is the model-theoretic weakening of the CEP referred to above.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Equivalent reformulations of CEP</head><p>One of the aspects of the CEP that makes it such an interesting problem is its numerous equivalences spanning many seemingly different areas of mathematics. In the main text, the equivalences with Kirchberg's QWEP conjecture in C &#730;-algebra theory and Tsirelson's problem in quantum information theory will be expounded on in more detail due to their relevance to the current story. In this section, we briefly mention some of the other well-known equivalences.</p><p>2.1. Free probability theory. In free probability theory, one considers noncommutative probability spaces, such as tracial von Neumann algebras pM, &#964; q, where the elements of M act as noncommutative random variables and the trace &#964; is the analogue of the integral. Voiculescu demonstrated the robustness of this theory, establishing free analogues of many familiar facts from ordinary probability theory and giving applications to operator algebras and random matrices (to name a few). A nice introduction to free probability is Speicher's lecture notes <ref type="bibr">[57]</ref>.</p><p>In classical probability theory, the entropy of a random variable is an important numerical value measuring the amount of information obtained when measuring the random variable. One method of calculating the entropy of a discrete random variable with probability distribution tp 1 , . . . , p n u is to approximate the distribution using microstates, which are functions f : t1, . . . , Nu &#209; t1, . . . , nu for which the fraction of j P t1, . . . , Nu, where f pjq " k is within of p k for all k " 1, . . . , n. By taking the logarithm of the number of such functions divided by N for a given pair pN, q of parameters and then letting N &#209; 8 and &#209; 0, we obtain the entropy Hpp 1 , . . . , p n q of the distribution. A more general version of this works for a wider class of random variables.</p><p>When faced with the task of defining the free entropy of a tuple pa 1 , . . . , a n q of self-adjoint elements in a tracial von Neumann algebra pM, &#964; q, Voiculescu proceeds analogously by considering those tuples pA 1 , . . . , A n q of self-adjoint matrices in some matrix algebra M k pCq for which a certain finite number of moments approximate the corresponding moments in the tracial von Neumann algebra; that is, &#964; pppa 1 , . . . , a n qq and trpppA 1 , . . . , A n qq differ by at most for finitely many noncommutative &#730;-polynomials ppX 1 , . . . , X n q in n-variables. Now one has to calculate the volume of the set of those matrices and let the various parameters involved tend to infinity or 0. With this definition of free entropy, one can prove a number of results which are the free analogues of the corresponding result in the classical theory. For example, it is known that a tuple of classical random variables has maximal entropy if and only if they are independent and have Gaussian distribution. In the free theory, the free entropy of a tuple is maximal if and only if the elements of the tuple are freely independent and have semicircular distributions (which are known to be the free analogue of the Gaussian distribution). The paper <ref type="bibr">[63]</ref> is a survey of free entropy by Voiculescu himself.</p><p>This definition of free entropy leads to an interesting feature: if there are no such tuples pA 1 , . . . , A n q that simulate pa 1 , . . . , a n q, then the free entropy of pa 1 , . . . , a n q equals &#180;8. It is well-known (see Subsection 3.6) that, for a given tracial von Neumann algebra pM, &#964; q, the set of such moments is nonempty for all such tuples pa 1 , . . . , a n q from M if and only if M embeds into R U (in a trace-preserving way). Thus, CEP is equivalent to all tuples of self-adjoint elements in tracial von Neumann algebras having nonnegative free entropy.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.2.">Hyperlinear groups.</head><p>Okay, so this one really is not an equivalence but rather an equivalence with a special case of the CEP. An important notion in group theory is that of a sofic group. Roughly speaking, a countable discrete group G is sofic if, for every finite subset F of G, there is a symmetric group S n and a function &#966; : F &#209; S n that is an approximately injective approximate homomorphism. For example, if g, h, gh P F , then one would like to say that &#966;pghq is close to &#966;pgq&#966;phq, where closeness is measured with respect to the normalized Hamming distance between permutations (which calculates what fraction of elements the permutations disagree on). The importance of this class of groups is that many important conjectures in group theory are known to hold when restricted to the class of sofic groups. Surprisingly, there is no known example of a nonsofic group! One can make a similar definition, replacing symmetric groups S n with unitary groups U n , equipped with their normalized Hilbert-Schmidt metric; the resulting class of groups is called the class of hyperlinear groups. Every sofic group is hyperlinear, and since we do not know if every group is sofic, we do not know if this inclusion is proper. Moreover, there is no known example of a nonhyperlinear group. We refer the reader to <ref type="bibr">[13]</ref> for more information on sofic and hyperlinear groups.</p><p>The connection with CEP comes via an observation of Radulescu <ref type="bibr">[53]</ref>, who showed that G is hyperlinear if and only if the group von Neumann algebra LpGq of G (see Subsection 3.7) embeds into R U . In other words, if CEP is true just for group von Neumann algebras, then every group is hyperlinear! Interestingly enough, even though we now know that CEP is false, we still do not know if its special case for group von Neumann algebras holds; that is, we still do not know if every group is hyperlinear.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.3.">Embeddability of general von Neumann algebras.</head><p>The CEP is about tracial von Neumann algebras. But there is a much wider class of von Neumann algebras out there. Is there a reformulation of the CEP that addresses them? The answer is yes, and it was established by Ando, Haagerup, and Winslow in <ref type="bibr">[1]</ref>. There is a so-called type III (in the sense of Subsection 3.5) version of R, called the Araki-Woods factor R 8 , which is the unique hyperfinite type III 1 factor. Moreover, there is a generalization of the tracial ultraproduct construction, known as the Ocneanu ultraproduct, that covers the much larger class of &#963;-finite von Neumann algebras, of which R 8 is one of them. The main result of <ref type="bibr">[1]</ref> states that CEP is equivalent to the assertion that every separably acting von Neumann algebra embeds with expectation into the Ocneanu ultrapower R U 8 . The notion of an embedding with expectation is defined in Subsection 3.9. In the case of tracial von Neumann algebras, the embedding is automatically with expectation, but in the general case, it is a necessary nontriviality condition. </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.5.">Noncommutative real algebraic geometry.</head><p>A Positivstellensatz is a theorem that declares that certain elements that are positive in some way are so for some good reason. Perhaps the best-known such result is the positive solution to Hilbert's 17th Problem, due to Artin <ref type="bibr">[2]</ref> (although this author is unabashedly fond of Abraham Robinson's model-theoretic solution <ref type="bibr">[54]</ref>): if f pX 1 , . . . , X n q P RpX 1 , . . . , X n q is a positive semidefinite rational function (that is, a rational function such that f px 1 , . . . , x n q &#283; 0 for all x 1 , . . . , x n P R), then f is a sum of squares of rational functions, providing a good reason that f is positive semidefinite.</p><p>One can ponder noncommutative versions of Artin's theorem. First, we set RxX 1 , . . . , X n y to be the set of polynomials in n noncommuting variables. Consider the positivity statement that f pA 1 , . . . , A n q &#283; 0 for all self-adjoint matrices A 1 , . . . , A n P M m pRq of operator norm at most 1, for all m P N. Then a theorem of <ref type="bibr">Helton and McCullough [36]</ref> tells us that there is a good reason for this kind of positivity, namely that, for all P R &#261;0 , f ` belongs to the quadratic module generated by 1 &#180;X2 i , i " 1, . . . , n. Here, a quadratic module is a subset M of RxX 1 , . . . , X n y containing 1, closed under addition and closed under the function a &#222; &#209; g &#730;ag, where a P M and g P RxX 1 , . . . , X n y (and where g &#730;is the result of reversing the orders of the variables in each monomial of g). Note indeed that all functions in the quadratic module generated by the 1&#180;X 2 i 's must be positive in the above sense, and the Helton-McCullough result says that this is (approximately) the good reason that any such noncommutative polynomial might be positive. Now suppose instead that we assume that f is merely trace positive, that is, trpf pA 1 , . . . , A n qq &#283; 0 for all such A 1 , . . . , A n as in the previous paragraph. Clearly, the operators in the Helton and McCullough result are trace positive. But now you can also add finite sums of commutators rA, Bs :" AB &#180;BA since the trace of a commutator vanishes. One can ask if this new class of noncommutative polynomials gives a necessary and sufficient condition to be trace positive; that is, if f is tracially positive, must it be the case that, for every &#261; 0, f ` differs from an element of the quadratic module generated by the 1 &#180;X2</p><p>i 's by a sum of commutators? It turns out that this tracial version of the Positivstellensatz from the previous paragraph is actually equivalent to the CEP, a result proven by Klep and Schweighofer in <ref type="bibr">[45]</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">A crash course in operator algebras</head><p>In this long section, we explain all of the background material in operator algebras one needs to know to understand the statements of both the CEP and the QWEP problem as well as to understand how a positive solution to the former implies a positive solution to the latter. Nearly everything discussed here can be found in Pisier's book <ref type="bibr">[52]</ref>. Brown and Ozawa's book <ref type="bibr">[12]</ref> is another nice reference.</p><p>3.1. Introducing C &#730;-algebras. A &#730;-algebra is an algebra A over C satisfying, for all x, y P A and &#955; P C,</p><p>If A is actually a unital algebra over C with unit 1 for which 1 &#730;" 1, we say that A is a unital &#730;-algebra. There are obvious notions of &#730;-subalgebra of a &#730;-algebra and unital &#730;-subalgebra of a unital &#730;-algebra.</p><p>A &#730;-homomorphism between &#730;-algebras is an algebra homomorphism that also preserves the &#730;-operation. If &#966; : A &#209; B is a &#730;-homomorphism between unital &#730;-algebras, then we implicitly assume that &#966; maps the unit of A to the unit of B.</p><p>In this paper, the most relevant (unital) &#730;-algebras are BpHq, the &#730;-algebra of bounded operators on the Hilbert space H, and its (unital) &#730;-subalgebras. Recall that for a Hilbert space H, a linear operator T : H &#209; H is bounded if its operator norm }T } :" supt}T &#958;} : }&#958;} &#271; 1u is finite. BpHq is a &#730;-algebra with the algebra operations being addition, composition, and scalar multiplication and with the &#730;operation being given by the adjoint, where, for T P BpHq, we have that T &#730;P BpHq is the unique operator for which xT &#958;, &#951;y " x&#958;, T &#730;&#951;y for all &#958;, &#951; P H. (In connection with this formula, we follow the convention that inner products are linear in the first argument and conjugate-linear in the second argument; this is the opposite of the convention used in the physics literature.) BpHq is a unital &#730;-algebra with identity operator I H acting as the unit.</p><p>We now define our first class of operator algebras, namely the class of C &#730;algebras. For both classes of operator algebras, there are two approaches to their definition, namely the concrete and the abstract. A concrete C &#730;-algebra is a &#730;-subalgebra A of BpHq that is closed in the operator norm topology. If, moreover, A contains the identity I H , then we say that A is a unital concrete C &#730;-algebra.</p><p>We now present the abstract approach to C &#730;-algebras. Suppose that A is a &#730;-algebra. A C &#730;-norm on A is a norm on A satisfying the following identities for all x, y P A:</p><p>The first two identities are the usual axioms for defining a normed &#730;-algebra; the last axiom, called the C &#730;-identity, is what makes a C &#730;-norm a C &#730;-norm. An abstract C &#730;-algebra is a &#730;-algebra equipped with a complete C &#730;-norm. If A is a &#730;-algebra equipped with a C &#730;-norm, then the &#730;-algebra operations extend naturally to the completion of the &#730;-algebra, which is then an abstract C &#730;-algebra. An abstract unital C &#730;-algebra is an abstract C &#730;-algebra that is a unital *-algebra; in this case, we have }1} " 1.</p><p>It is an important fact that a &#730;-homomorphism between abstract C &#730;-algebras is necessarily contractive; it is an isometric embedding if and only if it is injective. In particular, given any &#730;-algebra A, there is at most one norm on A which makes A into a C &#730;-algebra.</p><p>It is an easy exercise to see that the operator norm on BpHq is a C &#730;-norm, whence every concrete C &#730;-algebra is an abstract C &#730;-algebra. On the other hand, the Gelfand-Naimark theorem states that every abstract C &#730;-algebra is isomorphic (as abstract C &#730;-algebras) to a concrete C &#730;-algebra. This result can be reformulated in terms of representations of C &#730;-algebras. Given a C &#730;-algebra A, a representation of A is a &#730;-homomorphism &#960; : A &#209; BpHq for some Hilbert space H. Usually a nondegeneracy condition is assumed on a representation, namely that t&#960;paqp&#958;q : a P A, &#958; P Hu is dense in H; if A is unital, this is equivalent to assuming that &#960;p1q " I H . The representation &#960; is faithful if it is moreover injective (equivalently isometric). Thus, the Gelfand-Naimark theorem states that every abstract C &#730;-algebra admits a faithful representation.</p><p>From here on out, we no longer make a distinction between concrete and abstract C &#730;-algebras and simply take either perspective whenever it is convenient.</p><p>Unless stated otherwise, in the rest of this paper, we restrict our attention to unital C &#730;-algebras; we might often repeat this convention for emphasis.</p><p>A C &#730;-algebra is commutative (or abelian) if its multiplication is commutative. Given a compact Hausdorff space X, the set CpXq of continuous, complex-valued functions is a unital commutative C &#730;-algebra under the pointwise operations of addition, multiplication, and scalar multiplication, with the &#730;-operation being given by f &#730;:" f (complex conjugate), and with norm given by }f } :" sup xPX |f pxq|. In fact, all unital commutative C &#730;-algebras are of this form, and there is a dual equivalence of categories (known as Gelfand duality) between compact Hausdorff spaces with continuous maps and unital commutative C &#730;-algebras with &#730;-homomorphisms. For this reason, C &#730;-algebra theory is often dubbed "noncommutative topology."</p><p>There are special kinds of elements in C &#730;-algebras that will be important throughout this paper. If A is a C &#730;-algebra, x P A is called</p><p>In the case that A " BpHq, the self-adjoint (resp., positive) elements are those with spectrum contained in the reals (resp., the positive reals) while the projections correspond to orthogonal projections onto closed subspaces. In the case that A " CpXq for X a compact space, the self-adjoint (resp., positive) elements correspond to the real-valued (resp., positive real-valued) functions while the projections correspond to those functions which take only the values 0 or 1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>3.2.</head><p>Let's be positive. An important role in this story is played by maps between C &#730;-algebras which are not necessarily &#730;-homomorphisms but which still preserve some remnants of the C &#730;-algebra structure. It is hard to truly appreciate the importance of these maps without getting into the details of the results to follow, but we introduce the terminology in order to be able to follow the definitions and theorems.</p><p>First, we say that a linear map &#966; : A &#209; B between C &#730;-algebras is positive if it maps positive elements to positive elements. Note that a &#730;-homomorphism is positive: &#966;pa &#730;aq " &#966;paq &#730;&#966;paq.</p><p>For many purposes, a stronger version of positivity is needed. First, for any C &#730;-algebra A and any n &#283; 1, we let M n pAq denote the set of n &#710;n matrices with entries from A. We can view M n pAq as a &#730;-subalgebra of Bp &#192; n i"1 Hq and it is readily verified that, under this identification, M n pAq is closed in the operator norm topology, that is, M n pAq is a C &#730;-algebra once again. Note also that a linear map &#966; : A &#209; B induces a linear map &#966; n : M n pAq &#209; M n pBq given by &#966; n pa ij q " p&#966;pa ij qq. We say that &#966; is completely positive (cp) if each &#966; n is a positive map. If, in addition, &#966;p1q " 1, we say that &#966; is unital, completely positive (ucp). A &#730;-homomorphism &#966; : A &#209; B is easily seen to induce &#730;-homomorphisms &#966; n : M n pAq &#209; M n pBq, whence &#730;-homomorphisms are ucp. It can be shown that if A is commutative, then any positive map &#966; : A &#209; B is automatically completely positive.</p><p>In a similar vein, one says that &#966; as above is completely bounded (resp., completely contractive) if each &#966; n is bounded (resp., contractive).</p><p>A fundamental theorem of Stinespring says that ucp maps are not too far away from being &#730;-homomorphisms. More precisely, consider the following situation: suppose that H and K are Hilbert spaces and V : H &#209; K is an isometry, that is, a linear map for which V &#730;V " I H (or, in other words, xV &#958;, V &#958;y " x&#958;, &#958;y for all &#958; P H). Then for any representation &#960; : A &#209; BpKq of A, we have a map &#966; : A &#209; BpHq given by &#966;paqp&#958;q :" V &#730;p&#960;paqpV &#958;qq which is readily verified to be ucp. The Stinespring dilation theorem says that all ucp maps &#966; : A &#209; BpHq arise in this way. A particular consequence of this theorem is that ucp maps are completely contractive. The relevance of Stinespring's theorem to our story is that certain results that hold somewhat immediately for &#730;-homomorphisms will also hold for ucp maps (see <ref type="bibr">Subsection 3.8)</ref>.</p><p>We mention in passing that cp maps play an important role in quantum information theory. Indeed, one perspective on a quantum state (say on a finite-dimensional state space) is that of a positive matrix of trace 1, corresponding to the density matrix of some mixed state. A quantum channel is a linear map that is to represent some allowable physical transformation on quantum states. In particular, if it is to map density matrices to density matrices, then it should be trace-preserving and positive. However, often one needs to add ancilla bits to a given state and then apply the correspondiing quantum channel. The desire to have the resulting matrix be a density matrix again is equivalent to the requirement that the quantum channel be completely positive instead of merely positive. The reader can find more details in, for example, Vern Paulsen's lecture notes <ref type="bibr">[50]</ref> Von Neumann's bicommutant theorem allows for a purely algebraic reformulation of being a von Neumann algebra that is incredibly important to the theory. First, given a subset S &#270; BpHq, set S 1 :" tT P BpHq : T S " ST for all S P Su, the socalled commutant of S. Note that for any set S, we have that S 1 is a von Neumann subalgebra of BpHq and that S &#270; S 2 :" pS 1 q 1 . Von Neumann's bicommutant theorem states that for any unital &#730;-subalgebra A of BpHq, A 2 coincides with the WOTclosure of A in BpHq; this common algebra is the von Neumann algebra generated by A. In fact, the bicommutant theorem shows that both of these coincide with the closure of A in the strong operator topology (SOT), where now a subbasic open neighborhood of T P BpHq in the SOT has the form tS P BpHq : }pT &#180;Sq&#958;} &#259; u for some &#958; P H and some &#261; 0. A consequence of the bicommutant theorem is that a unital &#730;-subalgebra M of BpHq is a von Neumann algebra if and only if M " M 2 .</p><p>A von Neumann algebra M is called separable if its bidual is a separable Banach space. This is equivalent to having a concrete representation of M on a separable Hilbert space, whence one sometimes calls such a von Neumann algebra separably acting.</p><p>Just as in the case of C &#730;-algebras, we can completely characterize the commutative von Neumann algebras. Given a &#963;-finite measure space pX, &#956;q, we can view L 8 pX, &#956;q &#270; BpL 2 pX, &#956;qq by identifying f P L 8 pX, &#956;q with M f P BpL 2 pX, &#956;qq given by M f pgq :" fg. It is an exercise to check that L 8 pX, &#956;q " L 8 pX, &#956;q 1 , whence L 8 pX, &#956;q is a commutative von Neumann algebra. Moreover, all commutative von Neumann algebras have this form, whence von Neumann algebra theory is often dubbed "noncommutative measure theory."</p><p>While &#730;-homomorphisms between von Neumann algebras are automatically contractive with respect to the operator norm (as they are C &#730;-algebras), since the relevant topology for defining von Neumann algebras is the WOT, the appropriate continuity condition relates to this latter topology. More precisely, a positive linear map &#934; : M &#209; N between von Neumann algebras is normal if the restriction of &#934; to the operator norm unit ball of M is continuous when M and N are equipped with their WOT topologies. (The restriction to the operator norm unit ball may seem slightly unsightly; this is equivalent to saying that &#934; is continuous when both M and N are equipped with their weak*-topologies when viewed as dual Banach spaces.) One can reformulate normality in an intrinsic way that does not refer to the particular realization of M and N: &#934; : M &#209; N is normal if and only if it is positive, linear, and &#934;psup iPI x i q " sup iPI &#934;px i q for every bounded increasing net px i q iPI of positive elements in M.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>3.4.</head><p>States and traces. Fix a compact Hausdorff space X. Given a complex Borel measure &#956; on X, we can consider the associated integration functional I &#956; P CpXq given by I &#956; pf q :" &#351; X fd&#956; which satisfies }I &#956; } " }&#956;}, where }&#956;} denotes the total variation norm of &#956;. Setting M pXq to be the Banach space of complex Borel measures on X, the Riesz representation theorem implies that this association yields an isomorphism CpXq &#730;-M pXq. Moreover, the probability measures &#956; on X correspond to those I P CpXq &#730;for which I is a positive map satisfying Ip1q " 1.</p><p>More generally, given a unital C &#730;-algebra A, a state on A is a positive linear functional &#966; on A with &#966;p1q " 1. Thus, the states on a unital abelian C &#730;-algebra CpXq correspond to the integration functionals associated to probability measures on X, and one thinks of states on arbitrary C &#730;-algebras as the abstract analogue of such an integral.</p><p>The states on A form a convex, closed subset SpAq of A &#730;. The extreme points of SpAq are referred to as pure states. By the Krein-Milman theorem, finite convex combinations of pure states are dense in the space of all states. The pure states on BpHq are the vector states, that is, the states of the form T &#222; &#209; xT &#958;, &#958;y for some &#958; P H.</p><p>A consequence of the Hahn-Banach theorem is the fact that, for any C &#730;-algebra A and any self-adjoint element a P A, we have }a} " sup &#966;PSpAq |&#966;paq|. Another consequence of the Hahn-Banach theorem is that whenever A is a subalgebra of B, any state on A can be extended to a state on B.</p><p>When H is finite dimensional, every state on BpHq is of the form T &#222; &#209; TrpT &#961;q for a unique positive operator &#961; of trace 1, where Tr denotes the trace of an operator. The operator &#961; is often called the density matrix for the state. When H is not necessarily finite dimensional, the same result holds true for states on BpHq that are continuous with respect to the weak*-topology on BpHq, except that &#961; is now stipulated to be a trace-class operator (see, for example, <ref type="bibr">[35,</ref><ref type="bibr">Theorem 19.9]</ref>).</p><p>The term "state" comes from quantum mechanics. A first introduction to quantum mechanics will introduce a state of a physical system as simply a unit vector &#958; in the Hilbert space H associated to the physical system. This usage of the word state corresponds to the vector states described above. Later, one encounters the notion of mixed state (to accomodate the fact that results of quantum measurements are merely probabilistic ensembles of pure states), which is often defined in terms of the density matrix as defined above. The role of a state in quantum mechanics is simply to assign expected values of observables (see <ref type="bibr">[35,</ref><ref type="bibr">Section 19]</ref>).</p><p>An important construction associated to a state is the Gelfand-Naimark-Segal pGNS q construction, which associates a representation of the C &#730;-algebra to the state. Suppose that &#966; is a state on A. We define a sesquilinear form x&#168;, &#168;y&#966; on A by xx, yy &#966; :" &#966;py &#730;xq. It is straightforward to check that this is a so-called pre-inner product on A in that it satisfies all of the properties of being an inner product except that xx, xy &#966; " 0 need not necessarily imply that x " 0; when x, y &#966; is actually an inner product, we say that &#966; is faithful. Associated to x&#168;, &#168;y&#966; is the seminorm } &#168;}&#966; on A given by }x} &#966; :" a xx, xy &#966; . We obtain a Hilbert space, denoted L 2 pA, &#966;q, by quotienting out by the closed subspace of vectors with } &#168;}&#966; " 0 and then taking the completion. Given a P A, we let &#226; denote its equivalence class in L 2 pA, &#966;q. It follows that there is a representation &#960; &#966; : A &#209; L 2 pA, &#966;q uniquely determined by the condition &#960; &#966; paqp bq :" &#226;b for all a, b P A. The representation &#960; &#966; is cyclic, meaning that there is a vector &#958; P L 2 pA, &#966;q for which t&#960; &#966; paq&#958; : a P Au " L 2 pA, &#966;q, namely &#958; " 1. Moreover, the vector state x&#168;1, 1y &#966; on L 2 pA, &#966;q restricts to &#966; on the image of A. Note that &#960; &#966; is a faithful representation precisely when &#966; is faithful.</p><p>There is a converse to the above construction: if &#960; : A &#209; BpHq is a cyclic representation of A with cyclic vector &#958; P H, then one obtains a state &#966; &#960; on A by &#966; &#960; paq :" x&#960;paq&#958;, &#958;y and the GNS representation associated to &#966; &#960; is unitarily equivalent to &#960;.</p><p>Define H u :" &#192; &#966;PSpAq L 2 pA, &#966;q and set &#960; u " &#192; &#966;PSpAq &#960; &#966; : A &#209; H u , which we call the universal representation of A. Since }a} " sup &#966;PSpAq |&#966;paq| for any self-adjoint a P A, it follows that &#960; u is a faithful representation of A. Since any representation of A is a direct sum of cyclic representations and since every cyclic representation of A is, up to unitary equivalence, of the form &#960; &#966; for some &#966; P SpAq, we see that every representation of A is unitarily equivalent to a subrepresentation of &#960; u , whence the name! An important ingredient in this story is the von Neumann algebra &#960; u pAq 2 generated by the image of A in BpH u q. It can be shown that this von Neumann algebra is isometrically isomorphic to the Banach space A &#730;&#730;, whence it is this notation that is usually used.</p><p>A state &#966; on A is called a tracial state if &#966;pabq " &#966;pbaq for all a, b P A. For example, the normalized trace tr on M n pCq given by trpaq :" Suppose that &#964; is a trace on M. The corresponding representation &#960; &#964; : M &#209; BpL 2 pM, &#964; qq is normal and the image of &#960; &#964; pM q is WOT-closed in BpL 2 pM, &#964; qq. Also, M is separable if and only if it is separable with respect to the metric stemming from the norm } &#168;}&#964; . When restricted to the unit ball of M, the topology induced by } &#168;}&#964; coincides with the SOT on M it inherits from L 2 pM, &#964; q.</p><p>We end this section by showing how traces can be used to define the hyperfinite II 1 factor, the star of this paper! Given n &#283; 1, there is a natural embedding of tracial von Neumann algebras</p><p>In this way, we obtain a directed system of tracial von Neumann algebras whose union is a &#730;-algebra we denote by M :" &#356; n M 2 n pCq. The fact that the embeddings preserve the normalized traces on the individual matrix algebras implies that M has a tracial state &#964; on it. We apply the GNS construction to &#964; (which still works even though the original algebra is not necessarily complete) and take the von Neumann algebra generated by &#960; &#964; pM q inside of BpL 2 pM, &#964; qq. This von Neumann algebra is called the hyperfinite II 1 factor R. We will see the reason for the "II 1 factor" in the name in the next section but the terminology "hyperfinite" can be explained now. A separable von Neumann algebra is called hyperfinite if it contains an increasing union of finite-dimensional subalgebras whose union is WOT-dense. Murray and von Neumann showed that there is a unique separable hyperfinite II 1 factor. Consequently, if we started the above construction with any M n pCq instead of M 2 pCq, we would have arrived at the same II 1 factor, namely R.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.5.">More on von Neumann algebras. The center of a von Neumann algebra</head><p>M is ZpMq :" M X M 1 " tx P M : xy " yx for all y P Mu. A von Neumann algebra M is called a factor when its center is trivial, that is when ZpMq " C &#168;1. It is quite easy to see that BpHq is a factor; in particular, each M n pCq is a factor. This makes it plausible that R is also a factor, given that it is the completion of an increasing sequence of factors-one just needs to check that no elements snuck into the center at the completion stage.</p><p>The interest in factors comes from the fact that they are the building blocks of all von Neumann algebras in the sense that every von Neumann algebra can be written as a direct integral (a generalization of direct sum) of factors, and thus the study of arbitrary von Neumann algebras can usually be reduced to studying factors.</p><p>Murry and von Neumann divided the collection of factors into three types, (creatively) called types I, II, and III. They further split the first two types into subtypes as follows. First, for each n P N, there is a unique factor of type I n , namely M n pCq. The unique factor of type I 8 is BpHq for H infinite dimensional. Next, a II 1 factor is an infinite-dimensional finite factor, that is, an infinite-dimensional factor that admits a trace. Thus, the hyperfinite II 1 factor is indeed a II 1 factor. A II 8 factor is one that can be written as a proper increasing union of type II 1 factors. Equivalently, a II 8 factor can be written in the form M bBpHq for some II 1 factor M (see <ref type="bibr">Subsection 3.8</ref> </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>for the definition of tensor products of von Neumann algebras).</head><p>There is also division of type III factors into subtypes III &#955; for &#955; P r0, 1s, but we will not need to get into that here.</p><p>It is important to note that, while an arbitrary finite von Neumann algebra may have many traces, the trace on a finite factor is unique. We also note the crucial fact that R embeds into any II 1 factor.</p><p>As alluded to above when defining finite von Neumann algebras, the above type classification makes more sense in the context of Murray-von Neumann equivalence. However, we can still see this division using traces. Given a von Neumann algebra M, let PpMq denote the set of projections in M. If &#964; is a trace on M, set &#964; pPpMqq :" t&#964; ppq : p P PpMqu. Note that, for the unique type I n factor M n pCq, we have &#964; pPpM n pCqqq " t0, 1 n , . . . , n&#180;1 n , 1u, one value for every dimension being projected onto. On the other hand, for a II 1 factor M, one can show that &#964; pPpMqq " r0, 1s. Thus, we think of II 1 factors being like matrix factors in that they admit traces, but now we have a continuous dimension for projections.</p><p>One can explain the cases I 8 and II 8 using traces if one considers the unnormalized trace Tr on BpHq given by TrpT q :" &#345; iPI xT &#958; i , &#958; i y, where p&#958; i q iPI is any orthonormal basis for H. Note that Tr can take the value 8. We then have that the possible traces of projections for the I 8 factor are t0, 1, 2, . . . , u Y t8u while in the type II 8 case they are r0, 8s.</p><p>3.6. The tracial ultrapower construction and the official statement of the CEP. In general, an ultraproduct of a collection of similar structures is a structure of the same type that represents some sort of limit of these structures. There are ways of making this precise using model theory, and we will discuss this in Subsection 7.2. In this section, we show how to carry this construction out in the case of tracial von Neumann algebras and see how this allows us to precisely state the CEP.</p><p>First, one needs to introduce the notion of an ultrafilter. (For an entire book devoted to ultrafilters and their applications, see the author's <ref type="bibr">[27]</ref>). Given an index set I, an ultrafilter U on I is simply a t0, 1u-valued finitely additive probability measure on I. One often identifies U with its set of measure 1 sets and writes X P U instead of UpXq " 1. From this perspective, one can alternatively view an ultrafilter U on I as a division of the subsets of I into two categories-U-large and U-small -satisfying the following requirements: I is U-large while H is U-small; the intersection of two U-large sets is U-large; a superset of a U-large set is once again U-large; for any subset J of I, exactly one of J or IzJ is U-large.</p><p>Following typical measure-theoretic terminology, given a property P that may or may not hold of elements of I, we may write "for U-almost all i P I, P piq holds" when ti P I : P piq holdsu belongs to U.</p><p>Given a bounded sequence pz i q iPI of complex numbers, it is straightforward to show that there is a unique complex number z such that, for every &#261; 0, we have |z &#180;zi | &#259; for U-almost all i P I. This unique complex number z is called the Uultralimit of the sequence pz i q iPI , denoted lim i,U z i or simply lim U z i . The fact that every bounded sequence has a limit (in this generalized sense) is but one indication of the utility of ultrafilters.</p><p>Given j P I, the unique ultrafilter U on I for which Uptjuq " 1 is called the principal ultrafilter generated by j, and is denoted U j . An ultrafilter U on I is called nonprincipal if it is not principal. Equivalently, U is nonprincipal if UpXq " 0 for all finite X &#270; I. It is easy to check that lim U j z i " z j , whence ultralimits along principal ultrafilters do not really capture a genuine notion of limit. It is a basic fact that, for any infinite set I, there is a nonprincipal ultrafilter U on I (in fact there are many!). However, any proof of the existence of such ultrafilters is necessarily nonconstructive, and thus it is impossible to explicitly describe a nonprincipal ultrafilter (see <ref type="bibr">[27,</ref><ref type="bibr">Chapter 5]</ref> for more on these foundational matters concerning ultrafilters). In what follows, the specific choice of nonprincipal ultrafilter will be irrelevant for our purposes.</p><p>We now come to the tracial ultraproduct construction. Fix a family pM i , &#964; i q iPI of tracial von Neumann algebras and an ultrafilter U on I. We first set</p><p>that is, 8 pM i q collects all those sequences from the Cartesian product &#347; iPI M i for which the operator norms of the coordinates are uniformly bounded. It is readily verified that 8 pM i q is a C &#730;-algebra under the supremum norm. It is tempting to try to define a tracial state &#964; on 8 pM i q by declaring &#964; pxq :" lim U &#964; i pxpiqq, which makes sense given that the sequence p&#964; i pxpiqqq iPI is a uniformly bounded sequence of complex numbers (a consequence of the uniform bound on the operator norms of the coordinates of x). Unfortunately, if each xpiq is a positive element of M i , whence x is a positive element of 8 pM i q, with the property that lim U &#964; i pxpiqq " 0, then we have that &#964; pxq " 0 even though x may not be zero. In other words, this definition leads to a tracial state on 8 pM i q that is not faithful.</p><p>We fix the above problem by defining c U :" tx P 8 pM i q : lim U &#964; i pxpiqq " 0u. While there are a lot of things to check, we have that:</p><p>&#8218; c U is a two-sided ideal in 8 pM i q, &#8218; 8 pM i q{c U is a von Neumann algebra, &#8218; the induced tracial state &#964; on 8 pM i q{c U given by &#964; prxs U q :" lim U &#964; i pxpiqq is a trace (that is, a faithful, normal tracial state) on 8 pM i q{c U , where rxs U denotes the coset of x modulo c U .</p><p>The resulting tracial von Neumann algebra is denoted p &#347; U M i , lim U &#964; i q and is called the tracial ultraproduct of the family pM i , &#964; i q with respect to U. In a certain sense, one should think of this ultraproduct as some sort of limit of the constitutent tracial von Neumann algebras, an analogy that will become clearer as we proceed. When each M i is a finite factor, then the trace on each factor is unique and we simplify the notation to &#347; U M i . When each pM i , &#964; i q " pM, &#964; q, we simply write pM, &#964; q U and speak of the ultrapower of pM, &#964; q with respect to U. Similarly, the ultrapower of a finite factor is denoted M U . We view any tracial von Neumann algebra pM, &#964; q as a subalgebra of pM, &#964; q U via the diagonal embedding which maps an element a P M to the coset of the diagonal sequence pi &#222; &#209; aq modulo c U .</p><p>When U " U j is principal, one can verify that &#347; U pM i , &#964; i q -pM j , &#964; j q, whence this is not a terribly interesting procedure. The true power of the ultraproduct construction comes when one uses a nonprincipal ultrafilter, for then the ultraproduct is sort of an average or limit of the constitutent tracial von Neumann algebras.</p><p>If lim U dimpM j q &#259; 8, then &#347; U pM i , &#964; i q is also finite dimensional. Otherwise, &#347; U pM i , &#964; i q is quite large, in fact, nonseparable, even if each M i is separable. It is quite common to hear expressions such as "every II 1 factor in this paper (or talk) is separable unless it isn't." This tautology refers to the fact that often researchers are only interested in separable tracial von Neumann algebras, and the only nonseparable II 1 factors that one might encounter are those obtained from a nonprincipal ultraproduct of a family of separable II 1 factors. (We are being a bit sloppy-nonprincipality only guarantees nonseparability when the index set is countable; otherwise, one needs the mild assumption of countable incompleteness.)</p><p>We can now officially state the CEP.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Connes embedding problem.</head><p>Given any nonprincipal ultrafilter U on N, every separable tracial von Neumann algebra embeds into R U ; that is, it admits a tracepreserving injective &#730;-homomorphism into R U .</p><p>Let us make several remarks on variations of the statement of the CEP:</p><p>&#8218; It can be shown using some basic model theory that the CEP is equivalent to the statement that every separable tracial von Neumann algebra embeds into R U for some nonprincipal ultrafilter U on N. This fact can also be witnessed by using a simple ultrafilter-free equivalent reformulation of the CEP known as the microstate conjecture, discussed below. &#8218; The restriction to separable tracial von Neumann algebras is not necessary.</p><p>It can be shown that ultrapowers of R with respect to certain kinds of ultrafilters on larger index sets, known as good ultrafilters, lead to larger ultrapowers that can embed tracial von Neumann algebras of larger density character. In other words, we can reformulate CEP by saying every tracial von Neumann algebra embeds into some ultrapower of R. &#8218; The validity of the CEP does not change if we restrict ourselves to embedding II 1 factors into an ultrapower of R. The reason for this is due to the fact that every tracial von Neumann algebra pM, &#964; q embeds into a II 1 factor, say pM &#730;LpZq, &#964; &#730;&#964;LpZq q. Here LpZq is the group von Neumann algebra of the group of integers (see Subsection 3.7) and &#730;denotes the free product of tracial von Neumann algebras. &#8218; One can replace R U with a nonprincipal ultraproduct of matrix algebras without changing the validity of the CEP. More precisely, CEP is equivalent to the statement that, for any nonprincipal ultrafilter U on N, every separable tracial von Neumann algebra embeds into &#347; U M n pCq. This follows from the fact that each M n pCq embeds in R, whence &#347; U M n pCq embeds in R U , while there are conditional expectations &#934; n : R &#209; M n pCq, and the ultralimit of these expectations yields an embedding lim U &#934; n : R U &#227;&#209; &#347; U M n pCq. (See Subsection 3.9 for the definition of conditional expectation.)</p><p>The last alternate reformulation makes the equivalence with the so-called microstate conjecture more apparent. The microstate conjecture states that for any tracial von Neumann algebra pM, &#964; q, any finite collection p 1 pxq, . . . , p m pxq of &#730;polynomials in the noncommuting variables x " px 1 , . . . , x n q, any a 1 , . . . , a n P M in the operator norm unit ball of M, and any &#261; 0, there is k P N and b 1 , . . . , b n P M k pCq in the operator norm unit ball such that max 1&#271;i&#271;n |&#964; pp i paqq &#180;trpp i pbqq| &#259; .</p><p>In other words, any finite configuration that can be obtained in some tracial von Neumann algebra can be approximately obtained in some matrix algebra. It is this formulation of CEP that appeared in connection with free entropy as discussed in Subsection 2.1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.7.">Operator algebras coming from groups.</head><p>A large source of operator algebras arise from groups and these algebras play an important role in our story.</p><p>First, a unitary representation of a (discrete) group G is a group homomorphism &#960; : G &#209; UpAq, where A is a C &#730;-algebra and UpAq denotes the group of unitary elements of A.</p><p>Suppose that G is a group. Let 2 pGq be the Hilbert space formally generated by an orthonormal basis &#950; h for all h P G. For any g P G, define u g to be the linear operator on 2 pGq determined by u g p&#950; h q " &#950; gh for all h P G. Notice that u g is unitary for all g P G (since u g " u &#180;1 g " u g &#180;1 q and so &#955; : G &#209; Up 2 pGqq given by &#955;pgq :" u g is a unitary representation of G, called the left regular representation of G.</p><p>Recall that group algebra CrGs consists of formal linear combinations &#345; gPG c g g with only finitely many nonzero coefficients. There is a natural &#730;-algebra structure on CrGs, the addition and multiplication being the obvious ones and the &#730;-operation being given by p</p><p>CrGs is in fact a unital &#730;-algebra with unit e, where e denotes the identity of the group.</p><p>The left regular representation &#955; of G extends by linearity to a unital &#730;-algebra homomorphism &#960; : CrGs &#209; Bp 2 pGqq.</p><p>The reduced group C &#730;-algebra of G, denoted C r pGq, is the closure of &#960;pCrGsq in the operator norm topology on Bp 2 pGqq. The group von Neumann algebra of G, denoted LpGq, is the closure of &#960;pCrGsq in the WOT on Bp 2 pGqq. Moreover, the vector state on Bp 2 pGqq corresponding to &#958; e yields a tracial state on C r pGq and a trace on LpGq.</p><p>When G is finite, C r pGq " LpGq " CrGs and is generally considered uninteresting (to operator algebraists). When G is infinite, LpGq is a II 1 factor precisely when G is an infinite conjugacy class pICC q group, that is, when all nontrivial conjugacy classes of G are infinite.</p><p>The procedure of taking the group von Neumann algebra of a group can "forget" a lot of the algebraic structure of the group. For example, it follows from Connes' fundamental work <ref type="bibr">[15]</ref> that all ICC amenable groups have group von Neumann algebra isomorphic to R.</p><p>In what follows, the reduced group C &#730;-algebra of a group is not quite as important as a second C &#730;-algebra associated to a group, the so-called universal por maximalq group C &#730;-algebra. To define this, we define a norm on CrGs by defining</p><p>It is readily verified that this is a well-defined (that is, finite) C &#730;-norm on CrGs.</p><p>The completion of CrGs with respect to this norm is thus a C &#730;-algebra, called the universal C &#730;-algebra associated to G, denoted C &#730;pGq. Since the above norm is easily seen to be the maximal C &#730;-norm on CrGs, it is sometimes called the maximal norm on CrGs and the completion the maximal group C &#730;-algebra of G. It follows immediately from the definition that any unitary representation &#960; : G &#209; UpAq of G extends uniquely to a &#730;-homomorphism &#960; : C &#730;pGq &#209; A.</p><p>A particular corollary of this universal property of the universal group C &#730;-algebra is that C &#730;pF 8 q is surjectively universal, where F 8 is the free group on a countably infinite set of generators. More precisely, given any separable C &#730;-algebra A, there is a surjective &#730;-homomorphism C &#730;pF 8 q &#209; A. To see that this is the case, just note that there is a countable set tu i : i P Nu of unitaries that generates A (as a C &#730;algebra); now apply the universal property to the surjective unitary representation F 8 &#209; UpAq obtained by mapping the ith basis element of F 8 onto u i .</p><p>Another consequence of the universal property is that if f : G &#209; H is a group homomorphism, then we get an induced &#730;-algebra homomorphism C &#730;pf q : C &#730;pGq &#209; C &#730;pH q. A less obvious fact is that if H is a subgroup of G, then C &#730;pH q is naturally a C &#730;-subalgebra of C &#730;pGq. This follows immediately from the definitions once one knows that any unitary representation of H can be extended to a unitary representation of G (via a technique known as induction; see <ref type="bibr">[22,</ref><ref type="bibr">Chapter 6]</ref>).</p><p>By considering the left-regular representation of G, we immediately see that there is a canonical surjective &#730;-homomorphism C &#730;pGq &#209; C r pGq. In general, this map is not an isomorphism; that is, it often has nontrivial kernel. In fact, the canonical map C &#730;pGq &#209; C r pGq is an isomorphism precisely when G is amenable.</p><p>One final fact will prove useful later: for any two groups G and H, we have C &#730;pG &#730;Hq -C &#730;pGq &#730;C&#730;p Hq, where G &#730;H denotes the free product of groups and C &#730;pGq &#730;C&#730;p Hq denotes the unital free product of C &#730;-algebras, which is slightly annoying to define but whose properties can be guessed from the terminology.</p><p>3.8. The problem with C &#730;-algebra tensor products. Before discussing the issues associated with defining tensor products of C &#730;-algebras, we first recall the tensor product construction for vector spaces. Let V and W be vector spaces over the same field K. We let FpV &#710;W q be the free K-vector space on the set V &#710;W , that is, all formal linear combinations &#345; pv,wqPV &#710;W c pv,wq pv, wq with only finitely many nonzero coefficients. FpV &#710;W q carries an obvious K-vector space structure. The tensor product of V and W , denoted V d W , is the quotient of FpV &#710;W q by the subspace generated by elements of the following form, for v, v 1 P V , w, w 1 P W , and &#945; P K: &#8218; pv `v1 , wq &#180;pv, wq &#180;pv 1 , wq, &#8218; pv, w `w1 q &#180;pv, wq &#180;pv, w 1 q, &#8218; p&#945;v, wq &#180;&#945;pv, wq, &#8218; pv, &#945;wq &#180;&#945;pv, wq.</p><p>While it is more common to write V b W instead of V d W , we will reserve b for analytic tensor products (to be defined shortly) and will use d for the above algebraic tensor product.</p><p>The equivalence class of pv, wq in V d W is denoted v b w. Thus, an arbitrary element of V d W may be written as a formal linear combination</p><p>If V and W are both finite dimensional, then so is V d W with dimpV d W q " dimpV q &#168;dimpW q; if tv 1 , . . . , v m u is a basis for V and tw 1 , . . . , w n u is a basis for W , then tv i b w j :</p><p>If H and K are Hilbert spaces, then the algebraic tensor product H d K comes naturally equipped with an inner product uniquely determined by</p><p>The completion of H d K with respect to this inner product is then a Hilbert space, denoted H b K and called the Hilbert space tensor product of H and K. If te i : i P Iu and tf j : j P Ju are orthonormal bases for H and K, respectively, then te i b f j : i P I, j P Ju is an orthonormal basis for H b K. Moreover, if S : H 1 &#209; H 2 and T : K 1 &#209; K 2 are bounded linear maps, then the algebraic tensor product map S d T extends uniquely to a bounded linear map S b T :</p><p>We now come to the task of defining tensor products of operator algebras. We first note that if A and B are two &#730;-algebras, there is a natural &#730;-algebra operation on their algebraic tensor product A d B determined by A useful property of the minimal tensor product is the following result, which follows from the independence of the choice of representation. If</p><p>Using the Stinespring dilation theorem, one can generalize the conclusion of the previous sentence to ucp maps as follows. If &#934; A : A &#209; BpH A q and &#934; B : B &#209; BpH B q are ucp maps, then there is a unique ucp map</p><p>Another natural C &#730;-norm to consider on A d B is the so-called maximal norm defined by</p><p>In connection with this formula, it is useful to observe that a &#730;-homomorphism Before moving forward, we notice the following two facts, which are readily verified from the definitions. For any pair of groups G and H, we have</p><p>Returning to the general discussion, we have defined two extreme C &#730;-norms on A d B. In general, they can be different. For example, it can be shown that the maximal and minimal norms on C r pF 2 q d C r pF 2 q are distinct. The corresponding question for C &#730;pF 2 q d C &#730;pF 2 q turns out to be equivalent to CEP, as we will soon see! Another somewhat surprising result is that the maximal and minimal norms on BpHq d BpHq (for H infinite dimensional) are also distinct, a result due to Junge and Pisier <ref type="bibr">[42]</ref>. In fact, Ozawa and Pisier <ref type="bibr">[49]</ref> showed that there exist at least continuum many different C &#730;-norms on BpHq d BpHq when H is infinite dimensional.</p><p>We say that pA, Bq form a nuclear pair if there is a unique C &#730;-norm on A d B, that is, if the minimal and maximal norms on A d B coincide. We also say that A is nuclear if pA, Bq is a nuclear pair for every C &#730;-algebra B. There are many interesting examples of nuclear C &#730;-algebras. For example, M n pCq is nuclear for all n, the reason being that M n d B -M n pBq, which is already a C &#730;-algebra with a unique C &#730;-norm. A more interesting example coming from groups is that C &#730;pGq is nuclear if and only if C r pGq is nuclear if and only if G is amenable (in which case C &#730;pGq " C r pGq).</p><p>The following theorem of Kirchberg <ref type="bibr">[44]</ref> will be central moving forward.</p><p>Theorem 3.1. pC &#730;pF 8 q, BpHqq is a nuclear pair.</p><p>Note that neither of these algebras are nuclear. The importance of Kirchberg's theorem stems from the fact that C &#730;pF 8 q is surjectively universal while BpHq is injectively universal.</p><p>We also note that if H is a subgroup of G and A is any C &#730;-algebra for which pC &#730;pGq, Aq is a nuclear pair, then so is pC &#730;pH q, Aq. In particular, whether or not pC &#730;pF k q, C &#730;pF k qq is a nuclear pair is independent of the choice of k P t2, 3, . . .u Y t8u, a fact that will come up in our discussion of Kirchberg's QWEP problem. We will also need the fact that if p : G &#209; H is a surjective group morphism for which the canonical surjection C &#730;ppq : C &#730;pGq &#209; C &#730;pH q has a ucp lift (meaning a ucp map &#934; : C &#730;pH q &#209; C &#730;pGq for which C &#730;ppq&#934; is the identity on C &#730;pH q), then pC &#730;pGq, C &#730;pGqq being a nuclear pair implies pC &#730;pH q, C &#730;pH qq is a nuclear pair.</p><p>3.9. Kirchberg's QWEP problem. It follows from the definition of the minimal tensor product that for any inclusion A &#270; B of C &#730;-algebras, one has that Ab min C &#270; B b min C (isometrically) for any other C &#730;-algebra C. On the other hand, with the same setup, while there will always be a &#730;-homorphism A b max C &#209; B b max C, this homomorphism need not be injective, that is, isometric. One case, however, where this does hold is the inclusion A &#270; A &#730;&#730;. That is, it follows from the definitions that A b max C &#270; A &#730;&#730;b max C isometrically for all C &#730;-algebras A and C. Suppose again that A &#270; B and further suppose, for the sake of argument, that there is a ucp map &#934; : B &#209; A &#730;&#730;with &#934;paq " a for all a P A. By a fact pointed out in the the previous subsection, we obtain a ucp (and thus contractive) map &#934; b I C : B b max C &#209; A &#730;&#730;b max C. By the observation made in the previous paragraph, it follows that the canonical map</p><p>If A is a C &#730;-subalgebra of B and &#934; : B &#209; A is a linear map for which &#934;paq " a for all a P A, then a theorem of Tomiyama says that the following are equivalent: N of M is cp-complemented. To see this, fix a trace &#964; on M and note that L 2 pN, &#964; q is a closed subspace of L 2 pM, &#964; q. One shows that the orthogonal projection L 2 pM, &#964; q &#209; L 2 pN, &#964; q actually restricts to a conditional expectation</p><p>To see this, one shows that the map &#934; : G &#209; CrHs, defined by setting &#934;pgq " g for all g P H while &#934;pgq " 0 for all g P GzH, extends to a conditional expectation C &#730;pGq &#209; C &#730;pH q.</p><p>Returning to the general situation, if A is weakly cp-complemented in every superalgebra (or equivalently in BpHq), then we say that A has the weak expectation property pWEPq. An insight of Kirchberg <ref type="bibr">[44]</ref> was to use his theorem proving that pC &#730;pF 8 q, BpHqq is a nuclear pair to provide an alternate test for having WEP: Theorem 3.2. For a C &#730;-algebra A &#270; BpHq, the following are equivalent:</p><p>Proof. We already observed the equivalence of ( <ref type="formula">1</ref>) and <ref type="bibr">(2)</ref>. Now suppose that A has WEP. We then have</p><p>that is, pA, C &#730;pF 8 qq is a nuclear pair. Conversely, suppose that pA, C &#730;pF 8 qq is a nuclear pair. It suffices to show that A b max C &#730;pF 8 q &#270; BpHq b max C &#730;pF 8 q. However, this follows immediately from the assumption, Kirchberg's theorem, and the fact that b min preserves inclusions.</p><p>What are the ramifications of assuming that C &#730;pF 8 q itself has the WEP, that is, pC &#730;pF 8 q, C &#730;pF 8 qq is a nuclear pair? First, as observed above, this is equivalent to pC &#730;pF k q, C &#730;pF k qq being a nuclear pair for any fixed k &#283; 2. Next, if we define the QWEP to be the property that a C &#730;-algebra is a quotient of a C &#730;-algebra with WEP, then C &#730;pF 8 q having the WEP implies that all separable C &#730;-algebras have the QWEP. We note that it is common to see both phrases, "A has the QWEP" and "A is QWEP" (although the latter is of course grammatically incorrect).</p><p>Conversely, suppose that all separable C &#730;-algebras have the QWEP. Then certainly C &#730;pF 8 q has the QWEP. However, C &#730;pF 8 q has another property, the so-called lifting property pLPq which, when combined with QWEP, actually implies the WEP. A C &#730;-algebra A has the lifting property if, for any ucp map &#934; : A &#209; B{J, where B is a C &#730;-algebra and J is a closed, two-sided ideal in B, there is a ucp map &#936; : A &#209; B for which &#960; &#733;&#936; " &#934;, where &#960; : B &#209; B{J is the canonical quotient map. Said more casually, A has the LP if every ucp map into a quotient C &#730;-algebra has a ucp lift. Now suppose that A has the LP and the QWEP as witnessed by the quotient map q : B &#209; A with B having the WEP. Let &#936; : A &#209; B be a ucp lift of the identity map A &#209; A, that is, q &#733;&#936; " I A . Then by applying the ucp lift &#936; b I C &#730;pF 8 q of q b I C &#730;pF 8 q , we see that A also has the WEP.</p><p>We have thus arrived at the following.</p><p>Theorem 3.3. The following assertions are equivalent:</p><p>(1) C &#730;pF 8 q has the WEP.</p><p>(2) For some (equivalently any) k P t2, 3, . . .u Y t8u, pC &#730;pF k q, C &#730;pF k qq is a nuclear pair. (3) Every separable C &#730;-algebra has the QWEP. Any of the above equivalent statements are known as Kirchberg's QWEP problem. (We might be tempted to follow the CEP's lead and call this the QWEPP, but that looks a bit silly.) As mentioned above, QWEP combined with LP implies WEP. It turns out that it suffices to consider a local version of LP, aptly called the local lifting property pLLPq and the same argument works; that is, QWEP together with LLP implies WEP. Thus, another equivalent formulation of the QWEP problem is the statement that LLP implies WEP.</p><p>We mention one other equivalent formulation of the QWEP problem that is not relevant for our particular story but is fascinating nonetheless: the QWEP problem is equivalent to the statement that C &#730;pF 8 &#710;F8 q has a faithful tracial state. What makes this interesting is that this is true for the reduced group C &#730;algebra C r pF 8 &#710;F8 q (simply because it is true for any reduced group C &#730;-algebra) and it is true for C &#730;pF 8 q (a result due to Choi).</p><p>The classes of WEP and QWEP algebras enjoy a number of closure properties relevant to the proofs that follow. Rather than enumerate them all now, we will simply quote them when we need them later in the paper.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>3.10.</head><p>From CEP to QWEP. In this section, we show how a positive solution to the CEP implies a positive solution to the QWEP problem. While these statements are indeed equivalent, we focus on the direction that we need in order to give a negative solution to CEP.</p><p>So how does CEP get involved in a story about C &#730;-algebras? The first clue is that, for von Neumann algebras, the WEP had already been well studied and is referred to as injectivity. A not so trivial result is that any hyperfinite von Neumann algebra is injective, whence R is injective. The extremely deep work of Connes in <ref type="bibr">[15]</ref>, where the CEP originally comes from, proved the converse, namely any separable injective II 1 factor must be hyperfinite, and thus isomorphic to R. Thankfully we do not need this result in our story, although the proof that R is injective (and thus has WEP) is difficult enough. Now that we know that R is injective, so is 8 pRq as WEP is closed under the formation of direct sums. Since R U is a C &#730;-algebra quotient of 8 pRq, we see that R U is QWEP! Okay, it smells like we are getting closer.</p><p>Now suppose that M is a tracial von Neumann algebra that embeds in R U in a trace-preserving manner. Without loss of generality, let us assume that M is simply a subalgebra of R U . By a fact pointed out above, this means that M is cp-complemented in R U . Since QWEP is preserved by (weakly) cp-complemented inclusions, we conclude that M is also QWEP.</p><p>We have thus arrived at the statement: a positive solution to CEP implies all finite von Neumann algebras are QWEP! But we are still talking about von Neumann algebras. How do we bridge the gap into talking about C &#730;-algebras? Well, recall that every C &#730;-algebra A has a canonically associated von Neumann algebra A &#730;&#730;. Since A is tautologically weakly cp-complemented in A &#730;&#730;, in order to show that A has QWEP, it suffices to show that A &#730;&#730;has QWEP (again using the closure of QWEP under weakly cp-complemented subalgebras).</p><p>While A &#730;&#730;is a separable von Neumann algebra, it may not be finite. How do we get CEP to help us with nonfinite von Neumann algebras?</p><p>Given any von Neumann algebra M, there is an important one-parameter group p&#963; &#981; t q of automorphisms of M, known as the modular group. When M is finite, the modular automorphism group is trivial and thus plays no role. But in the general theory, it is an indispensible tool. (For all of the fancy type III material discussed in this paragraph, Takesaki's book <ref type="bibr">[58]</ref> is the canonical reference.) Akin to the semidirect product construction in group theory, there is a crossed product construction that associates to any group acting on a von Neumann algebra a larger von Neumann algebra where this action is implemented by unitaries. Thus, we are entitled to consider the crossed product algebra M &#963; &#981; t R corresponding to the action of R on M via the modular automorphism group. A serious theorem of Takesaki states that M &#963; &#981; t R is semifinite. We came across semifinite factors above. For a general von Neumann algebra, we can take semifinite to mean that the algebra contains an increasing union of finite subalgebras whose union generates the von Neumann algebra. Since QWEP is preserved under unions and a von Neumann algebra is QWEP if it contains a WOT-dense &#730;-subalgebra with QWEP, we see that M &#963; t &#981; R has QWEP. An alternative approach is to use the fact that a von Neumann algebra is QWEP if and only if all of the factors involved in its direct integral decomposition are QWEP. Thus, to show that a semifinite von Neumann algebra is QWEP, it suffices to consider the case of factors. But then a semifinite factor is of the form M bBpHq for a finite factor M, and one can use the fact that the von Neumann algebra tensor product of QWEP von Neumann algebras is again QWEP. Either way, we now know that M &#963; &#981; t R is QWEP. Finally, it is a general fact that any von Neumanna algebra M is always cpcomplemented in any crossed product M &#945; G; since M &#963; &#981; t R is QWEP for any von Neumann algebra M, it follows that M itself is also QWEP. Applying this fact to M " A &#730;&#730;, we see that A &#730;&#730;, and thus A, are also QWEP for any C &#730;-algebra A. This finishes the proof that a positive solution to CEP implies a positive solution to the QWEP problem.</p><p>As mentioned before, a positive solution to the QWEP problem implies a positive solution to the CEP. The proof involves the theory of amenable traces, which we will not go into now, but which will be important in our alternate derivation of the failure of CEP from MIP &#730;" RE given in Subsection 7.5.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.">A crash course in complexity theory</head><p>In this section, we introduce the basic notions from (classical) complexity theory needed to understand the statement of the result MIP &#730;" RE. Essentially all of this material (apart from the business about nonlocal games) was taken from the book <ref type="bibr">[3]</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1.">Turing machines.</head><p>A Turing machine is one of the more popular mathematical formulations of an idealized computing device. Formally, a Turing machine is a pair M " pQ, &#948;q, where Q is a finite set of states of the machine and &#948; : Q &#710;t0, 1, l, u 3 &#209; Q &#710;t0, 1, l, u 2 &#710;tL, S, Ru 3 is the transition function; here l and are two special symbols whose significance will be seen shortly. We always assume that Q contains two special states, namely the start state q start and the halting state q halt . Throughout, for any n P N, t0, 1u n denotes the set of binary strings of length n while t0, 1u &#730;:" &#356; nPN t0, 1u n denotes the set of all finite binary strings. Given z P t0, 1u &#730;, |z| denotes the length of the string z.</p><p>Here is how one should envision the computation performed by the Turing machine M upon some input z P t0, 1u &#730;. The machine contains three tapes, which are one-way infinite strips containing boxes which, at any given moment in the computation, contain exactly one symbol from t0, 1, l, u. The first tape is the input tape, the second tape is the work tape, and the last tape is the output tape. At the beginning of the computation, the input tape has the start symbol in the first box, then the input string z in the next |z| boxes, and then the remainder of the boxes contain the blank symbol l. Both the work tape and the output tape contain the start symbol in the first box and then blank symbols l in the remaining boxes. One envisions each tape having a "tape head" which is placed over exactly one box in the tape at any given moment during the computation; the tape head for the input tape can read the symbol in that box while the tape head for the other two tapes can both read the symbol in that box and potentially change it to a new symbol.</p><p>The Turing machine begins the computation in the start state q start with the tape head above the leftmost box (which contains the start symbol ) for each tape.</p><p>In general, at any given moment during the computation, the Turing machine is in some state q P Q with tape heads reading boxes k 1 , k 2 , k 3 P N (representing how far they are from the beginning of their respective tape) and with symbols s 1 , s 2 , s 3 P t0, 1, l, u inside of each of the boxes being read. The Turing machine then computes &#948;pq, s 1 , s 2 , s 3 q, obtaining the tuple pq 1 , s 1  2 , s 1 3 , I 1 , I 2 , I 3 q, which should be interpreted as follows:</p><p>&#8218; The box in the work tape (resp., output tape) that the tape head is reading should have its contents replaced by s 1 2 (resp., s 1 3 ). &#8218; The tape head for the input tape should move to the left if I 1 " L, to the right if I 1 " R, and should stay in the same place if I 1 " S. Similar actions should be taken corresponding to I 2 for the work tape and I 3 for the output tape. If any tape head is at the leftmost box and the instruction is L, then the tape head should also stay in the same place. &#8218; After executing these acts, the Turing machine should now enter state q 1 . The machine continues running in this fashion. If the machine ever enters the state q halt , then the machine stops running, that is, no further modification of the three tapes will take place. In this case, the output of the computation upon input z is the longest initial string on the output tape not containing any blank symbols. (If all the symbols are blank, then the output is considered the empty string).</p><p>Every Turing machine M computes a partial function f M : t0, 1u &#730;&#225; t0, 1u &#7832;hose domain consists of those strings z P t0, 1u &#730;for which M halts upon input z; in this case, we define f M pzq to be the corresponding output. We sometimes abuse notation and identify f M with M itself, that is, we may write Mpzq instead of f M pzq. We say a partial function f : t0, 1u &#730;&#225; t0, 1u &#730;is computable if f " f M for some Turing machine M.</p><p>Given a function T : N &#209; N, we say that the Turing machine M runs in T pnqtime if, for any input z P t0, 1u &#730;, upon input z, M halts in at most T p|z|q steps. Note that if M runs in T pnq-time for some function T , then f M is a total function. We say that M is a polynomial time (resp., exponential time) Turing machine if M runs in Cn c -time (resp., C2 n c -time) for some constants C &#261; 0 and c &#283; 1.</p><p>A language is simply a subset L &#270; t0, 1u &#730;. We identify a language L with its characteristic function &#967; L : t0, 1u &#730;&#209; t0, 1u. Consequently, it makes sense to speak of L being computable by a Turing machine. Usually, a language is described in terms of some mathematical problem under consideration, e.g., the set of finite graphs that can be 3-colored. The implict assumption is that there is some natural (and effective) way of coding the set of such graphs as a set of finite binary strings. In the following, for all languages introduced in this manner, we assume that the reader can figure out how such a coding might be performed.</p><p>Turing machines are one of several mathematically precise models for computation; other alternatives include register machines and the class of recursive functions. However, all known reasonable models of computation lead to precisely the same class of computable functions. This is evidence for the Church-Turing thesis, which states that this common class of functions coincides with our heuristic notion of what a computable function should be. (See <ref type="bibr">[18,</ref><ref type="bibr">Chapter 3]</ref> for more on this.) One can even formulate a stronger version of the thesis, which states that even when taking into account the efficiency of computations, that is, how fast one can compute a function, the choice of model is still irrelevant. (It is plausible that quantum computers could pose a serious threat to the strong Church-Turing thesis.) The import of the strong Church-Turing thesis for us in these notes is that, in what follows, when claiming that a certain problem can be solved in a certain efficient manner, we never need to actually write down the Turing machine that witnesses this fact. Instead, one can write down an argument using pseudo-code and the reader can (if they choose to) convert the pseudo-code into an actual Turing machine program.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2.">Some basic complexity classes.</head><p>A complexity class is simply a collection of languages. The most interesting complexity classes are those defined by some sort of condition saying that the languages in the class represent efficiently computable (or verifiable, as we shall shortly see) problems.</p><p>The complexity class P is defined to be the class of languages L such that membership in L can be decided by a Turing machine in polynomial time, that is, &#967; L can be computed by a polynomial time Turing machine. For example, the set of connected graphs is a language that belongs to P (as witnessed by, say, the breadth first search algorithm).</p><p>The complexity class EXP is defined in the same manner as P, replacing polynomial time by exponential time. The time hierarchy theorem implies that P EXP.</p><p>Sometimes it is too difficult to come up with an algorithm that efficiently decides membership in a particular language while it is the case that if someone were to hand you a proof that a certain string belonged to the language, then you could efficiently verify that the proof was indeed correct. The complexity class NP captures this idea. More precisely, the complexity class NP consists of those languages L for which there is a polynomial time Turing machine M and a polynomial ppnq such that:</p><p>&#8218; for all z P L, there is w P t0, 1u pp|z|q for which Mpz, wq " 1. &#8218; for all z R L and for all w P t0, 1u pp|z|q , Mpz, wq " 0.</p><p>In the above definition, one thinks of w as the proof that z P L; other commonly used terms for w are "witness" and "certificate." One often envisions this situation using two fictious players, a verifier and a prover. If z P L, the prover hands the verifier a proof w that z indeed belongs to L; the prover has unlimited computation power in this regard. In order for the verifier to be able to efficiently check that the proof indeed works, the proof cannot be too long (or else the verifier will not even be able to read the entire proof), hence the polynomial length requirement. Moreover, if z R L, then there should be no proof that z belongs to L, whence the second condition.</p><p>It is clear that P &#270; NP. While intuitively it seems clear that this inclusion should be proper (there ought to be problems that are impossible to efficiently decide, yet there are always proofs that are efficiently verifiable), this fact has yet to be established and remains one of the more famous open problems in mathematics.</p><p>We also note that NP &#270; EXP, as one can check all of the exponentially many possible certificates for a given string in exponential time.</p><p>An example of a language in NP is the set of codes for pairs pG, kq, where G is a finite graph that contains an independent set of size k; a certificate for a given pair is simply an independent set of size k. This language is unlikely to be in P. Indeed, this is an example of a so-called NP-complete problem, meaning that it is as difficult as any other problem in NP (in a precise sense), whence if it belongs to P, then so do all languages in NP and P " NP. Another example of a language in NP is the set of codes for pairs pG 1 , G 2 q of finite graphs that are isomorphic; the certificate here is the isomorphism between the graphs. This problem, however, is unlikely to be NP-complete (see <ref type="bibr">[3,</ref><ref type="bibr">Section 8.4]</ref>).</p><p>An alternative way of defining the class NP is to use nondeterministic Turing machines, which is actually the original definition and explains the terminology (NP stands for nondeterministic polynomial time). A nondeterministic Turing machine is defined exactly like a deterministic one except that it has two transition functions rather than one. Consequently, rather than there being a single (determinstic) sequence of steps during a computation upon a given input, there is an entire binary tree of such computations, for at every step during a computation, one can apply either of the two transition functions. One additional difference is that instead of a single halting state q halt , we now have two halting states called q accept and q reject . We say that the nondeterministic Turing machine M outputs 1 on input z if there is some sequence of steps which causes the machine to reach q accept . If every sequence of steps causes the machine to reach q reject , then we say that M outputs 0. If every sequence of computations results in either q accept or q reject in time T p|z|q, then we say that M runs in time T pnq. It thus makes sense to speak of polynomial time (resp., exponential time) nondeterminstic Turing machines.</p><p>It can easily be verified that a language L belongs to NP if and only if there is a polynomial time nondeterministic Turing machine M such that f M " &#967; L . Moreover, using exponential time nondeterministic Turing machines, we can also define the complexity class NEXP. Of course, using nondeterministic Turing machines that run in doubly exponential time, one can also define NEEXP (this will come up later). A nondeterministic version of the time hierarchy theorem guarantees NP NEXP NEEXP.</p><p>At this point, we have P &#270; NP &#270; EXP &#270; NEXP with P EXP and NP NEXP. One can also use a padding argument to show that if P " NP, then EXP " NEXP.</p><p>So far we have only been concerned with time efficiency. One can instead consider space efficiency. We will only consider the class PSPACE, which consists of all languages L for which there is a Turing machine such that, upon input z, it decides whether or not z P L using only a polynomial amount of work space. It is clear that P &#270; PSPACE. It is also fairly easy to see that NP &#270; PSPACE, for one can simply check all possible certificates, erasing one's work after each individual check, thus using only a polynomial amount of space. A slightly less obvious inclusion is PSPACE &#270; EXP; the proof uses the notion of a configuration graph for a computation. So, to update our state of knowledge, we have P &#270; NP &#270; PSPACE &#270; EXP &#270; NEXP. It is not known if either inclusion NP &#270; PSPACE or PSPACE &#270; NEXP is proper (although one of them must be as NP NEXP); as with P &#270; NP, it is believed that both of these inclusions are proper.</p><p>We end this section with the definition of the class BPP. Although it will not play a direct role in the story to follow, it will make a later pill easier to swallow. We return to the setting of nondeterministic Turing machines, but this time we count the proportion of computations that output Mpzq " 1. We say that the language L belongs to the class BPP if there is a nondeterministic Turing machine M such that, upon z P t0, 1u &#730;, the probability that a random nondeterministic computation agrees with &#967; L pzq is at least 2  3 . Just as in the case of NP, there is a formulation using deterministic Turing machines: L belongs to BPP if and only if there is a Turing machine M and a polynomial ppnq such that, for every string z P t0, 1u</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>&#730;,</head><note type="other">Remove Watermark Wondershare PDFelement THE CONNES</note><p>EMBEDDING PROBLEM: A GUIDED TOUR 531 the probability that a random r P t0, 1u pp|z|q is such that Mpz, rq " &#967; L pzq is at least 2 3 . We remark that the choice of 2  3 is fairly arbitrary; by repeating the computation several (but still a reasonable number of) times and taking the majority result of the computations, we can replace 2  3 with a probability as close to 1 as one desires. The class BPP is contained in EXP as one can check all random bits and compute the probability that a random choice yields 1 or 0.</p><p>If L is a language in BPP and one repeats the computation a sufficient number of times to achieve a probability of, say, 0.99, then one can be fairly certain that the result of the probabilistic computation is the truth, and thus BPP seems like a fairly good substitute for P. In fact, there are complexity-theoretic reasons for believing that BPP might coincide with P (see <ref type="bibr">[3,</ref><ref type="bibr">Chapter 16]</ref>).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.3.">Interactive proofs.</head><p>We now imagine the situation where rather than the prover just handing the verifier a proof, the prover and the verifier are allowed to interact. Given an input, the verifier can ask the prover a question, the prover can answer that question, then (based on that answer) the verifier can ask the prover another question to which the prover can reply, and so on, for a certain number of rounds. Each time, the verifier's question and the prover's answer depend on the entire sequence of questions and answers obtained up to that point (as well as the input). After this discussion, the verifier can decide whether or not to accept. Once again, the verifier uses a polynomial-time Turing machine to choose which questions to ask and whether or not to accept at the end of the conversation while the prover has no computational limitations.</p><p>It is not too difficult to verify that, with this description of interactive proof, the corresponding complexity class would simply be NP in disguise. Indeed, one can just use the conversation, or transcript as it is usually called, as the certificate. However, combining this idea with a randomized process as discussed at the end of the last subsection does lead to a class with more computational power (although, interestingly enough, it is a class we have already seen before).</p><p>In order to define this class, we fix k P N (although one could actually work with a polynomial-time computable k : N &#209; N instead) and a polynomial ppnq. Assume that we also have a Turing machine V (now that we are really viewing the machine as a verifier, we have replaced M with V) such that, for all z P t0, 1u &#730;, all r P t0, 1u pp|z|q , and all strings a 1 , . . . , a 2k P t0, 1u &#730;, V halts upon input pz, r, a 1 , . . . , a 2i q in time polynomial in |z| for all i " 0, . . . , k. We then imagine a prover P : t0, 1u &#730;&#209; t0, 1u &#730;interacting with V as follows. First, the verifier randomly selects r P t0, 1u pp|z|q and computes a 1 :" Vpz, rq; this is V's first question to P . P then responds with the answer a 2 :" Ppz, a 1 q. (Note that P does not have access to the random string r; one says that V is using private coins. It turns out that for what we are going to define below, one can also use public coins that the prover is aware of.) This constitutes the first round of their interaction. The verifier then asks P their second question a 3 :" Vpz, r, a 1 , a 2 q and P responds with a 4 :" P pz, a 1 , a 2 , a 3 q, completing the second round of interaction. This is repeated for a total of k rounds. V then returns their decision Vpz, r, a 1 , . . . , a 2k q P t0, 1u, indicating whether or not they accept the prover's answers as constituting evidence that z indeed belongs to L.</p><p>The complexity class IP is defined to be the collection of those languages L for which there is a Turing machine V as above such that: &#8218; If z P L, then there is a prover P such that the probability that a random string r causes V to accept is at least 2 3 . &#8218; If z R L, then no prover can cause V to accept more than 1  3 of the time. The probabilities 2  3 and 1 3 above are called the completeness and soundness parameters, respectively. As in the case of BPP, they are somewhat arbitrary; any choice of completeness parameter strictly larger than one's choice of soundness parameter will define the same class. It turns out that one can even replace the completeness parameter by 1 without changing the class; this property of IP is called perfect completeness.</p><p>A nice example of a language in IP is the collection of pairs pG 1 , G 2 q of finite graphs that are not isomorphic. Note that this class is not obviously in NP for there are too many possible functions that could serve as an isomorphism. There is however a simple interactive proof for this class. Indeed, the verifier randomly selects i P t1, 2u and then randomly selects a permutation &#963; on the number of vertices of G i , obtaining a graph H isomorphic to G i . The verifier then sends the graph H to the prover as its question. The prover then responds with a bit a P t1, 2u, which represents its guess as to which of the two graphs G 1 or G 2 the verifier selected randomly. The verifier accepts if and only if the prover guessed the chosen graph correctly. Note that if G 1 G 2 (that is, if the pair pG 1 , G 2 q belongs to the class), then the prover can always respond correctly, for the prover can just figure out whether or not H is isomorphic to G 1 or to G 2 . (Do not forget that the prover is all-powerful!) However, if G 1 -G 2 (that is, pG 1 , G 2 q does not belong to the class), then H is isomorphic to both G 1 and G 2 , and thus the prover (regardless of its unlimited power) can do no better than simply guessing which graph was chosen by the verifier, thus only convincing the verifier at most half of the time Given a verifier V as in the definition of IP, one can compute in polyp|z|q-space the optimal prover strategy. This shows that IP &#270; PSPACE. A landmark theorem in the subject shows that in fact we have equality: Theorem 4.1 (Lund, Fortnow, Karloff, Nisan <ref type="bibr">[23]</ref>; Shamir <ref type="bibr">[55]</ref>). IP " PSPACE.</p><p>Recall that randomization alone likely does not achieve anything new (earlier we remarked that P " BPP is likely), and, similarly, interaction alone does not achieve anything too new (as we just recover NP). However, combining randomization with interaction bumps us up to PSPACE (which is likely bigger than NP).</p><p>But why stop at one prover? One can consider interactions as above but allowing for multiple provers to interact with the verifier. It should be emphasized that the provers are not allowed to interact with each other during the interaction, but only with the verifier. They can, however, have a meeting before the interaction starts and decide upon a strategy that they will use while interacting with the verifier. In other words, the provers are cooperating but noncommunicating. If the provers use deterministic strategies as above, we arrive at the complexity class MIP. By allowing different kinds of strategies (in particular, those that employ quantum methods), we arrive at variations of MIP, such as the famous MIP &#730;appearing in the equation MIP &#730;" RE.</p><p>It turns out that the complexity class MIP is unchanged if one restricts to just two provers and one round of interaction. We thus make that default assumption from now on. By ignoring one of the provers, we clearly have that IP &#270; MIP. As with IP, one can also achieve perfect completeness.</p><p>With two provers, one can now utilize "police-style" interrogation tactics. This makes it possible for the verifier to read polynomially many random portions of an exponentially long proof and come to a conclusion that with high probability agrees with the truth. A formalization of this idea yields another major theorem in the subject: Theorem 4.2 (Babai, Fortnow, Lund <ref type="bibr">[5]</ref>). MIP " NEXP.</p><p>As mentioned before, it is believed that PSPACE NEXP. If this inclusion is indeed proper, then the jump from one to more than one prover does in fact lead to a larger collection of languages. 4.4. Nonlocal games. It will be useful to recast our description of the class MIP in terms of so-called nonlocal games, a certain collection of two-person games. (The terminology "nonlocal" comes from the connection with Bell's theorem on quantum nonlocality, as we discuss later.)</p><p>Consider a language L in MIP as witnessed by the polynomial-time verifier V. Given input z and a sequence of random bits r, by computing Vpz, rq, we are really computing the two questions x and y (sequences of bits of length polynomial in |z|) that are being sent to the two provers, whom we will call Alice and Bob, following typical quantum information nomenclature. Alice and Bob, employing their deterministic strategies A and B, then respond with their answers, say a :" Apxq and b :" Bpyq, and then the prover calculates Vpz, r, x, y, a, bq to decide whether or not to accept their answers. Whether or not z belongs to L then corresponds to the expected value over a randomly chosen r that the verifier returns Vpz, r, x, y, a, bq " 1. Note that the polynomial time requirement on V allows us to assume that the set of possible answers only contains bits that are of size at most some fixed polynomial in |z|.</p><p>This reformulation leads us to the following notion: A nonlocal game with k questions and n answers is a pair G " p&#960;, Dq, where &#960; is a probability distribution on rks&#710;rks and D : rks&#710;rks&#710;rns&#710;rns &#209; t0, 1u is the decision predicate for the game. Here, rks :" t1, . . . , ku and similarly for rns. A strategy for the players consists of a conditional probability ppa, b|x, yq expressing the probability that Alice and Bob respond with answers a and b if they are asked questions x and y, respectively. We view such a strategy p as an element of r0, 1s k 2 n 2 . Above, we only considered deterministic strategies, namely those p for which there are functions A, B : rks &#209; rns such that ppApxq, Bpyq|x, yq " 1 for all x, y P rks. We let C det pk, nq &#270; r0, 1s k 2 n 2 denote the set of such deterministic strategies. Later, we will consider several other sets of strategies.</p><p>Given a strategy p, the value of the game G with respect to the strategy p is the expected value the players will win G if they play according to p, that is, valpG, pq :" &#255; px,yqPrks&#710;rks</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>&#960;px, yq &#255; pa,bqPrns&#710;rns</head><p>Dpx, y, a, bqppa, b|x, yq.</p><p>We set valpGq :" sup pPC det pk,nq valpG, pq and refer to this as the classical value of the game G.</p><p>We can now rephrase the definition of MIP in terms of nonlocal games: a language L belongs to MIP if and only if there is an efficient mapping z &#222; &#209; G z (in the precise sense described earlier in this subsection) so that:</p><p>3 . The class MIP &#730;appearing in the result MIP &#730;" RE is defined in the analogous way except that we replace classical strategies by quantum strategies. But first, an interlude to explain all things quantum.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.">A quantum detour</head><p>In this section, we introduce the quantum prerequisites necessary to understand the definition of the complexity class MIP &#730;. Our presentation of quantum mechanics is fairly standard and can be found in any good textbook on quantum mechanics. As mentioned above, we also found Paulsen's lecture notes <ref type="bibr">[50]</ref> very helpful as well.</p><p>5.1. Quantum measurements. In quantum mechanics, one associates to each physical system a corresponding Hilbert space H. The state of the system at any given time is given by a unit vector &#958; P H. The state of the system evolves linearly according to a certain partial differential equation (the Schr&#246;dinger equation) until it is measured. A measurement should be thought of as an experiment on the system which has a finite number, say n, possible outcomes. (There are also experiments that can have a countably infinite set of outcomes, say the infinite discrete set of energies of some particle, or even a continuum of outcomes, say when measuring the position or momentum of a particle. For the purposes of this paper, it suffices to focus on the case of finitely many outcomes.) Formally, a measurement with n outcomes consists of n bounded operators M 1 , . . . , M n P BpHq. The Born rule states that, if the state of the system is &#958; upon measurement, then the probability that the ith outcome happens is given by }M i &#958;} 2 . Furthermore, in case the ith outcome is measured, the collapse dynamics tells us that the state of the system instantaneously (and discontinuously) changes to M i p&#958;q{}M i p&#958;q}. Since the sum of the outcome probabilities must be 1, we see that</p><p>Since this equality must hold true for all unit vectors &#958; P H, it follows that &#345; n i"1 M i M i " I H . Consequently, any sequence M 1 , . . . , M n P BpHq satisfying this latter property constitutes a measurement of the system.</p><p>If one is only interested in the probabilities of the outcomes rather than the outcomes themselves (as we will be when we return to our discussion of nonlocal games), then it simplifies matters by replacing a measurement as above by a sequence P 1 , . . . , P n consisting of positive operators which sum up to I H and interpret the probability that the ith outcome is obtained when the system is in state &#958; to be given by xP i &#958;, &#958;y. Such a collection of positive operators is called a positive operator-valued measure (POVM) on H (this terminology comes from spectral theory). If one specializes even further to the case that each P i is not only a positive operator but in fact a projection, then one speaks of projection-valued measures (PVMs) on H. Note then that the projections are automatically pairwise orthogonal, so a PVM on H with n outcomes corresponds to a decomposition of H into n orthogonal subspaces.</p><p>Many introductions to quantum mechanics discuss the measurements of observables. An observable for the physical system is a self-adjoint operator O on H. Supposing for simplicity that H is finite dimensional, the spectral theorem implies that we can find a PVM P 1 , . . . , P n on H such that the P i 's correspond to the projections onto the various eigenspaces of H corresponding to O. The self-adjointness assumption on O further implies that the corresponding eigenvalues are real numbers, whence we can interpret them as corresponding to actual possible physical measurements. Conversely, given any PVM P 1 , . . . , P n on H and real numbers &#955; 1 , . . . , &#955; n , one has an observable O :" &#345; n i"1 &#955; i P i . A simple example of the content of the previous paragraph is given by the spin of an electron. The spin of an electron along any choice of axis comes in one of two flavors: up or down. (By the way, this is what is "quantum" about quantum mechanics: many attributes of a physical system come in a discrete set of possibilities.) For the sake of completeness, let us say that we are measuring spin along the vertical axis. The state of the electron is given by a unit vector &#968; in the Hilbert space C 2 . We view the usual orthonormal basis te 1 , e 2 u for C 2 as representing the two possible spin values: so e 1 corresponds to up while e 2 corresponds to down. Now a general unit vector &#968; in C 2 can be written in the form &#968; " &#945; 1 e 1 `&#945;2 e 2 for unique complex numbers &#945; 1 , &#945; 2 P C for which</p><p>What is strange and new about quantum mechanics is that a given electron can be in a state that is neither up nor down. More specifically, when neither &#945; 1 nor &#945; 2 are 0, the electron is considered to be in a superposition of the two states and will only reveal one of these two states upon a measurement of the spin, that is, using the PVM P 1 , P 2 on C 2 consisting of the projections onto the coordinate axes. The state of the electron merely gives us probabilistic information as to which of the two outcomes will happen upon such a measurement. Moreover, once the measurement has been made, the new state of the electron instantaneously and discontinuously jumps to the unit vector e 1 or e 2 corresponding to the outcome of the measurement just made. This reflects the fact that if another measurement is made directly following the first measurement, the same outcome will occur. It is important to make the distinction between superpositions and definite measurement outcome with probabilities measuring ignorance of the actual value.</p><p>The above description of quantum mechanics is the standard or Copenhagen interpretation, and it is a mighty big pill to swallow upon a first reading. (Technically speaking, this is really the von Neumann-Dirac formulation of the theory; however, it has become common parlance to refer to this interpretation as the Copenhagen interpretation, even though Niels Bohr himself explicitly disagreed with this formulation.) Perhaps the biggest point of contention are the questions, "What constitutes a measurement?" together with the follow-up question "Why did the state of the electron collapse to one of the two basis states?" This is the so-called measurement problem and is a very popular topic of debate amongst philosophers and theoretical physicists. It has lead to a plethora of alternate interpretations of quantum mechanics (often yielding mathematically equivalent predictions); a good introduction to these foundational issues is Barrett's recent book <ref type="bibr">[6]</ref>.</p><p>To keep the strangeness coming, suppose that we want to measure spin in the horizontal direction instead of the vertical direction. It turns out that the appropriate basis to consider is now tv 1 , v 2 u, where v 1 " 1 ? 2 e 1 `1 ? 2 e 2 and v 2 " 1 ? 2 e 1 &#180;1 ? 2 e 2 . In other words, the PVM Q 1 , Q 2 consisting of the orthogonal projections onto the lines spanned by v 1 and v 2 , respectively, constitutes a measurement of the spin of the electron in the horizontal direction. Suppose that an electron has a definite spin, say up, in the vertical direction, whence its state is e 1 . In the eigenbasis for the observable of spin in the horizontal direction, the state becomes e 1 " 1 ?</p><p>Consequently, a measurement of an electron with an up spin in the vertical direction will yield a spin of either left or right in the horizontal direction with equal probability. Even more strangely, suppose that the electron that had a definite vertical spin that was up was then measured in the horizontal direction and the outcome was spin left; that is, the measurement led to an outcome state of v 1 . Suppose further that a subsequent measurement of the electron in the vertical direction was performed. Since v 1 " 1 ? 2 e 1 `1 ?</p><p>2 e 2 , we see that the outcome of the measurement now yields up or down with equal probability. Thus, the measurement in the horizontal direction destroyed the definite spin the electron had in the vertical direction! 5.2. The spookiness of entanglement. The postulates of quantum mechanics tell us that if H A and H B are the Hilbert spaces representing two physical systems, then the appropriate Hilbert space for studying the composite system is the tensor product space H A b H B . The fact that elements of the tensor product need not be merely simple tensors leads to the fascinating concept of entanglement, which, in some sense, is the essence of this entire story!</p><p>In order to get an idea of the utility of entanglement as a resource in, say, quantum information theory, we present the example of superdense coding. We set &#968; EP R :" 1 ? 2 pe 1 b e 1 `e2 b e 2 q P C 2 b C 2 -C 4 . This quantum state is known as the EPR state, named after Einstein, Podolsky, and Rosen. Shortly, we will have more to say about this state and why Einstein, Podolsky, and Rosen were considering it. Let us imagine that Alice and Bob each possess an electron and the joint state of the vertical spins of the two electrons is &#968; EP R , that is, the electrons are in an equal superposition of both spins being up or both spins being down. Furthermore, imagine that Alice and Bob are really (really) far away from each other. We show how Alice and Bob can utilize the fact that their electrons are in this entangled state in order for Alice to send two classical bits of information to Bob by just sending one qubit of information, that is, by Alice sending Bob her electron (after she has first done some work on it).</p><p>Depending on what two bits of information Alice wishes to send to Bob, she performs one of the following actions to her electron:</p><p>Here, X " &#710;0 1 1 0 &#729;, the so-called bit-flip operator, and Z " &#710;1 0 0 &#180;1&#729;, the so-called phase-flip operator.</p><p>Remove Watermark</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Wondershare PDFelement</head><p>One can check that the four vectors &#968; 11 , &#968; 12 , &#968; 21 , &#968; 22 form an orthonormal basis for C 2 b C 2 -C 4 known as the Bell basis. Consequently, any observable O on C 4 with distinct eigenvalues and with the Bell basis vectors as eigenvectors can be used to distinguish these vectors, that is, when the state of the system is &#968; ij , a measurement of O will yield &#968; ij with probability 1, whence Bob knows which of the four actions above Alice took and thus knows which pair of bits she wished to send to Bob. (One can be explicit about the observable O, namely O " pH b I C 2 qC, where H :" 1 ? 2 pX `Zq is the so-called Hadamard operator and C is the so-called controlled not operator.)</p><p>Notice something peculiar about the EPR state? If the state of two electrons is given by &#968; EP R , then they are in a superposition of either both electrons having spin up or both electrons having spin down (with equal probability). However, if Alice performs a measurement of the spin of her electron and sees a result of spin up, she knows, with absolute certainty, that a subsequent measurement of the spin of Bob's electron will also be spin up. Thus, while Bob's electron did not have a determinate spin before Alice's measurement, the result of Alice's measurement instantaneously gave a determinate value to the spin of Bob's electron.</p><p>Einstein was worried by this phenomenon, which he called "spooky action at a distance." Together with Podolsky and Rosen <ref type="bibr">[17]</ref>, they used the EPR state to present an argument for the incompleteness of quantum mechanics. The gist of the argument is as follows: Suppose that Alice and Bob share a pair of electrons in the EPR state &#968; EP R , and that Alice and Bob are again really (really) far apart. Suppose that Alice measures her electron and sees the result spin up. Then Alice knows with 100% certainty that if Bob were to measure his electron, then it must also have a determinately up spin. The same holds for a measurement result of spin down. Since Alice can predict with certainty the outcome of Bob's measurement, and since her measurement could not possibly have altered the spin of Bob's electron, Bob's spin must have a definite value, independent of whether or not Alice were to measure it. This definite value must represent some element of physical reality and if quantum mechanics were to be complete, there must be some counterpart of this physical reality in the theory. Since there is nothing in the description of the EPR state which specifies a determinate value for Bob's spin, quantum mechanics must be incomplete.</p><p>It gets even worse, for if Alice were to decide to measure her spin along a different axis, say the horizontal axis, then once again the result of her measurement would allow her to definitively conclude the value of Bob's electron's spin in the horizontal axis. In this case, both the vertical and horizontal spins would have definite, predetermined values, which is a contradiction of the fact that knowing, say, the vertical spin of an electron forces us to be maximally uncertain about the horizontal spin of the electron. So in some sense, the EPR argument even posits that quantum mechanics is inconsistent!</p><p>The underlying philosophy that Einstein, Podolsky, and Rosen have in their argument is usually dubbed local realism: the term "local" refers to the assumption that Alice's measurement could not have affected Bob's electron since they are so far away and communication cannot travel faster than the speed of light, while the term "realism" refers to the statement that the fact that one can determine the spin of Bob's electron with certainty implies that there must be some real, predetermined value to the spin. Einstein, Podolsky, and Rosen believed that there should be some hidden variable explaining this predetermined spin, allowing them to preserve their classical, locally real intuitions.</p><p>John Bell <ref type="bibr">[7]</ref> set up a thought experiment to determine whether there could indeed be a formulation of quantum mechanics that was complete and adhered to the local realist philosophy. He showed that this is in fact impossible by showing that a small set of local realist assumptions leads to an inequality on the expected outcome of a certain experiment and that a particular quantum measurement could violate that inequality. Moreover, it is actually experimentally testable whether or not this inequality holds in nature. Spoiler alert: the inequality is violated by nature, whence quantum mechanics comes out victorious! Thus, while seemingly strange, quantum mechanics lies in contradistinction to the local realist assumptions.</p><p>Besides being an intellectually fascinating story, there turns out to be a direct link between these Bell inequalities and the phenomena of having quantum strategies for nonlocal games that exceed all possible classical values, which we now explain. (The idea of treating the violation of Bell-type inequalities as quantum strategies for nonlocal games that exceed the classical value of the game seems to have first been seriously studied by Cleve, Hoyer, Toner, and Watrous <ref type="bibr">[14]</ref>).</p><p>We have already discussed deterministic strategies for nonlocal games. One may imagine incorporating a probabilistic component to these strategies by considering a probability space p&#937;, &#956;q and determinstic strategies A &#969; : rks &#209; rns and B &#969; : rks &#209; rns, one for each &#969; P &#937;. Consequently, the players can randomly (according to p&#937;, &#956;q) select an &#969; and then play deterministically according to A &#969; and B &#969; . In terms of the EPR experiment, one may think of &#969; as the hidden variable for which we do not have perfect knowledge but that if we were to know it, then things would behave deterministically. The probability space p&#937;, &#956;q represents our epistemic (lack of) knowledge of the hidden variable. Consequently, we now have probabilistic strategies ppa, b|x, yq :" &#956;pt&#969; P &#937; : A &#969; pxq " a and B &#969; pyq " buq, which are called local strategies, the term "local" referring to the fact that each player's output still only depends on their local environment. The set of such local strategies is denoted C loc pk, nq. It is straightforward to see that C loc pk, nq is a compact, convex subset of r0, 1s k 2 n 2 whose extreme points are the elements in C det pk, nq. Moreover, it is clear that every element of C loc pk, nq is a convex combination of elements of C det pk, nq, whence valpGq " sup pPC loc pk,nq valpG, pq for any nonlocal game G with k questions and n answers.</p><p>On the other hand, we can consider quantum strategies for nonlocal games as follows. We let C q pk, nq consist of those strategies p for which ppa, b|x, yq " xpA x a b B y b q&#968;, &#968;y, where, for each x, y P rks, A x " pA x a q aPrns and B y " pB y b q bPrns are POVMs with n outcomes on finite-dimensional Hilbert spaces H A and H B , respectively. We call such a strategy p a quantum strategy. These stratgies correspond to Alice and Bob sharing a (possibly entangled) state &#968; of their composite system H A b H B and performing measurements A x and B y on their portion of the state upon receiving questions x and y, respectively. Using a technique known as Naimark dilation (a special case of the Stinespring dilation theorem from above), one can replace POVMs with the more convenient to use PVMs without altering the definition of C q pk, nq. It is a straightforward argument to show that C q pk, nq is a convex subset of r0, 1s k 2 n 2 .</p><p>We have that C loc pk, nq &#270; C q pk, nq. Indeed, since every element of C loc pk, nq is a convex combination of deterministic strategies and C q pk, nq is convex, it suffices to show that every determinstic strategy p is contained in C q pk, nq. However, this is quite easy: if A : rks &#209; rns is the function determining Alice's strategy, let A x be the POVM on C for which A x Apxq " I and A x a " 0 for all a " Apxq. Bob's POVM B b y is defined in the analogous way. It follows that, for any state &#958; P C b C, we have that ppa, b|x, yq " xpA x a b B y b q&#958;, &#958;y. Given a nonlocal game G, we define its entangled value to be val &#730;pGq :" sup pPC q pk,nq valpG, pq.</p><p>By the previous paragraph, we have that valpGq &#271; val &#730;pGq for any nonlocal game G. The idea behind Bell's theorem, recast in the setting of nonlocal games, is that there are nonlocal games G for which valpGq &#259; val &#730;pGq.</p><p>For example, we consider the following game, known as the CHSH game. (The acronym CHSH stands for Clauser, Horne, Shimony, and Holt, the researchers responsible for the CHSH inequality, a Bell-type inequality that was one of the first to be experimentally testable.) The CHSH game G CHSH is a game with k " n " 2. The question distribution is the uniform distribution on r2s &#710;r2s and with decision predicate D given by the following conditions. &#8218; If x " 1 or y " 1, then Alice and Bob win if and only if their answers agree. &#8218; If x " y " 2, then Alice and Bob win if and only if their answers disagree.</p><p>By inspecting all determinstic strategies, one finds that valpG CHSH q " 3 4 . However, the entangled value of the game satisfies val &#730;pG CHSH q " cos 2 p &#960; 8 q &#171; 0.85 &#261; valpG CHSH q. The interested reader can find the details for this calculation in [14, Section 3.1]. We merely point out that a quantum strategy for achieving val &#730;pGq uses the EPR state &#968; EP R .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.3.">MIP*.</head><p>Based on the nonlocal game definition of the complexity class MIP and our recent discussion of quantum strategies for nonlocal games, it should be clear how to define the complexity class MIP &#730;: the language L belongs to MIP if there is an efficient mapping (in the precise sense from Subsection 4.4) z &#222; &#209; G z from strings to nonlocal games such that:</p><p>3 . We remark that the definition of MIP &#730;first appeared in the aforementioned paper <ref type="bibr">[14]</ref>.</p><p>To be fair, we are really defining the complexity class MIP &#730;p2, 1q, which only has two provers and one round of interactions. There are ways to define similar classes that allow more verifiers and rounds, but the eventual result MIP &#730;" RE will show they yield the same class anyways, so we will not bother.</p><p>So how do the classes MIP and MIP &#730;relate? The lesson from the previous section was that provers that share entanglement can win some nonlocal games more often than they rightfully should. In other words, it seems that it might be the case that for a language L that belongs to MIP and for a string z that does not belong to L, the provers might have a strategy for the corresponding game G z whose value exceeds 1  3 . Nevertheless (and perhaps somewhat surprisingly), Ito and Vidick <ref type="bibr">[38]</ref> showed that MIP &#270; MIP &#730;. The rough idea behind this inclusion is that it suffices to show that NEXP &#270; MIP &#730;, and the games involved in the proof that MIP " NEXP are such that their classical and quantum values are approximately the same.</p><p>Later, Natarajan and Wright <ref type="bibr">[46]</ref> showed that NEEXP &#270; MIP &#730;. Recalling that MIP " NEXP NEEXP, this shows that MIP MIP &#730;, whence adding entanglement does indeed strictly increase the computational power of the verifier.</p><p>So exactly how much extra power does entanglement give us? Besides the result mentioned in the last paragraph, there was only an a priori seemingly silly upper bound on MIP &#730;, namely MIP &#730;&#270; RE, where RE (which is short for recursively enumerable) is the complexity class which consists of those languages L for which there is a Turing machine M (with absolutely no efficiency requirements whatsoever) whose domain is L; that is, L consists of the set of inputs for which M halts. An alternative formulation of RE is helpful: L belongs to RE if there is a total computable function whose range is L (this is why modern computability theorists refer to this as being computably enumerable or CE ). To see the inclusion MIP &#730;&#270; RE, note first that, given any dimension d, one can effectively enumerate a countable set of quantum strategies of dimension d that is dense in the set of such strategies and for which one can effectively compute valpG, pq for any such quantum strategy p. By letting d tend to 8, if one ever finds such a strategy p for which valpG z , pq &#261; 1  3 , one knows that z P L (and one is guaranteed that this will happen for some such p if z P L). Note that if z R L, this procedure will never convince us that z R L because maybe we did not wait long enough, and a higher-dimensional strategy would indeed have convinced us if we were just a bit more patient.</p><p>The amazing fact proven in <ref type="bibr">[39]</ref> is that this upper bound is actually tight! That is, MIP &#730;" RE holds! More specifically, the authors prove that there is an effective mapping M &#222; &#209; G M from (codes for) Turing machines to nonlocal games such that:</p><p>&#8218; If M halts on the empty tape, then val &#730;pG M q " 1. &#8218; If M does not halt on the empty tape, then val &#730;pG M q &#271; 1 2 . The language consisting of codes for Turing machines that halt on the empty tape is known as the halting problem HALT. Since the halting problem is complete for the class RE, the inclusion RE &#270; MIP &#730;holds.</p><p>Regardless of your interest in CEP, the equality MIP &#730;" RE is an amazing fact. The halting problem is an undecidable problem (this follows from a simple diagonalization argument together with the fact that there is a so-called universal Turing machine). Nevertheless, if two cooperating but noncommunicating provers share some quantum entanglement, they can reliably convince a verifier whether or not a given Turing machine halts! This is a landmark intellectual achievement.</p><p>The proof of MIP &#730;" RE is very complicated, and we will not discuss it here. The introduction to <ref type="bibr">[39]</ref> does a great job outlining the essence of the proof.</p><p>The story of MIP &#730;is about allowing quantum resources but keeping the computational model classical. Further, it is interesting to ask what happens if we also replace the computational model we are using (i.e., the Turing machine) with a quantum computational model (e.g., quantum circuits). It turns out that there is nothing to be gained here: by prefixing the corresponding classical complexity class with a "Q" to denote its counterpart defined using a quantum computational model, we have QIP " IP, QMIP " MIP, and QMIP &#730;" MIP &#730;" RE; see <ref type="bibr">[62]</ref> for the details.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>6.</head><p>From MIP &#730;" RE to the failure of CEP:</p><p>the traditional route</p><p>The derivation of the negative solution to the CEP from MIP &#730;" RE now proceeds in two steps: We first show how MIP &#730;" RE leads to a negative solution to Tsirelson's problem in quantum information theory; we show this in the first subsection. In the second subsection, we then show how a negative solution to Tsirelson's problem naturally leads to a negative solution to Kirchberg's QWEP problem. As we already observed in 3.10, this leads to a negative solution to the CEP.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6.1.">A negative solution to Tsirelson's problem.</head><p>In order to explain Tsirelson's problem, we need to introduce some more collections of strategies. First, we define C qs pk, nq exactly as in the definition of C q pk, nq, except that we remove the finite-dimensionality assumptions on Alice's and Bob's state spaces H A and H B ; a strategy in this larger class is called a quantum spatial strategy. Quantum spatial strategies still correspond to the idea that Alice and Bob each have their own physical system and the state of their composite system is given by the tensor product. It can be checked that there is no loss of generality in restricting our attention to separable Hilbert spaces in the definition of C qs pk, nq. Moreover, by considering projections onto larger and larger finite-dimensional subspaces, we see that C qs pk, nq &#270; C q pk, nq, the closure of C q pk, nq in the usual topology it inherits from being a subset of r0, 1s k 2 n 2 . Like C q pk, nq, one can check that C qs pk, nq is convex.</p><p>There is another model that is natural to consider which arises in quantum field theory. In quantum field theory, one usually considers a large quantum system (maybe the system describing the whole universe!) and then it may be difficult to separate Alice and Bob's systems as isolated subsystems of the larger system. The state of the large system is now given by some unit vector &#958; in a single Hilbert space H, and Alice's and Bob's measurements are now given by families of POVMs pA x q xPrks and pB y q yPrks acting on this single Hilbert space H. Since we are still assuming that Alice and Bob are far away and so they cannot interact with each other, it is natural to assume that either of them can measure first without affecting the value of the other's measurements (or even that they can perform their measurements simultaneously). According to von Neumann, the mathematical way of modeling this situation is to assume that Alice's and Bob's measurements commute with one another, that is, A x a B y b " B y b A x a for all x, y P rks and all a, b P rns. The corresponding strategy is given by ppa, b|x, yq " xA x a B y b &#958;, &#958;y and is called a quantum commuting strategy. (Commutativity ensures that this a priori complex value lies in r0, 1s.) The set of quantum commuting strategies is denoted C qc pk, nq. Note that there is no requirement that H be finite dimensional (although one can take it to be separable) and, in fact, requiring H to be finite dimensional yields another description of the set C q pk, nq (see <ref type="bibr">[16]</ref>). Later, we will see that C qc pk, nq is a closed convex subset of r0, 1s k 2 n 2 and that, like C q pk, nq, one can use PVMs instead of POVMs without changing the definition.</p><p>It is clear that C qs pk, nq &#270; C qc pk, nq. In <ref type="bibr">[59]</ref>, Boris Tsirelson claimed (without proof) that equality holds for all pk, nq. After he was questioned about this, he realized that he could not prove this claim. In fact, upon further reflection, he could not even establish whether or not C qs pk, nq was closed nor whether or not C qa pk, nq :" C qs pk, nq " C q pk, nq coincided with C qc pk, nq (see his note <ref type="bibr">[60]</ref>). The question of whether or not C qa pk, nq " C qc pk, nq for all pk, nq is known as Tsirelson's problem. (Incidentally, in <ref type="bibr">[56]</ref> Slofstra showed that Tsirelson's original claim was false, that is, there is a pair pk, nq such that C qs pk, nq " C qc pk, nq, and he even strengthened this result to show that C qs pk, nq need not be closed, that is, there is pk, nq for which C qs pk, nq C qa pk, nq.) Recall that in our discussion of the inclusion MIP &#730;&#270; RE, we discussed how val &#730;pGq can be effectively approximated from below. On the other hand, it turns out that val co pGq can be effectively approximated from above. This result follows from two facts: &#8218; There is a finitely presented group G G (which in fact only depends on the number of questions and answers in G) and an element &#951; G P C &#730;pG G q such that val co pGq " }&#951; G } (see Corollary 6.3). &#8218; For any finitely presented group G, one can always find effective upper bounds on the operator norm of C &#730;pGq (a result due to Fritz, Netzer, and Thom [25, Corollary 2.2]).</p><p>In Subsection 7.8, we offer a simple model-theoretic proof of the fact that val co pGq can be approximated from above, although, to be fair, we really establish a slightly different version of this fact sufficient to derive the failure of Tsirelson's problem from MIP &#730;" RE. In any event, if val &#730;pGq " val co pGq, that is, if Tsirelson's problem has an affirmative answer, then we can effectively approximate val &#730;pGq " val co pGq both from below and above, which would then imply that all languages in MIP &#730;are decidable, contradicting MIP &#730;" RE! By the way, the argument in the preceding paragraph shows that MIP co &#270; coRE, where MIP co is defined exactly like MIP &#730;but using the commuting value val co of games instead of the entangled value val &#730;, and coRE denotes the class of languages whose complement lies in RE. It is currently unknown if this upper bound is sharp. 6.2. A negative solution to Kirchberg's QWEP problem. In this subsection, we show how a negative solution to Tsirelson's problem yields a negative solution to Kirchberg's QWEP problem. We follow Fritz's presentation <ref type="bibr">[24]</ref> closely.</p><p>We begin by considering the abelian C &#730;-algebra C n . For each a " 1, . . . , n, we let e a denote the ath standard basis element of C n . (We are using a as the index since we are using the notation from nonlocal games.) For any k &#283; 1, we also consider the k-fold free product &#730;k x"1 C n and denote by e x a the version of e a in the xth copy of C n . Proposition 6.1.</p><p>(1) There is a 1-1 correspondence between n-outcome POVMs tA 1 , . . . , A n u in BpHq and ucp maps &#934; : C n &#209; BpHq given by &#934;pe a q :" A a .</p><p>(2) There is a 1-1 correspondence between k-tuples tA x 1 , . . . , A x n u k x"1 of n-outcome POVMs in BpHq and ucp maps &#934; : &#730;k x"1 C n &#209; BpHq given by &#934;pe x a q :" A x a . Proof. The proof of ( <ref type="formula">1</ref>) is easy to check, using that a positive map with commutative domain is automatically completely positive. Part (2) follows from <ref type="bibr">(1)</ref> and a theorem of Florin Boca <ref type="bibr">[11]</ref>, which implies that the individual ucp maps &#934; x : C n &#209; BpHq given by &#934; x pe x a q :" A x a can be jointly extended to a single ucp map &#934; : &#730;k x"1 C n &#209; BpHq.</p><p>We now bring group C &#730;-algebras into the picture, getting us closer to the QWEP problem. We first note that C n -C &#730;pZ n q, where Z n denotes the additive group of integers modulo n. Indeed, let u be a generator of Z n and consider the element z :" &#345; n a"1 expp 2&#960;ia n qe a P C n . It is readily verified that z is an element of UpC n q of order n, whence the assignment u &#222; &#209; z yields a unitary representation Z n &#209; UpC n q, extending to a &#730;-homomorphism C &#730;pZ n q &#209; C n that can be checked to be an isomorphism. (This identification usually goes under the name discrete Fourier transform.)</p><p>Let Fpk, nq :" &#730;k x"1 Z n denote the group freely generated by k elements of order n. We then have C &#730;pFpk, nqq " C &#730;p&#730;k x"1 Z n q -&#730;k x"1 C &#730;pZ n q -&#730;k x"1 C n .</p><p>We abuse notation slightly and let e x a denote the element of C &#730;pFpk, nqq corresponding to e x a P &#730;k x"1 C n . (Another viewpoint is that pe x a q n a"1 denote the spectral projections corresponding to the xth unitary element of C &#730;pFpk, nqq.)</p><p>Here is the main result connecting the QWEP problem and for which ppa, b|x, yq " &#966;pe x a b e y b q. Proof. For the forward direction of (1), we may assume, without loss of generality, that p P C qs pk, nq, say ppa, b|x, yq " xpA x a b B y b q&#958;, &#958;y, where the POVMs A x and B y act on the Hilbert spaces H A and H B , respectively. By Proposition 6.1 and the above identification C &#730;pFpk, nqq -&#730;k x"1 C n , we have ucp maps &#934; A : C &#730;pFpk, nqq &#209; BpH A q and &#934; B : C &#730;pFpk, nqq &#209; BpH B q corresponding to these POVMs. These two ucp maps combine to yield a ucp map &#934; " &#934; A b &#934; B : C &#730;pFpk, nqq b min C &#730;pFpk, nqq &#209; BpH A b H B q. Consequently, we can define a state &#966; on C &#730;pFpk, nqq b min C &#730;pFpk, nqq by setting &#966;pw b zq :" xp&#934;pw b zq&#958;, &#958;y. It is clear that this state &#966; implements p as in the statement of <ref type="bibr">(1)</ref>.</p><p>Conversely, suppose that &#966; is a state on C &#730;pFpn, kqq b min C &#730;pFpn, kqq for which ppa, b|x, yq " &#966;pe x a b e y b q. Concretely represent C &#730;pFpk, nqq &#270; BpHq so that C &#730;pFpk, nqqb min C &#730;pFpk, nqq &#270; BpHbHq. Extend &#966; to a state on BpHbHq, which we will continue to denote &#966;. Since convex combination of vector states are dense in the state space of BpH b Hq, given &#261; 0 there are vectors &#958; 1 , . . . , &#958; n P H b H for which |&#966;pe x a b e y b q &#180;&#345;n i"1 xpe x a b e y b q&#958; i , &#958; i y| &#259; for all x, y P rks and a, b P rns. This shows that p can be approximated by convex combinations of elements of C qs pk, nq. Since C qa pk, nq is closed and convex, we have that p P C qa pk, nq.</p><p>The proof of the forward direction of ( <ref type="formula">2</ref>) is identical to the proof of the forward direction of (1), using the fact that one can combine ucp maps with commuting ranges into a ucp map on the maximal tensor product. For the converse, suppose that &#966; is a state on C &#730;pFpn, kqq b max C &#730;pFpn, kqq for which ppa, b|x, yq " &#966;pe x a b e y b q. Let &#960; &#966; : C &#730;pFpn, kqq b max C &#730;pFpn, kqq &#209; BpHq be the GNS representation corresponding to the state &#966; with cyclic vector &#958;. Set A x a :" &#960; &#966; pe The quotient map Z &#209; Z n yields a quotient map F k &#209; Fpk, nq, leading to a surjective &#730;-homomorphism C &#730;pF k q &#209; C &#730;pFpk, nqq. One can show that this map has a ucp lift C &#730;pFpk, nqq &#209; C &#730;pF k q (see, for example, <ref type="bibr">[24,</ref><ref type="bibr">Lemma D.3]</ref>), whence pC &#730;pFpk, nqq, C &#730;pFpk, nqqq is a nuclear pair if pC &#730;pF k q, C &#730;pF k qq is a nuclear pair. (It can be shown that Fpk, nq contains a copy of F 2 if pk, nq " p2, 2q, whence the converse to the previous sentence also holds in this case.) Consequently, we have the following. In the last subsection, we saw that MIP &#730;" RE implies that Tsirelson's problem has a negative solution. Combined with Corollary 6.5, we now have that the QWEP problem has a negative solution, and thus, coupled with the discussion in Subsection 3.10, we finally have the desired negative solution to the CEP! 7. From MIP &#730;" RE to the failure of CEP: a model-theoretic shortcut</p><p>In this section, we show how ideas from logic yield (in this author's opinion) a more elementary derivation of a negative solution of CEP from MIP &#730;" RE. Much of the material presented in this section represents joint work of the author and Bradd Hart <ref type="bibr">[31]</ref> and <ref type="bibr">[32]</ref>. 7.1. A continuous logic for studying tracial von Neumann algebras. The negative solution to CEP from MIP &#730;" RE presented in this section uses techniques from logic. Consequently, we need to describe an appropriate first-order language in a certain continuous logic for studying tracial von Neumann algebras. (We apologize for the double use of the word "language" in this paper. The complexity-theoretic languages have been denoted using bold letters L; we will use Roman letters L for languages in the sense of logic.)</p><p>For a von Neumann algebra M, we let M 1 denote the operator norm unit ball. Recall that by a &#730;-polynomial ppx 1 , . . . , x n q in the indeterminates x 1 , . . . , x n we mean an expression built from the indeterminates using the &#730;-algebra operations. Let F denote the set of all &#730;-polynomials ppx 1 , . . . , x n q (n &#283; 0) such that, for any von Neumann algebra M, we have ppM n 1 q &#270; M 1 . For example, the following functions belong to F: &#8218; the constant symbols 0 and 1 (thought of as 0-ary functions),</p><p>2 . We then work in the formal language L vNa :" F Yttr R , tr , du, where tr (resp., tr ) denotes the real (resp., imaginary) parts of the trace and d denotes the metric on the operator norm unit ball given by dpx, yq :" }x &#180;y} &#964; . We can then formulate certain properties of tracial von Neumann algebras using the language L vNa as follows.</p><p>Basic L vNa -formulae will be formulae of the form tr ppp xqq or tr ppp xqq for p P F. Quantifier-free L vNa -formulae are formulae of the form f p&#981; 1 , . . . , &#981; m q, where f : R m &#209; R is a continuous function and &#981; 1 , . . . , &#981; m are basic L vNaformulae. Finally, an arbitrary L vNa -formula is of the form</p><p>where each i j P t1, . . . , nu, &#981;px 1 , . . . , x n q is a quantifier-free L vNa -formula, and each Q i is either sup or inf. We think of these Q i 's as quantifiers over the unit ball of the algebra.</p><p>For those keeping score at home, our setup here is a bit more specialized than the general treatment of continuous logic in <ref type="bibr">[8]</ref> (or even the version <ref type="bibr">[20]</ref> presented for operator algebraists), but a dense set of the formulae in <ref type="bibr">[8]</ref> are logically equivalent to formulae in the above form, so there is no loss of generality in our treatment here.</p><p>Also, in order to keep the set of formulae separable and computable, when forming the set of quantifier-free formulae, we really should restrict ourselves to a computable dense subset of the set of all continuous functions R m &#209; R as m ranges over N. (See <ref type="bibr">[31,</ref><ref type="bibr">Section 2]</ref>.) Suppose that &#981;p xq is a formula, M is a tracial von Neumann algebra, and a P M n 1 , where n is the length of the tuple x. We let &#981;p aq M denote the real number obtained by replacing the variables x with the tuple a; we may think of &#981;p aq M as the truth value of &#981;p xq in M when x is replaced by a. For example, if &#981;px 1 q is the formula sup x 2 dpx 1 x 2 , x 2 x 1 q, then &#981;paq M " 0 if and only if a is in the center of M.</p><p>If &#981; has no free variables (that is, all variables occurring in &#981; are bounded by some quantifier), then we say that &#981; is a sentence, and we observe that &#981; M is a real number. Given a tracial von Neumann algebra, the theory of M is the function ThpMq which maps the sentence &#981; to the real number &#981; M . Sometimes authors define ThpMq to consist of the set of sentences &#981; for which &#981; M " 0; since ThpMq, as we have defined it, is determined by its zeroset, these two formulations are equivalent.</p><p>If &#981;p xq is a formula, then there is a bounded interval rm &#981; , M &#981; s &#270; R called the range of &#981; such that, for any tracial von Neumann algebra M and any a P M 1 , we have &#981;p aq M P rm &#981; , M &#981; s.</p><p>At this point we need to mention an important if not seemingly pedantic point (to a nonlogician). We have been focusing our attention on those structures in the language L vNa that actually correspond to (unit balls of) tracial von Neumann algebras. This is a perfectly legitimate thing to do because the class of tracial von Neumann algebras form an elementary class. Perhaps a simpler example from classical logic will help illustrate the point. Let L grp " t&#168;, eu consist of a single binary function symbol &#168;and constant symbol e. Of course, the intended L grp -structures are the ones that interpret these symbols as the multiplication and identity of a group. However, there are perfectly reasonable, if not silly, L grp -structures, such as, for example, one that interprets &#168;as a constant function. The key point is that we can write down a collection of axioms, that is, a set of L grp -sentences T grp , that single out the class of groups in the sense that an L grp -structure G is a group if and only if every sentence in T grp is true in G. This is the definition of what it means for the class of groups to be an elementary class in the language L grp .</p><p>A similar situation is true in our context, namely, there is a collection T vNa of L vNa -sentences such that an L vNa -structure is the unit ball of a von Neumann algebra if and only if each sentence in T vNa evaluates to 0 in the structure. In fact, one can add to these axioms a couple of extra sentences in order to obtain the theory T II 1 whose models are all (unit balls of) II 1 factors.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.2.">The model-theoretic reformulation of CEP.</head><p>An L vNa -sentence &#963; of the form sup</p><p>is called universal if &#981; is quantifier-free and the range of &#981; is nonnegative and similarly existential if all the quantifiers are inf. This terminology is justified if one thinks of the value 0 as true for then &#963; M " 0 if and only if &#981;pa 1 , . . . , a n q " 0 for all a 1 , . . . , a n P M 1 . If we restrict the function ThpMq to the set of all universal (resp., existential) sentences, the resulting function is defined to be the universal (resp., existential ) theory of M, denoted Th @ pMq (resp., Th D pMq).</p><p>It is fairly easy to see that Th @ pMq " Th @ pM U q for any tracial von Neumann algebra M and any ultrafilter U. (The Los theorem <ref type="bibr">[20,</ref><ref type="bibr">Proposition 4.3]</ref> shows that ThpMq " ThpM U q, but we will not need this more general fact.) Consequently, if N embeds into M U , then we have that Th @ pNq &#271; Th @ pMq (as a function). It turns out that the converse is also true. To see this, assume that Th @ pNq &#271; Th @ pMq. To show that N embeds into an ultrapower of M, it suffices (by standard ultrapower arguments) to show, given any finitely many a 1 , . . . , a n P N 1 , any atomic formula &#981;px 1 , . . . , x n q, and any &#261; 0, that there are b 1 , . . . , b n P M 1 such that |&#981;p aq N &#180;&#981;p bq M | &#259; . Set r :" &#981;p aq N and &#963; :" inf x |r &#180;&#981;p xq|. It is clear that &#963; N " 0. The assumption that Th @ pNq &#271; Th @ pMq implies that Th D pMq &#271; Th D pNq, whence &#963; M " 0, which easily implies the existence of the desired tuple b P M 1 . (None of this is particular to the case of tracial von Neumann algebras and holds for any pair of structures in the same language.)</p><p>We can thus reformulate the CEP as follows. For every tracial von Neumann algebra M, we have that Th @ pMq &#271; Th @ pRq. Recalling that R embeds into every II 1 factor, we can further reformulate the CEP-there is a unique universal theory of II 1 factors, namely Th @ pRq.</p><p>7.3. The completeness theorem for (continuous) first-order logic. Before discussing the completeness theorem for II 1 factors in the context of continuous logic, we consider the simpler example of groups in classical logic.</p><p>Consider the following theorem in group theory: every group has a unique identity element. This theorem can be written as an L grp -sentence &#963; e defined by @xp@ypx &#168;y " y &#168;x " xq &#209; x " eq. What exactly does it mean for &#963; e to be a theorem of group theory?</p><p>Syntactically, what this means is that in some formal proof system for first-order logic, there is a formal proof of &#963; e from T grp , denoted T grp $ &#963; e . This formal proof is simply a finite list of sentences, each of which is either an element of T grp or can be obtained from earlier elements of the list using the rules of the proof system, with &#963; e being the last element of the list.</p><p>Semantically, we might say that in every model of T grp , that is, in every group, the sentence &#963; e is true. We denote this relationship by T grp |&#249; &#963; e .</p><p>For any reasonable proof system, it is fairly easy to prove that $ implies |&#249;; this is called the soundness theorem for first order logic. A much less obvious result is that the converse also holds, namely that any time T grp |&#249; &#963;, then in fact T grp $ &#963;. (There is obviously nothing special here about T grp and this works for any classical first-order theory.) This is called the completeness theorem for first-order logic and is due to Einstein's pal Kurt G&#246;del. (See [18, Section 2.5] for a nice treatment.)</p><p>The relevance of the completeness theorem is that if we use some effective coding of the symbols of L grp and the logical symbols, then we can start a computer program running all proofs from T grp and outputting all theorems of T grp . In other words, the language (in the sense of complexity theory) consisting of codes for theorems of group theory belongs to RE. Note that all that was used about T grp is that the set of codes for axioms in T grp itself belongs to RE.</p><p>There are corresponding soundness and completeness theorems for continuous logic due to Ben Yaacov and Pedersen <ref type="bibr">[10]</ref>. Due to the approximate nature of continuous logic, the completeness theorem takes a slightly different form. Restricted to our case of interest, namely T II 1 , it reads: for every L vNa -sentence &#963;, we have supt&#963; M : M a II 1 factoru " inftr P Q &#261;0 : T II 1 $ &#963; &#180;ru.</p><p>Here, &#180;is the function given by r &#180;s :" maxpr &#180;s, 0q. Consequently, the completeness theorem tells us that the largest truth value that &#963; could take in a II 1 factor is the smallest upper bound for &#963; that you could prove from the axioms T II 1 .</p><p>The proof system for continuous logic is still of the form that you can effectively enumerate theorems from an effectively enumerated set of axioms. In particular, since the set of axioms for T II 1 (given in <ref type="bibr">[20]</ref>) is easily checked to be effectively enumerated, we see that the set of theorems of T II 1 belongs to RE. 7.4. CEP and the computability of the universal theory of R. Given a tracial von Neumann algebra M, we say that the universal theory of M is computable if there is an algorithm such that, upon input an L vNa -sentence &#963; and a rational &#261; 0, returns a, b P Q &#261;0 with a &#259; b and b &#180;a &#259; and for which &#963; M P pa, bq. The ideas in Subsection 7.3 allow us to prove the following. Theorem 7.1 <ref type="bibr">(Goldbring and Hart [31]</ref>). If CEP has a positive answer, then the universal theory of R is computable.</p><p>Proof. If CEP holds, then, recalling that R embeds into any II 1 factor, we have, for any universal sentence &#963;, that supt&#963; M : M a II 1 factoru " &#963; R . Consequently, if we start enumerating all proofs from T II 1 and record all instances of theorems of the form &#963; &#180;r, then we know that &#963; R &#271; r and this allows us to effectively enumerate better and better upper bounds for &#963; R .</p><p>On the other hand, we can also effectively enumerate better lower bounds for &#963; R . There are two ways that one can go about this. One way is to write &#963; " sup x &#981;pxq, where &#981;pxq " f p&#964; pp 1 pxqq, . . . , &#964; pp n pxqqq, and each p i is a &#730;-polynomial and f is a computable continuous function, that is, generated from a computable set of connectives. One can then approximately calculate &#981; on matrices of larger dimensions with rational coordinates. (Technically, x is restricted to range over matrices of operator norm at most one, but one can efficiently verify this too.) Another option is to consider the existential sentence &#963; 0 :" M &#963; &#180;&#963;, where M &#963; is an upper bound for &#963; (uniform over all II 1 factors) that is effectively computable from &#963; itself. Since R embeds in every II 1 factor, we once again have supt&#963; M 0 : M a II 1 factoru " &#963; R 0 (this does not use CEP), and thus we can enumerate all proofs from T II 1 and every time we see that &#963; 0 &#180;r, we know that &#963; R &#283; M &#963; &#180;r.</p><p>We run both the upper and lower bound algorithms simultaneously and wait until they output numbers within of each other. 7.5. Synchronous strategies, definable sets, and finishing the proof. Based on Theorem 7.1, in order to refute CEP, it suffices to prove Theorem 7.2: Theorem 7.2 <ref type="bibr">(Goldbring and Hart [32]</ref>). The universal theory of R is not computable.</p><p>We will use MIP &#730;" RE to prove this result. But how? Given a nonlocal game G, the definition of val &#730;pGq resembles a universal sentence in the language L vNa except that it is not a priori clear how to view the set of correlations C qa as something that we can quantify over a II 1 factor.</p><p>Thankfully, a specific subset of C qa can be characterized by a formula that our logic can handle. A strategy p is called synchronous if ppa, b|x, xq " 0 for all x P rks and distinct a, b P rns. That is, p is synchronous if, whenever both players are asked the same question, they always answer with the same answer. We let C s qa pk, nq (resp., C s qc pk, nq) denote the synchronous elements of C qa pk, nq (resp., C qc pk, nq). Given a nonlocal game G with k questions and n answers, we set its synchronous entangled value to be sval &#730;pGq :" sup pPC s qa pk,nq valpG, pq.</p><p>One defines the synchronous commuting value sval co pGq in the obvious way. In general, we have that sval &#730;pGq &#271; val &#730;pGq and sval co pGq &#271; val co pGq. Paulsen et al. <ref type="bibr">[51,</ref><ref type="bibr">Corollary 5.6]</ref> showed that p P C s qc pk, nq if and only if there is a tracial state &#964; on C &#730;pFpk, nqq such that ppa, b|x, yq " &#964; pe x a e y b q. Contrast this result with Theorem 6.2: gone is the maximal tensor product of C &#730;pFpk, nqq with itself, but instead the state is required to be a tracial state. Later, Kim, Paulsen, and Schaufhauser <ref type="bibr">[43,</ref><ref type="bibr">Theorem 3.6]</ref> showed that p P C s qa pk, nq if and only if there is an amenable tracial state &#964; on C &#730;pFpk, nqq such that ppa, b|x, yq " &#964; pe x a e y b q. One definition of an amenable tracial state &#964; on a C &#730;-algebra A is that there is a &#730;homomorphism &#952; : A &#209; R U with a ucp lift A &#209; 8 pRq for which &#964; " &#964; U R &#733;&#952;, where &#964; R is the unique trace on R. There are many alternate characterizations of being an amenable trace showing that this is indeed a robust condition. In fact, Kirchberg used the notion of amenable trace in his proof that, for finite von Neumann algebras, being QWEP is equivalent to being isomorphic to a &#730;-subalgebra of R U .</p><p>In any event, the above characterization of C s qa pk, nq can be used to show that p P C s qa pk, nq if and only if there are n-outcome PVMs pf</p><p>In what follows, we let X n denote the set of PVMs in R U of length n. By the previous paragraph, we have</p><p>Dpx, y, a, bq&#964; pf x a f y b q &#8218;R U .</p><p>We now note two very important facts:</p><p>(1) The value contained in the parentheses is a legitimate first-order formula evaluated in the ultrapower R U of R. (2) The proof of MIP &#730;" RE actually shows that the reduction M &#222; &#209; G M from Turing machines to nonlocal games is such that if M halts, then sval &#730;pG M q " 1.</p><p>From these two facts, it seems like the proof of Theorem 7.2 is complete, for if we could approximately compute the value of any universal sentence in R, then we could approximate sval &#730;pG M q for any Turing machine M and thus be able to decide the halting problem! There is one (not so minor) issue: the supremum in the above display is still not technically allowable in our logic! Indeed, we are taking the supremum over elements from a certain set X n rather than just tuples from the unit ball. However, it turns out that the founders of continuous logic thought long and hard about such suprema and their efforts will pay off tremendously.</p><p>To explain this, we return to classical logic for one moment and the case of groups. Given any group G, its center ZpGq can be defined by the formula &#947;pxq :" @ypxy " yxq, that is, ZpGq " tg P G : &#947;pgq is true in Gu. Consequently, given any formula &#952;pxq, the formula p@x P ZpGqq&#952;pxq represents an actual sentence in classical logic, being shorthand for the more cumbersome @xp&#947;pxq &#209; &#952;pxqq.</p><p>We are faced with a similar situation in the above paragraph. The elements of X n are those that make the formula max &#732;max i"1,...,n dpp i , p i q, max i"1,...,n dpp i , p 2 i q, d &#732;n &#255;</p><p>i"1 p i , 1 &#184;&#553;qual to 0. One would hope that we could thus take the supremum over this set of elements as a shorthand for a more complicated legitimate formula. Unfortunately, such a move is not always possible.</p><p>More generally, given L vNa -formulae &#952;pxq and &#968;pxq, the expression supt&#968;pxq R : &#952;pxq R " 0u is only equivalent to &#963; R for an actual L vNa -sentence &#963; if &#952;pxq satisfies a certain almost-near property; that is, for each &#261; 0, there is a &#948; &#261; 0 such that, for all a P R 1 , if &#952;paq R &#259; &#948;, then there is b P R 1 with &#952;pbq R " 0 and dpa, bq &#259; .</p><p>In the operator algebraic literature, this is usually referred to as a weak stability phenomena. In the model theory literature, this is called being a definable set.</p><p>(See the author's paper <ref type="bibr">[28]</ref> for more on definability in continuous logic and its connection to operator-algebraic matters.) Now here is the fantastic (and fortuitious) part: the formula defining X n above does have this property! And here's the kicker: Kim, Paulsen, and Schaufhauser themselves proved it [43, Lemma 3.5] while establishing their above characterization of C s qa pk, nq. Thus, we are entitled to write the above formula for sval &#730;pGq as a shorthand for a legitimate sentence in the language of continuous logic. There is a little bit of fine print to check, namely that the resulting sentence is in fact universal and that this transformation can be done effectively, but the details can indeed be carried out. This completes the proof of Theorem 7.2 and thus the model-theoretic proof of the negative solution to CEP. 7.6. A G&#246;delian refutation of the CEP. G&#246;del's incompleteness theorem is one of the landmark intellectual achievements of the 20th century. It addresses a seemingly simple question: is there an algorithm such that, upon input a sentence in the language of number theory, returns the truth value of the sentence in the natural numbers? Surprisingly, G&#246;del proved that the answer is no <ref type="bibr">[26]</ref>! (See also <ref type="bibr">[18,</ref><ref type="bibr">Section 3.5]</ref> for a more modern treatment.)</p><p>G&#246;del actually proved something much stronger, namely he proved that any attempt to answer the previous question by giving an effective axiomatization of number theory is doomed to fail. More specifically, there is a natural (and effective) collection of axioms known as Peano arithmetic such that any effective extension T of Peano arithmetic is destined to be incomplete, meaning there will be sentence &#963; that is true in N but not provable from T . Since simply listing all true sentences of N as axioms is obviously complete, it follows that the set of true sentences is not effectively enumerable.</p><p>We can use the ideas in the previous subsection to give a G&#246;delian-style refutation of CEP. Indeed, one can view CEP as the question of asking whether or not the effective list of axioms for being a II 1 factor is enough to axiomatize the universal theory of R. The failure of CEP shows that the answer to this is no. But perhaps there is a stronger, but still effective, list of axioms extending the axioms for being a II 1 factor so that any model of these axioms would then satisfy the conclusion of CEP. Our proof from the previous subsection shows that the answer is still no: Theorem 7.3 <ref type="bibr">(Goldbring and Hart [32]</ref>). There does not exist an effectively enumerable list T of axioms extending T II 1 such that all models of T are embeddable in R U .</p><p>In particular, this shows that the collection of axioms &#963; &#180;r for which &#963; R &#271; r is not effectively enumerable.</p><p>Theorem 7.3 allows us to provide many counterexamples to CEP:</p><p>Corollary 7.4. There is a sequence M 1 , M 2 , . . . , of separable II 1 factors, none of which embed into an ultrapower of R, and such that, for all i &#259; j, M i does not embed into an ultrapower of M j .</p><p>Proof. We construct the sequence inductively. Set M 1 to be any separable II 1 factor that does not embed into an ultrapower of R. Suppose now that M 1 , . . . , M n have been constructed satisfying the conclusion of Corollary 7.4. For each i " 1, . . . , n, let &#963; i be a nonnegative sentence such that &#963; R i " 0 but &#963; M i i &#261; 0. For each i " 1, . . . , n, fix a rational number &#948; i P p0, &#963; M i i q. Let T be the theory of II 1 factors together with the single condition max i"1,...,n p&#963; i &#180;&#948;i q " 0. It is clear that T is an effectively enumerable subset of the theory of R. Thus, by Theorem 7.3, there is a separable model M n`1 of T such that M n`1 does not embed into an ultrapower of R. Given i " 1, . . . , n, since &#963; M i i &#261; &#948; i while &#963; M n`1 i &#271; &#948; i , it follows that M i does not embed into an ultrapower of M n`1 . This indicates how to continue the recursive construction, completing the proof. 7.7. The universal theory of R and the moment approximation problem. In this subsection, we offer a purely operator-algebraic reformulation of the statement that Th @ pRq is not computable, first proven in <ref type="bibr">[32]</ref>.</p><p>Given positive integers n and d, we fix variables x 1 , . . . , x n and enumerate all &#730;-monomials in the variables x 1 , . . . , x n of total degree at most d as m 1 , . . . , m L . (Of course, L " Lpn, dq depends on both n and d.) We consider the map &#956; n,d : R n 1 &#209; D L given by &#956; n,d p aq " p&#964; pm i p aqq : i " 1, . . . , Lq. (Here, D is the complex unit disk.)</p><p>Let Xpn, dq denote the range of &#956; n,d , and let Xpn, d, pq be the image of the unit ball of M p pCq under &#956; n,d . Notice that &#356; pPN Xpn, d, pq is dense in Xpn, dq. Theorem 7.5. The following statements are equivalent:</p><p>(1) The universal theory of R is computable.</p><p>(2) There is a computable function F : N 3 &#209; N such that, for every n, d, k P N, Xpn, d, F pn, d, kqq is 1 k -dense in Xpn, dq. Proof. First suppose that the universal theory of R is computable. We produce a computable function F as in <ref type="bibr">(2)</ref>. Fix n, d, and k, and set :" 1 3k . Computably find s 1 , . . . , s t , an -net in D L . For each i " 1, . . . , t, ask the universal theory of R to compute intervals pa i , b i q with b i &#180;ai &#259; and with pinf x |&#956; n,d p xq &#180;si |q R P pa i , b i q. For each i " 1, . . . , t such that b i &#259; 2 , let p i P N be the minimal p such that when you ask the universal theory of M p pCq to compute intervals of shrinking radius containing pinf x |&#956; n,d p xq &#180;si |q M p pCq , there is a computation that returns an interval pc i , d i q with d i &#259; 2 . Let p be the maximum of these p i 's. We claim that setting F pn, d, kq :" p is as desired. Indeed, suppose that s P Xpn, dq and take i " 1, . . . , t such that |s &#180;si | &#259; . Then pinf x |&#956; n,d p xq &#180;si |q R &#259; , whence b i &#259; 2 . It follows that there is an interval pc i , d i q as above with pinf x |&#956; n,d p xq &#180;si |q M p pCq &#259; d i &#259; 2 .</p><p>Let a P M p pCq realize the infimum. Then |&#956; n,d p aq &#180;s| &#259; 3 " 1 k , as desired. Now suppose that F is as in <ref type="bibr">(2)</ref>. We show that that the universal theory of R is computable. Toward this end, fix a universal sentence &#963; " sup x f p&#964; pm 1 q, . . . , &#964; pm qq, where x " x 1 , . . . , x n , m 1 , . . . , m are *-monomials in x of total degree at most d, and f is a computable connective. Fix also rational &#261; 0. We show how to compute the value of &#963; R to within . Since f is computable, it has a computable modulus of continuity &#948;, meaning that we can find k P N computably so that 1 k &#271; &#948;p q. Set p " F pn, d, 2kq. Computably construct a sequence a 1 , . . . , a t P pM p pCq 1 q n that is a 1 2k cover of pM p pCq 1 q n (with respect to the 1 metric corresponding to the 2-norm). Consequently, &#956; n,d p a 1 q, . . . , &#956; n,d p a t q is a 1 2k -cover of Xpn, d, pq. Set r :" max i"1,...,t f p&#964; pm 1 p a i qq, . . . , &#964; pm l p a i qqq.</p><p>By assumption, Xpn, d, pq is 1 2k -dense in Xpn, dq. It follows that r &#271; &#963; R &#271; r ` , as desired. 7.8. A negative solution to Tsirelson's problem from MIP &#730;" RE. In this subsection, we offer an alternative proof of the negative solution to Tsirelson's problem using MIP &#730;" RE and the completeness theorem; we follow closely the treatment given in <ref type="bibr">[32]</ref>. As in the definition of the synchronous entangled value sval &#730;pGq of a nonlocal game G with k questions and n answers, we define its synchronous commuting value to be sval co pGq :" sup pPC s qc pk,nq valpG, pq. Definition 7.6. Fix 0 &#259; r &#271; 1. We define MIP co,s 0,r to be the set of those languages L for which there is an efficient mapping z &#222; &#209; G z from strings to nonlocal games such that z P L if and only if sval co pG z q &#283; r. Theorem 7.7 <ref type="bibr">(Goldbring and Hart [32]</ref>). For any 0 &#259; r &#271; 1, every language in MIP co,s 0,r belongs to the complexity class coRE. In other words, if L P MIP co,s 0,r , then there is an algorithm which enumerates the complement of L.</p><p>For the remainder of this subsection, we work in the first-order language L &#964;C for tracial C &#730;-algebras, that is, C &#730;-algebras equipped with a distinguished tracial state, which is defined in a manner analogous to the language L vNa used to study tracial von Neumann algebras. Fix a nonlocal game G with k questions and n answers. Let w " pw x,a q xPrks,aPrns denote a tuple of variables, and let &#968; G pwq be the L &#964;C &#730;-formula &#255; set of expressions. Provided that the players address a dense set of moments infinitely often, they can ensure that the play is definitive, meaning that the final set of expressions yields complete information about all &#730;-polynomials over the variables C (that is, for each &#730;-polynomial ppxq and each tuple c from C, there should be a unique r such that the play of the game implies that }ppcq} &#964; " r) and that this data describes a countable, dense &#730;-subalgebra of a unique tracial von Neumann algebra, which is called the compiled structure. In what follows, we assume all plays of the game are definitive.</p><p>8.2. Enforceable properties of tracial von Neumann algebras. Crucial to the connection between the above games and the CEP is the notion of an enforceable property:</p><p>Definition 8.1. Given a property P of tracial von Neumann algebras, we say that P is an enforceable property if there a strategy for D so that, regardless of player @'s moves, if D follows the strategy, then the compiled structure will have property P .</p><p>Perhaps being an enforceable property seems so severe that there are in fact no enforceable properties. We will soon see that many interesting properties are in fact enforceable. First, we mention the conjunction lemma [29, Lemma 2.4]: if P n is an enforceable property for each n P N, then so is the conjunction &#377; n P n . As a first example of an enforceable property of tracial von Neumann algebras, we show that being a factor is enforceable. To see this, let &#952;pxq be the L vNa -formula a }x} 2 &#964; &#180;&#964; pxq 2 , and let &#951;pxq be the L vNa -formula sup y }xy &#180;yx} &#964; . Finally, let &#963; be the L vNa -sentence sup x p&#952;pxq &#180;&#951;pxqq. It was shown in <ref type="bibr">[20]</ref> that a von Neumann algebra M is a factor if and only if &#963; M " 0. To see that being a factor is enforceable, by the conjunction lemma, it suffices to show that, given any n P N and rational &#261; 0, the expression p&#952;pc n q &#180;&#951;pc n qq &#259; is enforceable. To see that this is the case, suppose that player @ opened the game with the open condition &#931;. Without loss of generality, we may suppose that c n appears in &#931;. Since &#931; is satisfiable in some tracial von Neumann algebra, it is also satisfiable in some II 1 factor M (as every tracial von Neumann algebra embeds in a II 1 factor). Consequently, since &#963; M " 0, we see that M also witnesses that &#931; Y t&#952;pc n q &#180;&#951;pc n q &#259; u is a condition, whence D can respond with this condition, as desired.</p><p>We next show that being a II 1 factor is enforceable. Since being a factor is enforceable, it suffices to show that it is enforceable that, in the compiled structure, there is a projection of irrational trace (say 1 &#960; ). By the conjunction lemma again, it suffices to show that, for any rational &#261; 0, there is some n P N for which maxpdpc n , c nq, dpc n , c 2 n q, |&#964; pc n q &#180;1 &#960; |q &#259; is enforceable. Indeed, if this is enforceable, then since almost projections are near actual projections, there will be actual projections in the compiled structure whose trace approaches 1 &#960; , whence there will be an actual projection of trace 1 &#960; , as desired. However, this condition is clearly enforceable by the exact same argument used in the previous paragraph, this time, using a fresh constant, that is, some c n which did not appear in player @'s opening play &#931;.</p><p>One can go even further and show that being a McDuff II 1 factor is enforceable. A II 1 M factor is McDuff if M bR -M. For example, R is McDuff. An alternate formulation for being McDuff will prove useful: M is McDuff if and only if there is a copy of M 2 pCq inside of M 1 X M U . This amounts to showing that for any finite F &#270; M and any rational &#261; 0, there are matrix units pe ij q i,j"1,2 for M 2 pCq for which }rx, e ij s} &#964; &#259; for all x P F and all i, j " 1, 2. Hopefully by now the strategy is apparent: given any open play &#931; for player @, we realize &#931; in some tracial von Neumann algebra M. We then note that &#931; is also realized in M bM 2 pCq and then choose fresh constants c n 1 , . . . , c n 4 and say that they are almost matrix units for M 2 pCq which almost commute with c 1 , . . . , c n . As we let n increase and decrease and using the fact that almost matrix units are near actual matrix units, the result follows using the conjunction lemma.  <ref type="bibr">[19]</ref>, <ref type="bibr">[28]</ref>, and <ref type="bibr">[33]</ref>.</p><p>But can we name a concrete e.c. tracial von Neumann algebra? Well: Theorem 8.2 <ref type="bibr">(Farah,</ref><ref type="bibr">Goldbring,</ref><ref type="bibr">Hart,</ref><ref type="bibr">and Sherman [19]</ref>). R is an e.c. tracial von Neumann algebra if and only if CEP has a positive solution.</p><p>Proof. We first note that if R is e.c., then CEP holds: given a II 1 factor M, we have that R &#270; M, whence, since R is e.c., we have that M embeds into R U . Conversely, suppose that CEP holds; we show that R is e.c. To see this, suppose that R &#270; M with M separable. By CEP, M embeds into R U . At the moment, this does not imply that R is e.c. as the composed embedding R &#227;&#209; R U need not be the diagonal embedding. However, a nontrivial result of Kenley Jung <ref type="bibr">[40]</ref> implies that every embedding &#960; : R &#227;&#209; R U is unitarily conjugate to the diagonal embedding, meaning that there is a unitary element u P R U such that &#960;paq " uau &#730;for all a P R (viewing R as literally a subalgebra of R U via the diagonal embedding). It is straightforward to check that this finishes the job.</p><p>Following <ref type="bibr">[21]</ref>, we call a tracial von Neumann algebra M locally universal if every tracial von Neumann algebra embeds into an ultrapower of M. In this terminology, CEP asks if R is locally universal. The proof of Theorem 8.2 shows the following. </p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_0"><p>PDFelement</p></note>
		</body>
		</text>
</TEI>
