Quantum Games

Nilin Abrahamsen nilin@mit.edu

Daniel Alabi alabid@g.harvard.edu

Mitali Bafna mitalibafna@g.harvard.edu

Emil Khabiboulline ekhabiboulline@g.harvard.edu

Juspreet Sandhu jus065@g.harvard.edu

Two-prover one-round (2P-1R) games have been the subject of intensive study in classical complexity theory and quantum information theory. In a 2P-1R game, a verifier sends questions privately to each of two collaborating provers , who then aim to respond with a compatible pair of answers without communicating with each other. Sharing quantum entanglement allows the provers to improve their strategy without any communication, illustrating an apparent paradox of the quantum postulates. These notes aim to give an introduction to the role of entanglement in nonlocal games, as they are called in the quantum literature. We see how nonlocal games have rich connections within computer science and quantum physics, giving rise to theorems ranging from hardness of approximation to the resource theory of entanglement.

Introduction

In these notes we discuss 2-prover 1-round games and the classical complexity of approximating the value of such games in the setting where the provers can share entanglement. That is, given the description of a game, we ask how hard it is to estimate the winning probability of the best winning strategy of the entangled provers. Let us first formally define games and its relation to the label cover problem. We write .

Definition (Label cover)

A label cover instance consists of variable sets , alphabet set , and a collection of constraints of the form . Given an assignment (or coloring) we define its value to be . Define the value of to be the maximum over all possible assignments, i.e. . Many familiar computational problems can be formulated as a label cover, such as , , and .

Definition (2-prover 1-round game)

Let be a label cover instance. We can then associate the following two-prover one-round game with . Let be two provers who cannot communicate, and let be the verifier. Given the label cover instance , the verifier uniformly samples a constraint and sends to and to . The provers then reply with and respectively to . Finally, outputs if and only if .

Any coloring of the label cover instance corresponds to a deterministic strategy for the corresponding game. Therefore, with an optimal strategy the provers win the game associated to label cover instance with probability . That is, the value of the game equals that of the label cover instance. However, this is with the assumption that provers can only use deterministic strategies or convex combinations of these (that is, using shared randomness). If the provers share an entangled quantum state, then the provers (who still cannot communicate) can enjoy correlations that allow them to win with a higher probability than classically. In the quantum literature, these 2P-1R games are known as nonlocal games referring to the fact that the correlations arise without signaling between the provers. We are concerned with the complexity of approximating the winning probability of this strategy. We refer to the optimal winning probability within some class (classical or entangled) of strategies as the classical and quantum value of the game, respectively, and we use the terms quantum strategy and entangled strategy interchangeably. Fixing different constraint families in the label cover game changes the complexity of finding the (classical and entangled) values of the game. We will show that approximating the entangled value of XOR games, or more generally unique games (to be defined later on), is possible in polynomial time. This is remarkable because a famous conjecture known as the unique games conjecture says that approximating the classical value of unique games is NP-hard. In contrast, we will see that for unrestricted edge constraints, it is NP-hard to approximate the entangled value of a nonlocal game. Thus, hardness of approximation of the game’s value, established by the celebrated PCP theorem , still applies in the presence of entanglement. In the quantum world, we have new complexity classes such as QMA (which can be regarded as “quantum NP”), so one may conjecture whether approximating the entangled value of a general game is QMA-hard (the games formulation of the quantum PCP conjecture ). We will indicate progress in this direction but will explicitly demonstrate the NP-hardness result. Entanglement is often regarded as an expensive resource in quantum information because it is difficult to produce and maintain. Hence, even if sharing entanglement can improve the success probability of winning a game, the resource consumption may be costly. We will conclude by discussing lower bounds on the number of shared entangled bits required to achieve the optimal value of a game.

Notation and quantum postulates

Let us first establish notation and define what is meant by an entangled strategy. In keeping with physics notation we write a column vector as and its conjugate-transpose (a row vector) as . More generally the conjugate-transpose (Hermitian conjugate) of a matrix is written . Then is the inner product of two vectors (a scalar) and the outer product (a rank-1 matrix). A matrix is said to be Hermitian if . A matrix is positive semidefinite , written , if for some matrix . We write the identity matrix as , denote by the set of -by- Hermitian matrices.

Observables, states, and entanglement

In a quantum theory the observables are Hermitian operators on a vector space . It then makes sense to say that a state is a functional on the set of observables. That is, to specify the state of a physical system means giving a (expected) value for each observable. It turns out states are linear functionals of the observables, and such functionals can be written for some -by- matrix . We call the density matrix and require moreover that is positive semidefinite and has trace . Every density matrix is a convex combination of rank-one projections known as pure states. The unit vectors are also themselves known as pure states. If the state of one particle is described by a vector in (referring here to pure states), then two particles are described by a vector in the tensor product . The two particles are entangled if their state is not in the form of a pure tensor . We also write product states as , omitting the tensor symbol.

Quantum measurements

A quantum measurement can be described in terms of a projection-valued measure (PVM). Definition 1 (PVM) A projection-valued measure on vector space (where the quantum states live) is a list of projection matrices on such that for and . The PVM describes a measurement which, on state outputs measurement outcome with probability . The quantum state after obtaining outcome is . When the projections are rank-one projections we say that we measure in the basis . In this case the probability of outcome in state is , and the post-measurement state is simply . Applying the measurement on the left half of a two-particle state means applying the PVM on the two-particle state.

Quantum strategies for nonlocal games

We now introduce the notion of a quantum strategy for a nonlocal game. Each prover holds a particle, say with state space , and Alices particle may be entangled with Bob’s. The global state is . Each player receives a question from the verifier and then chooses a measurement (a PVM) depending on the question. The player applies the measurement to their own particle and responds to the verifier with their measurement outcome. Hence for Alice we specify PVM’s where is a question, and each PVM is a list . By definition 1, given questions the probability that Alice outputs and Bob outputs is

where we have used that squaring a projection leaves it unchanged.

Quantum strategies beat classical ones

For any 2P-1R game , let be the maximum probability — over the players’ classical strategies — that the verifier accepts and the maximum probability that the verifier accepts when the provers use qubits such that player 1’s qubits are entangled with those of player 2. The game of Clauser, Horne, Shimony, and Holt (CHSH) has the property that the provers can increase their chance of winning by sharing an entangled pair of qubits, even when no messages are exchanged between the players. We show that there’s a characterization of the CHSH game’s value which is better than the classical value . Let us first define XOR games, of which the CHSH game is a special case.

Definition (XOR game)

An XOR game is a 2-player classical game (the questions and answers are classical bits) where:

1. Questions are asked according to some distribution (e.g. uniform).
2. Answers are provided by players (call them Alice and Bob).
3. The verifier computes a predicate used to decide acceptance/rejection.

Definition (CHSH Game)

An XOR game with where are independent random bits and . To win the CHSH game, Alice and Bob need to output bits (from Alice) and (from Bob) that disagree if and agree otherwise. If Alice and Bob are classical then they can do no better than by always outputting , say, in which case they win in the three out of four cases when one of the questions is . Equivalently, where is the CHSH game. This is the content of Bell’s inequality :

Lemma (Bell’s Inequality)

For any two functions , we have where and are independent uniformly random bits.
Proof. The probability of any event is a multiple of so it suffices to show that . So assume for contradiction that for all pairs . Then we have that and which implies that . But then which is a contraction.

The strategy

The entangled strategy for the CHSH game requires that Alice and Bob each hold a qubit, so that their two qubits together are described by a vector in . The two qubits together are in the state forming what is known as an EPR (Einstein-Podolsky-Rosen) pair. Now for define and . Now we describe a (quantum) strategy with winning probability . In each case Alice and Bob respond with their measurement outcome, where subscripts of the measurement basis vectors correspond to the answer to be sent back to the verifier.

• If , Alice measures in basis . If , Alice measures in . Alice answers bit if outcome is and answers otherwise.
• If , Bob measures in basis . If , Bob measures in .
• Each player responds with their respective measurement outcome.

Lemma 2 Alice and Bob win the CHSH game with probability .
Proof. We will show that for each pair of questions the pair of answers is correct with probability . We can split the pairs of questions into the two cases and :

• () The three cases are all analogous: in each case Alice an Bob must output the same answer, and in each case Bob’s measurement basis is almost the same as Alice’s except rotated by a small angle . Of the three above cases we consider the one where and check that indeed the two measurement outcomes agree with probability : When Alice measures her qubit and obtains some bit , the shared pair collapses to . Indeed, since the question was , Alice measures her qubit in the basis . This means that Alice applies the measurement on the global state. The post-measurement state is the normalization of because can be viewed as a Kronecker delta of and . In particular, Bob is now in the pure state . Because Bob received question he measures in the basis Therefore his probability of correctly outputting is
• () Now consider the case where Alice and Bob are supposed to give different answers. Alice measures in basis consisting of and . If Alice gets outcome then the post-measurement global state is . Therefore when Bob applies the measurement in basis he mistakenly outputs only with probability .

Lemma 2 implies a lower bound on the value of the CHSH game.

Corollary

It turns out that this lower bound is sharp, that is, the strategy just described is optimal.

Lemma

The value of the CHSH game using a quantum strategy is at most . Proof. We can describe the quantum strategy of Alice and Bob in an XOR game by (i) a shared quantum state (note that for the CHSH game, ); (ii) measurements for every question sent to Alice; (iii) measurements for every question sent to Bob. The probability of answering given questions is . Now let us write and so that for any , we can write Note that since the possible outcomes here are finite, are Hermitian and we may assume have bounded norm of 1. Furthermore, we assume that are observables so that . Now denoting as the XOR predicate to be computed, we can write the quantum game value as where the summation has been evaluated in the last line. Now note that the first term is independent of the quantum strategy and as a result equals the value of the uniformly random strategy which is 1/2. So we proceed to focus on the second term. Note that for CHSH simplifying the second term to Next, we invoke Tsirelson’s Theorem (See Theorem 3) to bound this second term as where we have used Cauchy-Schwartz and the concavity of the function. This completes our proof showing the exact characterization of the value () of the CHSH game using a quantum strategy. This proof is an adaptation of the one in [12]. Theorem 3 (Tsirelson’s Theorem [1]) For any matrix , the following are equivalent:

1. There exist such that for any . Further this would imply that ;
2. There exist real unit vectors for such that ;

Entangled unique games are easy

The CHSH game provides the first example that the entangled value of a nonlocal game can exceed the classical value . XOR-games like the CHSH game are the special case corresponding to alphabet size of the class of unique games :

Definition (Unique Games)

A 2-prover 1-round game is called a unique game if its constraints are of the form where is a permutation of the alphabet for each edge . The famous unique games conjecture (UGC) by Khot says that is NP-hard to approximate for unique games. Surprisingly, Kempe et al. showed that a natural semidefinite relaxation for unique games yields an approximation to the entangled value which can be computed in polynomial time. In other words the UGC is false for entangled provers, in contrast to the classical case where the conjecture is open.
Theorem 4 There is an efficient (classical) algorithm which takes a description of a nonlocal game as its input and outputs such that Put differently, if and , then
The algorithm of theorem 4 proceeds by relaxing the set of quantum strategies to a larger convex set of pseudo-strategies and maximizing over instead of actual strategies, a much easier task. In approximation theory one often encounters a collection of hypothetical moments not arising from a distribution, known as a pseudo-distribution. In contrast, our pseudo-strategies are actual conditional probability distributions on answers (conditional on the questions). What makes a set of “pseudo”-strategies rather than actual strategies is that they may enjoy correlations which cannot be achieved without communication.

Convex relaxation of quantum strategies

We will define to be a class of conditional probability distributions on answers given questions. We will require that the pseudo-strategies satisfy a positive semidefinite constraint when arranged in matrix form. In particular this matrix has to be symmetric, so we symmetrize the conditional probability by allowing each of and to be either a question for Alice or for Bob. That is, we extend the domain of definition for from to where and are the question sets. So each question and and answer and can be either for Alice or Bob — we indicate this by changing notation from to and for the answers replacing by .
Definition 5 (Block-matrix form) Given a function defined on with and , define a -by- matrix whose rows are indexed by pairs and columns by pairs , and whose entries are In other words consists of -by- blocks where the block at position contains the entries .
Definition 5 is simply a convenient change of notation and we identify with , using either notation depending on the context.
Definition 6 (Pseudo-strategies) Let and be the question sets for Alice and Bob, respectively. We say that (or its matrix form ) is a pseudo-strategy if:

1. is positive semidefinite.
2. For any pair of questions , .
3. The blocks on the diagonal are themselves diagonal -by- matrices.

Define the winning probability or value of a pseudo-strategy as: The algorithm outputs the maximum winning probability: over pseudo-strategies . This maximum is efficiently computable using standard semidefinite programming algorithms. As we will see, actual quantum strategies are in which immediately implies . It then remains to show that the optimal pseudo-strategy can be approximated by an actual entangled strategy, thus bounding the gap from to .

Quantum strategies are in

Let us establish that is indeed a relaxation of the class of quantum strategies, that is, it contains the quantum strategies. So suppose we are given a quantum strategy. By equation 1 the probability of answers and given questions and is of the form for some PVM’s and and some . This conditional probability distibution is not immediately in the form of a pseudo-strategy because we cannot evaluate it on pairs of Alice-questions or pairs of Bob-questions. We therefore have to extend it, as follows: Place all the column vectors , side by side, and then append the vectors , resulting in a -by- matrix . We then define through its matrix form (see the comment below definition 5):

Lemma 7 defined in 2 is a pseudo-strategy, that is, .
Proof. We verify the conditions in definition 6. Condition 1 () holds because it is of the form . Condition 2 (Each block sums to ) holds because PVM’s sum to the identity. Condition 3 (Diagonal blocks are diagonal) holds because the projections in the PVM are mutually orthogonal, hence if . Lemma 7 means is an (efficiently computable) upper bound for :

Corollary

.
To finish the proof of theorem 4 we need to show that any pseudo-strategy can be rounded to an actual quantum strategy with answer probabilities such that

Applying this rounding to the optimal pseudo-strategy implies that or , which will finish the proof of theorem 4.
Proof.[Proof of theorem 4] Let be a pseudo-strategy. We construct a quantum strategy approximating . Since is positive semidefinite we can write for some matrix and . Now let us define vectors and in , and let and be the same vectors normalized. The strategy is constructed as follows. Alice and Bob share the maximally entangled state Before deciding on Alice and Bob’s PVM’s and let us see what this choice of shared state means for the conditional distribution on answers (see equation (1)).

, (*)

where the bar represents entrywise complex conjugation, is the entrywise dot product of matrices, and the entrywise complex inner product (Hilbert-Schmidt inner product). We now choose the measurements. Given question , Alice measures in the PVM with Similarly, Bob on question applies the PVM with The condition 3 in definition 6 ensures that for any question , the vectors are orthogonal so that this is a valid PVM. The measurement outcome “” is interpreted as “fail”, and upon getting this outcome the player attempts the measurement again on their share of a fresh copy of . This means that the strategy requires many copies of the entangled state to be shared before the game starts. It also leads to the complication of ensuring that with high probability the players measure the same number of times before outputting their measurement, so that the outputs come from measuring the same entangled state. By (*), at a given round of measurements the conditional distribution of answers is given by We wish to relate the LHS to , so to handle the factor each prover performs repeated measurements, each time on a fresh copy of , until getting an outcome . Moreover, to handle the factor , each prover consults public randomness and accepts the answer with probability and respectively, or rejects and start over depending on the public randomness. Under a few simplifying conditions (more precisely, assuming that the game is uniform meaning that an optimal strategy exists where the marginal distribution on each prover’s answers is uniform), we can let for all , and one can ensure that the conditional probabilities of the final answers satisfy

At this stage it is important that we are dealing with a unique game . Indeed, by (4) we have for every and , where the last inequality follows from concavity. Taking the expectation over and implies the bound (3), thus concluding the proof of theorem 4.

General games are hard

We just saw that a specific class of games becomes easy in the presence of shared entanglement, in that semidefinite programming allows the entangled value to be approximated to within exponential precision in polynomial time. Does this phenomenon hold more generally, so that the value of entangled games can always be efficiently approximated? We answer in the negative, by constructing a game where is NP-hard to approximate to within inverse-polynomial factors. The complexity for 2P-1R entangled games can be strengthened to constant-factor NP-hardness, putting it on par with the classical PCP theorem. This result is used to prove (with some conditions) the games formulation of the quantum PCP theorem, which states that the entangled value of general games is QMA-hard to approximate within a constant factor.

Formulation of game

Given any instance of a -CSP (constraint satisfaction problem, where is the number of literals), we can define a clause-vs-variable game (see clause-vs-variable figure):

1. The referee (verifier) randomly sends a clause to Alice (first prover) and a variable to Bob (second prover).
2. Alice and Bob reply with assignments.
3. The referee accepts if Alice’s assignment satisfies the clause and Bob’s answer is consistent with Alice’s.

To show hardness of approximation, we need to go beyond the usual 2-player construction. In particular, in our game [3] one of the players receives an extra dummy question (see subfigure (a)). Mathematically, the result is very similar to introducing another player and having the referee play the 2-player game with two players chosen randomly [4] (see subfigure (b)). In either variation, the quantum phenomenon of monogamy of entanglement , imposing that only two parties can be maximally entangled to one another, is key to establishing hardness. The players do not know where to use their entanglement, which prevents them from coordinating as well as they could in the standard game.

NP-hardness of approximating the entangled value

To prove hardness, we rely on several results from classical complexity theory.
Theorem 8 ([6]) Given an instance of 1-in-3 3SAT (a CSP), it is NP-hard to distinguish whether it is satisfiable or no assignments satisfy more than a constant fraction of clauses.
Theorem 9 ([2]) For a PCP game (emulating the CSP) and its oracularization (transformation to a 2P-1R game),

Theorem 8 establishes the CSP variant of the classical PCP theorem: distinguishing between and is NP-hard for some -CSP. Here, denotes the maximum fraction of clauses that are simultaneously satisfiable. Theorem 9 relates the general game obtained from the CSP to a two-player one-round game , in terms of the value (probability of winning) the game. The first inequality, equivalently saying , is achieved since the players can answer the questions in the game to satisfy the clauses in . These theorems together imply that is NP-hard to approximate to within constant factors. Allowing the two players to share entanglement can increase the game value to . Classical results do not necessarily carry over, but exploiting monogamy of entanglement allows us to limit the power of entangled strategies. One can show the following lemma, which is weaker than what we have classically.
Lemma 10 ([3]) There exists a constant such that for a CSP ,

where is the number of variables. Combining Theorem 9 and Lemma 10, we have Using Theorem 8, approximating is NP-hard to within inverse polynomial factors. Proving Lemma 10 takes some work in keeping track of approximations. For simplicity, we will show a less quantitative statement and indicate where the approximations come in.
Proposition 11 (adapted from [13]) is satisfiable iff .

Proof of Proposition 11

The forward direction is straightforward: If is satisfiable, then there exists a perfect winning strategy where the questions are answered according to the satisfying assignment. For the reverse direction, suppose there exists a strategy that succeeds with probability 1, specified by a shared entangled state and measurements for Alice and for Bob, where the questions , and the answers are from the CSP’s alphabet. Since one of the questions/answers for Bob corresponds to a dummy variable that is irrelevant to the game, trace over the dummy variable to define a new measurement operator . We can introduce a distribution on assignments to the relevant variables,

If we show that the distribution for assignments on variables in any clause is

then, since the players win with certainty, has a satisfying assignment. To transform Eq. 7 to Eq. 8, we need a relation between the and measurement operators and a way to commute the operators. The success probability of the players’ strategy is expressed as where is the index of one of the variables on which acts, and indicates that the assignment satisfies the clause. By positivity and summation to identity of the measurement operators and , each term is at most 1; for our hypothesis , each has to be 1. Hence, using orthogonality of the vectors for different , we have

for any and . We now demonstrate that two different , commute, so that Bob can match any satisfied clause/variable. In the second line, we used (9) to relate the measurements. The third line follows by the orthogonality of for different . For the fourth equation, we simply swap since the questions are indistinguishable to Bob. Thus, we can see how the dummy variable comes into play. If we had assumed and kept track of approximations, we would find

This approximate commutativity results in the hardness of approximation holding only to within inverse poly factors. Now we are ready to transform Eq. 7 to Eq. 8 to conclude the proof. In the second line, we used (10) to commute the measurement operators, along with their properties of orthogonality and summation to identity. For the third equality, we used (9) to relate Bob’s measurements to Alice’s, along with orthogonality of for different .

Constant-factor NP-hardness

The weakness in the above two-player game carries over from the original three-player variant. Thus, to achieve constant-factor NP-hardness of approximation, we could start with a different multiplayer game. Vidick [11] establishes the soundness of the “plane-vs-point” low-degree test (checking that the restriction of a low-degree polynomial to a plane matches its value at some point) in the presence of shared entanglement. Soundness , in the eponymous probabilistically checkable proof (PCP) formulation of the PCP theorem, refers to the verifier accepting a wrong proof with some bounded probability; bounding with a constant maps to constant-factor hardness of approximation. Here, soundness comes from a strong bound on error accumulation, similar to our approximate commutativity, but relies on the players’ Hilbert space being decomposable into three parts (i.e., there being three players). The particular game is constructed by combining the low-degree test with the 3-SAT test (encoding satisfying assignments in a low-degree polynomial), which can be reduced to the three-player QUADEQ test (testing satisfiability of a system of quadratic equations in binary variables, which is NP-complete). By the strong soundness result, the entangled value is NP-hard to approximate to within constant factors. Natarajan et al. [7] show that soundness holds even for two players, using a semidefinite program. They then construct a two-player game in a way similar to what we demonstrated.

Constant-factor QMA-hardness

The above can be thought of as the games formulation of the classical PCP theorem holding under shared entanglement. A true quantum PCP theorem states that the entangled value of general games is QMA-hard to approximate to within constant factors. Natarajan et al. [8] establish such a theorem, but under randomized reductions. This requirement stems from the lack of a sufficiently strong QMA-hardness result for local Hamiltonians (the quantum analog of CSPs). The soundness of the two-player low-degree test above is one instrumental component in the proof.

How much entanglement is needed?

We now focus on the question of quantifying exactly how much entanglement is needed to play XOR games optimally. As we shall see, the answer depends on the size of the question sets posed to Alice & Bob in the game. The previous bound given by Tsirelson [10] (see table below) is tight for certain families of games, but is not tight for other families of games (such as a generalization of the CHSH game). The reason for this discrepancy is closely tied in with the the properties of the representation of the Observables that form the Optimal Strategy (). Slofstra [9] shows that if the Observables constitute a Clifford Algebra (that is, the solutions are pair-wise anti-commutative), then the strategy is minimally entangled (uses the least number of entangled bits) iff the strategy is a unique solution to the SDP rounding problem. As a trivial corollary, if the SDP rounding problem does not have a unique solution (and a correspondingly unique strategy), then there exists a Non-Clifford optimal strategy that uses (atleast) bits of entanglement less than the Clifford strategy. Slofstra further states that minimally entangled -optimal strategies may be constructed for XOR games where the optimal strategies have ‘stable’ representations. For the purposes of this post, we will analyze the exact result and merely state the approximate result.

Main Results

EXACT

For the exact realm, the table below summarizes Slofstra and Tsirelson’s main results.

Person	Strategy	Bound(entangled bits)
Slofstra	(Possibly) Non-Clifford
Tsirelson	Clifford

Here, is the largest integer such that and corresponds to the maximum-rank of an extremal point in the quantum correlation matrix corresponding to an optimal strategy. is the minimum dimension of the representations of the Operators ().

APPROXIMATE

In the approximate realm, the minimum entanglement dimension of the representation of the Operators from an -Optimal Strategy is: min(). As we shall see, Slofstra’s theorem allows us to recover Tsirelson’s bound easily by using a fact from Representation Theory about the irreducible representations of Clifford Algebras, but stands as a more general lower bound for solutions that aren’t Clifford.

Marginals and Solution Algebras

We’ll begin by introducing 3 key ideas: i) Degeneracy Non-Degeneracy ii) Existence of Marginals iii) Solution Algebra Once these ideas are defined and their notions made clear, we will be in a position to state the main result and sketch a proof for it.

Definition (Marginal Strategy)

Given an Optimal Quantum Strategy (), a marginal constitutes , and the partial trace of with respect to (). It is also possible to dualize the definition for obtaining and . We now define the notion of degeneracy, which is critical when proving the main theorem. The main point to drive home is that a degenerate optimal quantum strategy can be reduced to a unique, non-degenerate optimal quantum strategy.

Definition (Degenerate Quantum Strategy)

A quantum strategy () is said to be degenerate if , such that: i) commutes with all and ii) commutes with all and Since we can efficiently construct for any degenerate Optimal Quantum Strategy a unique, non-degenerate Optimal Quantum Strategy, we will now assume WLOG that every Optimal Quantum Strategy is non-degenerate (and unique). We now define the (unique) existence of marginal biases, which correspond to constants for the rows of the quantum correlation matrix (which is a generalization of the classical pay-off). An equivalent statement can be made for columns () by dualizing the existence of row marginals. These constants can be thought of as representing the (expected) optimum-payoff possible for a set of operator choices by one player, given that the other player’s choice is fixed. Intuitively, this can be seen as “collapsing” the quantum correlation matrix into a column, by summing over the rows (or collapsing into a row, by summing over the columns).
Lemma 12 (Existence of Marginals) For all XOR games G, , such that, if form an -optimal vector strategy where ,

If and our strategy is perfectly optimal, we recover an exact estimation of the marginal biases:

The proof for the above lemma provided by Slofstra relies on using techniques to analyze the structure of the SDP program that pertains to quantum marginals. In particular, conducting trace analysis on SDP matrices that correspond to using the game matrix as off-diagonal elements leads us to the construction of the desired marginal biases. It is also critical to note that a dual statement allows us to recover the column biases :

We now move on to defining the notion of a solution algebra.
Definition 13 (Solution Algebra) A solution algebra consists of self-adjoint (Hermitian) operators that satisfy the following predicates:

The definition above merely enforces the property that our unknown marginal operators be Hermitian (14) and that they respect the optimal marginal biases (or payoffs) (15) we saw in (11), so that they correspond to being constructed from an optimal vector strategy. These unknown operators will be mapped to operators that are the marginal strategy corresponding to the optimal quantum strategy. This is at the heart of the main theorem we will now state: Theorem 14 (Slofstra, 2010) Given a XOR game G (with no zero rows or columns) and a solution algebra , a collection of Linear Operators and density matrix are the marginal of an optimal strategy iff the map induces a density-matrix representation of and commutes with . Put simply, the theorem states that our unknown self-adjoint operators map to an optimal marginal strategy iff the density matrix (traced from the joint Hilbert-Space) commutes with all the mapped operators (). The result we desire on the lower bound for the number of entangled bits, given a mapping from these indeterminate operators to the marginal of an optimal strategy, comes from a corollary to (14).
Corollary 15 Given a XOR game G (with no zero rows or columns) and a solution algebra with minimum dimension among non-zero representations, the strategy for minimum entanglement uses entangled bits. The proof for this corollary follows from the eigenspace decomposition of the joint Hilbert Space in terms of , which is preserved by the action of . As a result, each eigenspace decomposes into a finite sum of irreducible representations of . The minimum entanglement is realized when there is exactly one invariant subspace (with one irreducible representation). The entanglement used by such a representation is .

Proof of Theorem 20

The rest of the section is dedicated to sketching a brief (but formal) proof for Theorem (14), and then using a simple fact about the representations of a Clifford Algebra to show how Slofstra’s result subsumes Tsirelson’s bound. For this section, refers to an arbitrary state in (the joint Hilbert space). We can write over some basis , where is a linear map. Then, the partial trace of over is given by . Let denote the algebra generated by and . Here, the generating elements are the observables of an optimal quantum strategy. To arrive at a proof for the theorem, we will rely on 2 additional lemmas which we will not prove but state.
Lemma 16 Given Hermitian operators , ,

This allows us to conclude that,

Lemma 17 The optimal strategy in question is non-degenerate iff

As a special case:

Forward direction : We use the first lemma to prove commutativity of with all , and we use the second lemma to show that the closure of is . We first show the forward direction: Suppose we are given an optimal quantum strategy () for a game . Then, we fix our optimal vector strategy as:

We can now use Equations (11) and (13) to establish our optimal marginal biases to write a relationship between them and , and apply Lemma (16) to show commutativity and Lemma (17) to show that = cyclic(). Using (13) with (20) and (21), we have:

We can now use (17) with on (22) to see that commutes with every . Additionally, as the terms in (22) constitute linear combinations of and , we can compute the closure of their actions on and , which will be equivalent. Therefore, = , which follows from the special case of (19). For the dual case, we substitute (20) and (21) into (12):

On taking the norm of the above on both sides and using a little algebra, we finally obtain the fact that satisfy predicate (15) making them the representations of : This shows that the map from computes a density matrix representation of , where commutes with all .
Backward Direction : The proof for the backward direction is much less involved: If we knew that constituted the cyclic representation of with commutativity (with ), then we can use Lemma (19) to conclude that the image of on would form a subspace of . We define: allowing us to recover our original marginal biases that satisfy (23) and therefore correspond to the optimal strategy. This shows us that , would constitute an optimal quantum strategy. Having proved this theorem, we now obtain Corollary 15, which is the main desired result. To see how it subsumes Tsirelson’s result as a special case, we use a simple fact from Representation Theory:
Lemma 18 For a Clifford Algebra generated by , there exist one or two irreducible representations of dimension Plugging Lemma 18 into Corollary 15, we simply recover the fact that the number of entangled bits of a solution algebra that is Clifford is . However, note that being Clifford means an extra constraint: , The constraints on the Solution Algebra (14), (15) given by Slofstra do \textit{not} necessarily mean that the solution is Clifford. In fact, when an optimal quantum strategy with minimal entanglement is Clifford, , are constructed from a unique set of , . To end, we write down a lemma that shows there exist XOR games where the optimal strategy is not unique and for minimal entanglement, a solution generated by a Non-Clifford algebra must be used:

Lemma (Existence of XOR games with Non-Clifford optimal strategies)

There exist a family of XOR games that correspond to generalizations of the CHSH games (), such that, the optimal strategy of minimal entanglement is Non-Clifford.

References

[1] David Avis, Sonoko Moriyama, and Masaki Owari. From bell inequalities to tsirelson’s theorem. IEICE Transactions, 92-A(5):1254–1267, 2009.

[2] Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. Theoretical Computer Science, 134(2):545 – 557, 1994.

[3] T. Ito, H. Kobayashi, and K. Matsumoto. Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies. ArXiv e-prints, October 2008.

[4] J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick. Entangled games are hard to approximate. ArXiv e-prints, April 2007.

[5] Julia Kempe, Oded Regev, and Ben Toner. Unique games with entangled provers are easy. SIAM Journal on Computing, 39(7):3207– 3229, 2010.

[6] S. Khanna, M. Sudan, L. Trevisan, and D. Williamson. The approximability of constraint satisfaction problems. SIAM Journal on Computing, 30(6):1863–1920, 2001.

[7] Anand Natarajan and Thomas Vidick. Two-player entangled games are NP-hard. arXiv e-prints, page arXiv:1710.03062, October 2017.

[8] Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. arXiv e-prints, page arXiv:1801.03821, January 2018.

[9] William Slofstra. Lower bounds on the entanglement needed to play xor non-local games. CoRR, abs/1007.2248, 2010.

[10] B.S. Tsirelson. Quantum analogues of the bell inequalities. the case of two spatially separated domains. Journal of Soviet Mathematics, 36(4):557–570, 1987.

[11] Thomas Vidick. Three-player entangled XOR games are NP-hard to approximate. arXiv e-prints, page arXiv:1302.1242, February 2013.

[12] Thomas Vidick. Cs286.2 lecture 15: Tsirelson’s characterization of xor games. Online, December 2014. Lecture Notes.

[13] Thomas Vidick. Cs286.2 lecture 17: Np-hardness of computing . Online, December 2014. Lecture Notes.