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.


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 { [n]=\{1,\ldots,n\}}.

Definition (Label cover)

A label cover instance { I=(S,T,\Sigma,\Pi)} consists of variable sets { S=\{s_i\}_{i\in[n]},T=\{t_j\}_{j\in[n]}}, alphabet set { \Sigma}, and a collection { \Pi} of constraints of the form { t_j=f_{i,j}(s_i)}. Given an assignment (or coloring) { c : S\cup T \rightarrow \Sigma} we define its value to be { \omega(c)=\mathbb P_{f_{ij}\sim\Pi}\big(c(t_j)=f_{ij}(c(s_i))\big)}. Define the value of { I} to be the maximum over all possible assignments, i.e. { \omega(I) = \max_{c} \omega(c)}. Many familiar computational problems can be formulated as a label cover, such as { \textsc{3SAT}}, { \textsc{3Lin}}, and { \textsc{MaxCut}}.
Label cover graph

Definition (2-prover 1-round game)

Let { I = (S,T,\Sigma,\Pi)} be a label cover instance. We can then associate the following two-prover one-round game { G(I)} with { I}. Let { P_1,P_2} be two provers who cannot communicate, and let { V} be the verifier. Given the label cover instance { I}, the verifier uniformly samples a constraint { f_{i,j} \in \Pi} and sends { s_i} to { P_1} and { t_j} to { P_2}. The provers then reply with { a \in \Sigma} and { b\in\Sigma} respectively to { V}. Finally, { V} outputs { 1} if and only if { b = f_{i,j}(a)}.
The game view of label cover
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 { I} with probability { \omega(I)}. 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 { |{v}\rangle \in\mathbb C^d} and its conjugate-transpose (a row vector) as { \langle{v}| } . More generally the conjugate-transpose (Hermitian conjugate) of a matrix { A} is written { A^\dag}. Then { \langle{v}| w\rangle} is the inner product of two vectors (a scalar) and { |{v}\rangle \langle{w}| } the outer product (a rank-1 matrix). A matrix { A} is said to be Hermitian if { A^\dag=A}. A matrix { A} is positive semidefinite , written { A\succeq 0}, if { A=B^\dag B} for some matrix { B}. We write the identity matrix as { {\mathbb{I}}}, denote by { Herm(\mathbb{C}^d)} the set of { d}-by-{ d} Hermitian matrices.

Observables, states, and entanglement

In a quantum theory the observables are Hermitian operators { A\in Herm(\mathbb C^d)} on a vector space { \mathbb C^d}. It then makes sense to say that a state is a functional { \varphi} 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 { \varphi(A)=\langle A,\rho\rangle} for some { d}-by-{ d} matrix { \rho}. We call { \rho} the density matrix and require moreover that { \rho} is positive semidefinite and has trace { 1}. Every density matrix is a convex combination of rank-one projections { |\psi\rangle\langle\psi|} known as pure states. The unit vectors { |\psi\rangle\in\mathbb C^d} are also themselves known as pure states. If the state of one particle is described by a vector in { \mathbb C^d} (referring here to pure states), then two particles are described by a vector in the tensor product { \mathbb C^d\otimes\mathbb C^d}. The two particles are entangled if their state is not in the form of a pure tensor { |\phi\rangle\otimes|\psi\rangle}. We also write product states as { |\phi\rangle|\psi\rangle}, 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 { \mathbb C^d} (where the quantum states live) is a list of projection matrices { A_1,\ldots,A_k} on { \mathbb C^d} such that { A_iA_j=0} for { i\neq j} and { \sum_i A_i={\mathbb{I}}}. The PVM describes a measurement which, on state { |\psi\rangle\in\mathbb C^d} outputs measurement outcome { i} with probability { \langle\psi| A_i|\psi\rangle}. The quantum state after obtaining outcome { i} is { \frac1{\|A_i|\psi\rangle\|}A_i|\psi\rangle}. When the projections are rank-one projections { A_i= |{\beta_i}\rangle \langle{\beta_i}| } we say that we measure in the basis { \{ |{\beta_i}\rangle \}_i}. In this case the probability of outcome { i} in state { |\psi\rangle} is { |\langle\beta_i |{\psi}\rangle |^2}, and the post-measurement state is simply { |{\beta_i}\rangle} . Applying the measurement { (A_i)_i} on the left half of a two-particle state { |{\Psi}\rangle \in\mathbb C^d\otimes\mathbb C^d} means applying the PVM { (A_i\otimes {\mathbb{I}})_{i}} 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 { \mathbb C^d}, and Alices particle may be entangled with Bob’s. The global state is { |{\phi}\rangle _{AB}\in\mathbb C^d\otimes\mathbb C^d}. 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 { n} PVM’s { A^s} where { s\in S} is a question, and each PVM is a list { A^s_{a=1},\ldots,A^s_k}. By definition 1, given questions { s,t} the probability that Alice outputs { a} and Bob outputs { b} is

\displaystyle  P(a,b|s,t)=\|({\mathbb{I}}\otimes B^t_b)(A^s_a\otimes {\mathbb{I}}) |{\phi}\rangle _{AB}\|^2= \langle{\phi}| A^s_a\otimes B^t_b|\phi\rangle, \ \ \ \ \ (1)

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

Quantum strategies beat classical ones

For any 2P-1R game { G}, let { \omega(G)} be the maximum probability — over the players’ classical strategies — that the verifier accepts and { \omega^*(G)} 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 { \omega^*(G)=\cos^2(\frac{\pi}{8}) = \frac{1}{2}+\frac{\sqrt{2}}{4}\approx 0.85} which is better than the classical value { \omega(G)\leq \frac{3}{4}}. 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 { (s, t)\in\{0, 1, \ldots, n-1\}^2} are asked according to some distribution { \Pi} (e.g. uniform).
  2. Answers { a, b\in\{0, 1\}} are provided by players (call them Alice and Bob).
  3. The verifier computes a predicate { V(a, b|s, t) = f_{s, t}(a\oplus b)} used to decide acceptance/rejection.

Definition (CHSH Game)

An XOR game with { n=2} where { s, t\in\{0, 1\}} are independent random bits and { V(a, b | s, t)=1 \Longleftrightarrow a\oplus b = s\wedge t}. To win the CHSH game, Alice and Bob need to output bits { a} (from Alice) and { b} (from Bob) that disagree if { s=t=1} and agree otherwise. If Alice and Bob are classical then they can do no better than by always outputting { 0}, say, in which case they win in the three out of four cases when one of the questions is { 0}. Equivalently, { \omega(G)=\frac34} where { G} is the CHSH game. This is the content of Bell’s inequality :

Lemma (Bell’s Inequality)

For any two functions { g, h: \{0, 1\}\rightarrow\{0, 1\}}, we have { {\mathop{\mathbb{P}}}_{x, y\in\{0, 1\}}\left[g(x)\oplus h(y) = x\wedge y\right] \leq \frac{3}{4} } where { x} and { y} are independent uniformly random bits.
The probability of any event is a multiple of { 1/4} so it suffices to show that { {\mathop{\mathbb{P}}}_{x, y\in\{0, 1\}}\left[g(x)\oplus h(y) = x\wedge y\right]\neq1}. So assume for contradiction that { g(x)\oplus h(y) = x\wedge y} for all pairs { x,y}. Then we have that { g(0)\oplus h(0) = 0} and { g(0)\oplus h(1) = 0} which implies that { h(0)=h(1)}. But then { 0=g(1)\oplus h(0) =g(1)\oplus h(1) = 1} 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 { \mathbb C^2\otimes\mathbb C^2}. The two qubits together are in the state { |{\phi}\rangle = \frac{1}{\sqrt{2}}\left( |{0}\rangle _A |{0}\rangle _B + |{1}\rangle _A |{1}\rangle _B\right), } forming what is known as an EPR (Einstein-Podolsky-Rosen) pair. Now for { \theta\in[-\pi, \pi]} define { |{\beta_0(\theta)}\rangle = \cos\theta |{0}\rangle + \sin\theta |{1}\rangle } and { |{\beta_1(\theta)}\rangle = -\sin\theta |{0}\rangle + \cos\theta |{1}\rangle } . Now we describe a (quantum) strategy with winning probability { \cos^2(\frac{\pi}{8})}. 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 { s=0}, Alice measures in basis { \{ |{\beta_0(0)}\rangle , |{\beta_1(0)}\rangle \} = \{ |{0}\rangle , |{1}\rangle \}}. If { s=1}, Alice measures in { \{ |{\beta_0(\frac{\pi}{4})}\rangle , |{\beta_1(\frac{\pi}{4})}\rangle \}}. Alice answers bit { a = 0} if outcome is { \beta_0(\cdot)} and answers { a = 1} otherwise.
  • If { t=0}, Bob measures in basis { \{ |{\beta_0(\frac{\pi}{8})}\rangle , |{\beta_1(\frac{\pi}{8})}\rangle\}}. If { t=1}, Bob measures in { \{ |{\beta_0(-\frac{\pi}{8})}\rangle , |{\beta_1(-\frac{\pi}{8})}\rangle \}}.
  • Each player responds with their respective measurement outcome.
Lemma 2 Alice and Bob win the CHSH game with probability { \cos^2(\frac{\pi}{8})}.
We will show that for each pair of questions { s,t} the pair of answers { a,b} is correct with probability { \cos^2(\pi/8)}. We can split the pairs of questions into the two cases { s\wedge t=0} and { s\wedge t=1}:
  • ({ s\wedge t=0}) The three cases { (s,t)=(0,0),(0,1),(1,0)} 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 { \pm\pi/8}. Of the three above cases we consider the one where { s,t=0} and check that indeed the two measurement outcomes agree with probability { \cos^2(\pi/8)}: When Alice measures her qubit and obtains some bit { a}, the shared pair { |{\beta}\rangle} collapses to { |{a}\rangle _A |{a}\rangle _B}. Indeed, since the question was { s=0}, Alice measures her qubit in the basis { \{|0\rangle,|1\rangle\}}. This means that Alice applies the measurement { \{|0\rangle\langle 0|\otimes {\mathbb{I}},|1\rangle\langle 1|\otimes {\mathbb{I}}\}} on the global state. The post-measurement state is the normalization of { ( |{a}\rangle \langle{a}| \otimes {\mathbb{I}}) |{\phi}\rangle _{AB}=\frac{1}{\sqrt2} |{a}\rangle \overbrace{\langle a |{0}\rangle }^{\delta_{a,0}}\otimes | 0\rangle + |{a}\rangle \overbrace{\langle a |{1}\rangle }^{\delta_{a,1}}\otimes |{1}\rangle =\frac {1}{\sqrt2} |{a}\rangle _A |{a}\rangle _B } because { \langle a |{a'}\rangle} can be viewed as a Kronecker delta of { a} and { a'}. In particular, Bob is now in the pure state { |{a}\rangle} . Because Bob received question { t=0} he measures in the basis { \{ |{\beta_b(\pi/8)}\rangle \}_b} Therefore his probability of correctly outputting { b=a} is { {\mathop{\mathbb{P}}}[\text{Bob gets outcome }a] = |\langle\beta_a(\tfrac{\pi}{8}) |{a}\rangle |^2 = \cos^2\left(\frac{\pi}{8}\right) }
  • ({ s\wedge t=1}) Now consider the case { s=1,t=1} where Alice and Bob are supposed to give different answers. Alice measures in basis consisting of { |{\beta_0(\pi/4)}\rangle =\frac{|0\rangle+|1\rangle}{\sqrt2}} and { |{\beta_1(\pi/4)}\rangle =\frac{-|0\rangle+|1\rangle}{\sqrt2}}. If Alice gets outcome { a} then the post-measurement global state is { |{\beta_a(\frac\pi4)}\rangle |{\beta_a(\frac\pi4)}\rangle} . Therefore when Bob applies the measurement in basis { \{ |{\beta_a(-\frac\pi8)}\rangle \}_a} he mistakenly outputs { a} only with probability { |\langle\beta_a(\frac\pi4) |{\beta_a(-\frac\pi8)}\rangle |^2=\sin^2(\frac\pi8)=1-\cos^2(\frac\pi8)}.
Lemma 2 implies a lower bound on the value of the CHSH game.


{ \omega^*(G)\ge\cos^2(\frac\pi8)}
It turns out that this lower bound is sharp, that is, the strategy just described is optimal.


The value of the CHSH game using a quantum strategy is at most { \frac{1}{2} + \frac{\sqrt{2}}{4} = \cos^2\frac{\pi}{8}\approx 0.85}. Proof. We can describe the quantum strategy of Alice and Bob in an XOR game by (i) a shared quantum state { |{\phi}\rangle _{AB}\in\mathbb{C}^d\otimes\mathbb{C}^d} (note that for the CHSH game, { d=2}); (ii) measurements { \{A^0_s, A^1_s\}} for every question { s} sent to Alice; (iii) measurements { \{B^0_t, B^1_t\}} for every question { t} sent to Bob. The probability of answering { (a, b)} given questions { (s, t)} is { \langle{\phi}| A^a_s\otimes B^b_t |{\phi}\rangle} . Now let us write { A_s=A^0_s - A^1_s} and { B_t=B^0_t - B^1_t} so that for any { a, b\in\{0, 1\}}, we can write { A_s^a = \frac{{\mathbb{I}} + (-1)^aA_s}{2}, B_t^b = \frac{{\mathbb{I}} + (-1)^bB_t}{2} } Note that since the possible outcomes here are finite, { A_s, B_t} are Hermitian and we may assume have bounded norm of 1. Furthermore, we assume that { A_s, B_t} are observables so that { A_s^2 = B_t^2 = {\mathbb{I}}} . Now denoting { f_{s, t}(a\oplus b)} as the XOR predicate to be computed, we can write the quantum game value as \omega^*(G) = \sup_{ |{\phi}\rangle , \{A_s^a\}, \{B_t^b\}} {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\sum_{a, b}f_{s, t}(a\oplus b) \langle{\phi}| A^a_s\otimes B^b_t |{\phi}\rangle  \\ = \sup_{ |{\phi}\rangle , \{A_s\}, \{B_t\}} {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\sum_{a, b}f_{s, t}(a\oplus b) \langle{\phi}| \frac{{\mathbb{I}} + (-1)^aA_s}{2}\otimes  \frac{{\mathbb{I}} + (-1)^bB_t}{2} |{\phi}\rangle  \\ = {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\sum_{a, b}\frac{f_{s, t}(a\oplus b)}{4} + \sup_{ |{\phi}\rangle , \{A_s\}, \{B_t\}} {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\sum_{a, b}f_{s, t}(a\oplus b) \langle{\phi}| \frac{{\mathbb{I}} + (-1)^aA_s}{2}\otimes  \frac{{\mathbb{I}} + (-1)^bB_t}{2} |{\phi}\rangle  \\ = {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\sum_{a, b}\frac{f_{s, t}(a\oplus b)}{4} + \sup_{ |{\phi}\rangle , \{A_s\}, \{B_t\}} {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\sum_{a, b}\frac{f_{s, t}(a\oplus b)(-1)^{ab}}{4} \langle{\phi}| A_s\otimes B_t |{\phi}\rangle  \\ = {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\sum_{a, b}\frac{f_{s, t}(a\oplus b)}{4} + \sup_{ |{\phi}\rangle , \{A_s\}, \{B_t\}} {\mathop{\mathbb{E}}}_{(s, t)\sim\Pi}\frac{f_{s, t}(0) - f_{s,t}(1)}{2} \langle{\phi}| A_s\otimes B_t |{\phi}\rangle  \\ where the summation { \sum_{a, b\in\{0, 1\}}\left(\cdot\right)} 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 { f_{s, t}(0) - f_{s,t}(1) = (-1)^{st}} simplifying the second term to { \frac{1}{8}( \langle{\phi}| A_0\otimes B_0 |{\phi}\rangle + \langle{\phi}| A_1\otimes B_0 |{\phi}\rangle + \langle{\phi}| A_0\otimes B_1 |{\phi}\rangle - \langle{\phi}| A_1\otimes B_1 |{\phi}\rangle ). } Next, we invoke Tsirelson’s Theorem (See Theorem 3) to bound this second term as = \sup_{{\textbf{x}}_s, {\textbf{y}}_t}\frac{1}{8}({\textbf{x}}_0\cdot {\textbf{y}}_0 + {\textbf{x}}_0\cdot {\textbf{y}}_1 + {\textbf{x}}_1\cdot {\textbf{y}}_0 - {\textbf{x}}_1\cdot {\textbf{y}}_1) \\ \leq \sup_{{\textbf{x}}_s, {\textbf{y}}_t}\frac{1}{8}(\|{\textbf{x}}_0\|\|{\textbf{y}}_0 + {\textbf{y}}_1\| + \|{\textbf{x}}_1\|\|{\textbf{y}}_0 - {\textbf{y}}_1\|) \\ \leq \sup_{{\textbf{x}}_s, {\textbf{y}}_t}\frac{\sqrt{2}}{8}\sqrt{2\|{\textbf{y}}_0\|^2 + 2\|{\textbf{y}}_1\|^2} \leq \frac{\sqrt{2}}{4} where we have used Cauchy-Schwartz and the concavity of the { \sqrt{\cdot}} function. This completes our proof showing the exact characterization of the value ({ =\cos^2(\frac{\pi}{8})=\frac{1}{2}+\frac{\sqrt{2}}{4}}) 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 { n\times n} matrix { C = (C_{s, t})}, the following are equivalent:
  1. There exist { d\in\mathbb{N}, |{\phi}\rangle \in\mathbb{C}^{d}\otimes\mathbb{C}^{d}, A_s, B_t\in\text{Herm}(\mathbb{C}^d), A_s^2 = B_t^2 = I} such that for any { s, t\in[n]} { C_{s, t} = \langle{\phi}| A_s\otimes B_t |{\phi}\rangle} . Further this would imply that { d\leq 2^{\lceil\frac{n+2}{2}\rceil}};
  2. There exist real unit vectors { {	{\textbf{x}}}_s, {	{\textbf{y}}}_t\in{\mathbb{R}}^{n+2}} for { s, t\in [n]} such that { C_{s, t} = {	{\textbf{x}}}_s\cdot {	{\textbf{y}}}_t};

Entangled unique games are easy

The CHSH game provides the first example that the entangled value { \omega^*(G)} of a nonlocal game can exceed the classical value { \omega(G)}. XOR-games like the CHSH game are the special case corresponding to alphabet size { k=2} 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 { b=\pi_{ij}(a)} where { \pi_{ij}} is a permutation of the alphabet { \Sigma} for each edge { i\sim j}. The famous unique games conjecture (UGC) by Khot says that { \omega(G)} 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 { \omega^*(G)} 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 { G} as its input and outputs { \hat\omega(G)} such that { 1-6(1-\hat\omega(G))\le\omega^*(G)\le\hat\omega(G) } Put differently, if { \omega^*(G)=1-\varepsilon^*} and { \hat\omega(G)=1-\hat\varepsilon}, then { \varepsilon^*\in[\hat\varepsilon,6\hat\varepsilon] }
The algorithm of theorem 4 proceeds by relaxing the set of quantum strategies to a larger convex set { \mathcal S} of pseudo-strategies and maximizing over { \mathcal S} 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 { \mathcal S} 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 { \mathcal S} to be a class of conditional probability distributions { \tilde{P}(a,b|s,t)} 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 { \tilde{P}(a,b|s,t)} by allowing each of { s} and { t} to be either a question for Alice or for Bob. That is, we extend the domain of definition for { \tilde{P}(a,b|s,t)} from { \Sigma^2\times S\times T} to { \Sigma^2\times (S\cup T)^2} where { S} and { T} are the question sets. So each question { s} and { t} and answer { a} and { b} can be either for Alice or Bob — we indicate this by changing notation from { (s,t)\in S\times T} to { q,q'\in S\cup T} and for the answers replacing { a,b} by { c,c'}.
Definition 5 (Block-matrix form) Given a function { \tilde{P}=\tilde{P}(\cdot\cdot|\cdot\cdot)} defined on { (S\cup T)^2\times \Sigma^2} with { |S|=|T|=n} and { |\Sigma|=k}, define a { 2nk}-by-{ 2nk} matrix { M^{\tilde{P}}} whose rows are indexed by pairs { (q,c)\in(S\cup T)\times\Sigma} and columns by pairs { (q',c')\in (S\cup T)\times\Sigma}, and whose entries are { M^{\tilde{P}}_{(q,c),(q',c')}=\tilde{P}(c,c'|q,q') } In other words { M^{\tilde{P}}} consists of { k}-by-{ k} blocks where the block { M^{\tilde{P}}_{q,q'}} at position { q,q'} contains the entries { \tilde{P}(\cdot\cdot|q,q')}.
Definition 5 is simply a convenient change of notation and we identify { \tilde{P}} with { M^{\tilde{P}}}, using either notation depending on the context.
Definition 6 (Pseudo-strategies) Let { S} and { T} be the question sets for Alice and Bob, respectively. We say that { \tilde{P}=\tilde{P}(\cdot\cdot|\cdot\cdot):\Sigma^2\times (S\cup T)^2\rightarrow[0,1]} (or its matrix form { M^{\tilde{P}}}) is a pseudo-strategy if:
  1. { M^{\tilde{P}}} is positive semidefinite.
  2. For any pair of questions { q,q'\in S\cup T}, { \sum_{c,c'=1}^k \tilde{P}(c,c'|q,q')=1}.
  3. The blocks { M^{\tilde{P}}_{q,q'}} on the diagonal are themselves diagonal { k}-by-{ k} matrices.
Define the winning probability or value of a pseudo-strategy as: { \omega^{\tilde{P}}(G)=\mathbb E_{(s,t)\sim \Pi} \sum_{a,b} \tilde{P}(a,b|s,t)V(a,b|s,t) } The algorithm outputs the maximum winning probability: { \hat\omega(G)=\max_{\tilde{P}\in\mathcal S}\omega^{\tilde{P}}(G) } over pseudo-strategies { \tilde{P}\in \mathcal S}. This maximum is efficiently computable using standard semidefinite programming algorithms. As we will see, actual quantum strategies are in { \mathcal S} which immediately implies { \hat\omega(G)\ge\omega^*(G)}. It then remains to show that the optimal pseudo-strategy can be approximated by an actual entangled strategy, thus bounding the gap from { \omega^*(G)} to { \hat\omega(G)}.

Quantum strategies are in { \mathcal S}

Let us establish that { \mathcal S} 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 { a} and { b} given questions { s} and { t} is of the form { \langle\phi|A^s_a\otimes B^t_b |\phi\rangle=\langle\phi|(A^s_a\otimes {\mathbb{I}})({\mathbb{I}}\otimes B^t_b )|\phi\rangle } for some PVM’s { A^s} and { B^t} and some { |\phi\rangle\in\mathbb C^d\otimes\mathbb C^d}. 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 { A^s_a\otimes {\mathbb{I}}|\phi\rangle}, { (s,a)\in S\times \Sigma} side by side, and then append the vectors { I\otimes B^t_b|\phi\rangle}, resulting in a { d^2}-by-{ 2nk} matrix { R}. We then define { {P}(\cdot\cdot|\cdot\cdot):\Sigma^2\times(S\cup T)^2\rightarrow[0,1]} through its matrix form (see the comment below definition 5):

\displaystyle  M^{P}:=R^\dag R=\begin{pmatrix} (\langle\phi|A^s_a A^{s'}_{a'}\otimes {\mathbb{I}} |\phi\rangle)_{(s,a),(s',a')} (\langle\phi|A^s_a\otimes B^t_b |\phi\rangle)_{(s,a),(t,b)} \\\\ (\langle\phi|B^t_b\otimes A^s_a |\phi\rangle)_{(t,b),(s,a)} (\langle\phi|{\mathbb{I}}\otimes B^t_bB^{t'}_{b'} |\phi\rangle)_{(t,b),(t',b')} \end{pmatrix} \ \ \ \ \ (2)

Lemma 7 { M^{P}} defined in 2 is a pseudo-strategy, that is, { M^{P}\in\mathcal S}.
We verify the conditions in definition 6. Condition 1 ({ M^{P}\succeq0}) holds because it is of the form { R^\dag R}. Condition 2 (Each block { M^{P}_{q,q'}} sums to { 1}) holds because PVM’s sum to the identity. Condition 3 (Diagonal blocks { \tilde M=M^{P}_{qq}} are diagonal) holds because the projections in the PVM { A^q} are mutually orthogonal, hence { \langle{\phi}| A^q_cA^q_{c'} |{\phi}\rangle =0} if { c\neq c'}.
Lemma 7 means { \hat\omega(G)=\max_{{P}\in \mathcal S}\omega^{P}(G)} is an (efficiently computable) upper bound for { \omega^*(G)}:


{ \hat\omega\ge \omega^*(G)}.
To finish the proof of theorem 4 we need to show that any pseudo-strategy { \tilde{P}} can be rounded to an actual quantum strategy with answer probabilities { {P}} such that

\displaystyle  1-\omega^{P}\le 6(1-\omega^{\tilde P}) \ \ \ \ \ (3)

Applying this rounding to the optimal pseudo-strategy implies that { 1-\omega^*\le 6(1-\hat\omega) } or { \omega^*\ge 1-6(1-\hat\omega)}, which will finish the proof of theorem 4.
[Proof of theorem 4] Let { \tilde{P}\in\mathcal S} be a pseudo-strategy. We construct a quantum strategy { {P}} approximating { \tilde{P}}. Since { M^{\tilde{P}}} is positive semidefinite we can write { \tilde M=R^\dag R } for some matrix { R\in \mathbb C^{r\times 2nk}} and { r\leq 2nk}. Now let us define { 2nk} vectors { |\tilde u^s_a\rangle} and { |\tilde v^t_b\rangle} in { \mathbb C^{r}}, and let { |{u^s_a}\rangle} and { |{v^t_b}\rangle} be the same vectors normalized. The strategy is constructed as follows. Alice and Bob share the maximally entangled state { |\phi\rangle=\frac1{\sqrt r}\sum_{i=1}^r|i\rangle|i\rangle\in\mathbb C^r\otimes\mathbb C^r } Before deciding on Alice and Bob’s PVM’s { A^s} and { B^t} let us see what this choice of shared state means for the conditional distribution on answers (see equation (1)).

\langle\phi| A^s_a\otimes B^t_b|\phi\rangle =\frac1r\sum_{i,j=1}^r\langle i | A^s_a| j\rangle\langle i | B^t_b| j\rangle =\frac1r A^s_a\cdot B^t_b=\frac1r\langle A^s_a,\overline{B^t_b}\rangle, (*)

where the bar represents entrywise complex conjugation, { \cdot} is the entrywise dot product of matrices, and { \langle\:,\rangle} the entrywise complex inner product (Hilbert-Schmidt inner product). We now choose the measurements. Given question { s}, Alice measures in the PVM { A^s=(A^s_a)_{a=0}^k} with { A^s_a= |{u^s_a}\rangle \langle{u^s_a}| \text{ for }a=1,\ldots,k\text{, and }A^s_0={\mathbb{I}}-\sum_{i=1}^k |{u^s_a}\rangle \langle{u^s_a}| } Similarly, Bob on question { t} applies the PVM { B^t} with { B^t_b= |{v^t_b}\rangle \langle{v^t_b}| \text{ for }b=1,\ldots,k\text{, and }B^t_0={\mathbb{I}}-\sum_{i=1}^k |{v^t_b}\rangle \langle{v^t_b}| } The condition 3 in definition 6 ensures that for any question { s}, the vectors { |{u^s_1}\rangle ,\ldots, |{u^s_1}\rangle} are orthogonal so that this is a valid PVM. The measurement outcome “0” is interpreted as “fail”, and upon getting this outcome the player attempts the measurement again on their share of a fresh copy of { |\phi\rangle_{AB}}. 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 { \langle\phi|A^s_a\otimes B^t_b|\phi\rangle=\frac1r\Big\langle |{u^s_a}\rangle \langle{ u^s_a}| \:,\: |{{v^t_b}\rangle } \langle{ {v^t_b}| }\Big\rangle=\frac1r|\langle {u^s_a}|v^t_b\rangle|^2=\frac1{r|\tilde u^s_a|^2|\tilde v^t_b|^2}\Big(M^{\tilde{P}}_{(s,a),(t,b)}\Big)^2, } We wish to relate the LHS to { M^{\tilde{P}}_{(s,a),(t,b)}}, so to handle the factor { \frac1r} each prover performs repeated measurements, each time on a fresh copy of { |\phi\rangle_{AB}}, until getting an outcome { \neq0}. Moreover, to handle the factor { \frac1{|u^s_a|^2|v^t_b|^2}}, each prover consults public randomness and accepts the answer { a\in[k]} with probability { |u^a_s|^2} and { |v^b_t|^2} 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 { M^{\tilde{P}}_{(s,a),(t,b)}\le 1/k} for all { s,a,t,b}, and one can ensure that the conditional probabilities { {P}} of the final answers satisfy

\displaystyle 1/k-P(a,b|s,t)\le 3\big(1/k-k(M^{\tilde P}_{(s,a),(t,b)})^2\big),\ \ \ \ \ (4) At this stage it is important that we are dealing with a unique game . Indeed, by (4) we have for every { s} and { t}, 1-\sum_{a=1}^k P(a,\pi_{st}(a)|s,t)=\sum_a \Big(\frac{1}{k}-P(a,\pi_{st}(a)|s,t) \Big) \\ \leq 3\sum_{b=\pi_{st}(a)} \Big(\frac{1}{k}-k(M^{\tilde{P}}_{(s,a),(t,b)})^2 \Big) \\ \leq 6\sum_{b=\pi_{st}(a)}\big(\frac{1}{k}-M^{\tilde{P}}_{(s,a),(t,b)}\big)=6\Big(1-\sum_{b=\pi_{st}(a)} M^{\tilde{P}}_{(s,a),(t,b)}\Big) where the last inequality follows from concavity. Taking the expectation over { s} and { t} 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 { \omega^*} 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 { \omega^*} 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 { \phi} of a { k}-CSP (constraint satisfaction problem, where { k} is the number of literals), we can define a clause-vs-variable game { G_\phi} (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.
Two variations of a 2-player clause-vs-variable game; new features are in red and shared entanglement is denoted in blue. In the standard game { G_\phi}, given { k}-CSP { \phi=(C_1,\ldots,C_m)} on { n} variables { x_i}, (1) the referee R randomly sends a clause { C_j} to Alice A and a literal index { t\in[k]} to Bob B, (2) A replies with an assignment { (a_1,\ldots,a_k)} and B replies with assignment { b}, (3) R accepts iff { (a_1,\ldots,a_k)} satisfies { C_j} and { a_t=b}. In variation (a), R sends an additional dummy index { l\in[k]}, so that B replies with an additional assignment { b'}, but he does not know which is the right variable. Equivalently, in (b) a third player Charlie C is introduced, but { G_\phi} is played with two randomly chosen players. Since only parties can be maximally entangled and the players do not know who is playing the game, they cannot coordinate perfectly.

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 {G} (emulating the CSP) and its oracularization {G'} (transformation to a 2P-1R game),

\displaystyle  \omega(G)\leq \omega(G')\leq 1-\frac{1-\omega(G)}{3}\,. \ \ \ \ \ (5)

Theorem 8 establishes the CSP variant of the classical PCP theorem: distinguishing between { \omega(\phi)=1} and { \omega(\phi)\leq 1/2} is NP-hard for some { k}-CSP. Here, { \omega(\phi)} denotes the maximum fraction of clauses that are simultaneously satisfiable. Theorem 9 relates the general game { G} obtained from the CSP to a two-player one-round game { G'}, in terms of the value (probability of winning) the game. The first inequality, equivalently saying { \omega(\phi)\leq \omega(G_\phi)}, is achieved since the players can answer the questions in the game { G_\phi} to satisfy the clauses in { \phi}. These theorems together imply that { \omega(G_\phi)} is NP-hard to approximate to within constant factors. Allowing the two players to share entanglement can increase the game value to { \omega^*(G_\phi)\geq \omega(G_\phi)}. 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 {c>0} such that for a CSP {\phi},

\displaystyle  \omega^*(G_\phi)\leq 1 - \frac{c(1-\omega(\phi))^2}{n^2}\,, \ \ \ \ \ (6)

where {n} is the number of variables. Combining Theorem 9 and Lemma 10, we have { \omega(\phi)\leq \omega^*(G_\phi)\leq 1 - \frac{c(1-\omega(\phi))^2}{n^2}\,. } Using Theorem 8, approximating { \omega^*(G_\phi)} 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]) {\phi} is satisfiable iff {\omega^*(G_\phi)=1}.

Proof of Proposition 11

The forward direction is straightforward: If { \phi} 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 { |{\psi}\rangle \in\mathbb{C}^d\otimes\mathbb{C}^d} and measurements { (A^j_{a_1,\ldots,a_k})_{a_1,\ldots,a_k}} for Alice and { (B^{t,l}_{b,b'})_{b,b'}} for Bob, where the questions { j\in[m]}, { t,l\in[k]} and the answers { a,b} 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 { \tilde{B}^t_b=\frac{1}{n}\sum_{l,b'} B^{t,l}_{b,b'}}. We can introduce a distribution on assignments to the { n} relevant variables,

\displaystyle  p(a_1,\ldots,a_n)=\lVert \mathbb{I} \otimes \tilde{B}^1_{a_1}\cdots\tilde{B}^n_{a_n} |\psi\rangle \rVert^2\,.  \ \ \ \ \ (7)

If we show that the distribution for assignments {a_{i_1},\ldots,a_{i_k}} on variables {x_{i_1},\ldots,x_{i_k}} in any clause {C_j} is

\displaystyle  p(a_{i_1},\ldots,a_{i_k})= \lVert A^j_{a_{i_1},\ldots,a_{i_k}} \otimes \mathbb{I} |\psi\rangle \rVert^2\,,  \ \ \ \ \ (8)

then, since the players win with certainty, {\phi} has a satisfying assignment. To transform Eq. 7 to Eq. 8, we need a relation between the {A} and {\tilde{B}} measurement operators and a way to commute the {\tilde{B}} operators. The success probability of the players’ strategy is expressed as { P=\frac{1}{m}\sum_{j\in[m]}\frac{1}{k}\sum_{i\in C_j} \sum_{(a_1,\ldots,a_k)\vdash C_j} \langle{\psi}| A^j_{a_1,\ldots,a_k}\otimes \tilde{B}^i_{a_i} |{\psi}\rangle \,, } where { i} is the index of one of the { k} variables on which { C_j} acts, and { (a_1,\ldots,a_k)\vdash C_j} indicates that the assignment satisfies the clause. By positivity and summation to identity of the measurement operators { A} and { \tilde{B}}, each term is at most 1; for our hypothesis { P=1}, each has to be 1. Hence, using orthogonality of the vectors { {\mathbb{I}}\otimes\tilde{B}^i_{a_i} |{\psi}\rangle} for different { a_i}, we have

\displaystyle  \sum_{\substack{(a_{i_1},\ldots,a_{i_k})\vdash C_j \\ a_i=b}} A^j_{a_{i_1},\ldots,a_{i_k}}\otimes \mathbb{I} |\psi\rangle = \mathbb{I} \otimes \tilde{B}^i_{a_i}|\psi\rangle\,,  \ \ \ \ \ (9)

for any { j\in[m]} and { i\in C_j}. We now demonstrate that two different { \tilde{B}^{t_1}_{b_1}}, { \tilde{B}^{t_2}_{b_2}} commute, so that Bob can match any satisfied clause/variable. {\mathbb{I}} \otimes \tilde{B}^{t_1}_{b_1} \tilde{B}^{t_2}_{b_2} |{\psi}\rangle =  {\mathbb{I}} \otimes (\frac{1}{n}\sum_{l_1,b_1'} B^{t_1,l_1}_{b_1,b_1'}) (\frac{1}{n}\sum_{l_2,b_2'} B^{t_2,l_2}_{b_2,b_2'}) |{\psi}\rangle \\ = {\mathbb{I}} \otimes (\frac{1}{n}\sum_{t_2,b_1'} B^{t_1,t_2}_{b_1,b_1'}) (\frac{1}{n}\sum_{t_1,b_2'} B^{t_2,t_1}_{b_2,b_2'}) |{\psi}\rangle \\ = {\mathbb{I}} \otimes \frac{1}{n^2}\sum_{t_1,t_2} B^{t_1,t_2}_{b_1,b_2} |{\psi}\rangle \\ = {\mathbb{I}} \otimes \frac{1}{n^2}\sum_{t_1,t_2} B^{t_2,t_1}_{b_2,b_1} |{\psi}\rangle \\ = {\mathbb{I}} \otimes \tilde{B}^{t_2}_{b_2} \tilde{B}^{t_1}_{b_1} |{\psi}\rangle In the second line, we used (9) to relate the measurements. The third line follows by the orthogonality of { B^{t_1,t_2}_{b_1,b_2}} for different { b_1,b_2}. For the fourth equation, we simply swap { t_1,t_2} since the questions are indistinguishable to Bob. Thus, we can see how the dummy variable comes into play. If we had assumed { P=1-\epsilon} and kept track of approximations, we would find

\displaystyle  \frac{1}{n^2}\sum_{t_1,b_1}\sum_{t_2,b_2}\lVert \mathbb{I} \otimes (\tilde{B}^{t_1}_{b_1} \tilde{B}^{t_2}_{b_2} - \tilde{B}^{t_2}_{b_2} \tilde{B}^{t_1}_{b_1}) |\psi\rangle \rVert^2 = O(\epsilon)\,.  \ \ \ \ \ (10)

This approximate commutativity results in the hardness of approximation holding only to within inverse poly{ (n)} factors. Now we are ready to transform Eq. 7 to Eq. 8 to conclude the proof. p(a_1,\ldots,a_n)=\lVert {\mathbb{I}} \otimes \tilde{B}^1_{a_1} \ldots \tilde{B}^n_{a_n} |{\psi}\rangle \rVert^2 \\ =\lVert {\mathbb{I}} \otimes \tilde{B}^{i_1}_{a_{i_1}} \ldots \tilde{B}^{i_k}_{a_{i_k}} |{\psi}\rangle \rVert^2 \\ = \lVert A^j_{a_{i_1},\ldots,a_{i_k}} \otimes {\mathbb{I}} |{\psi}\rangle \rVert^2 \\ =p(a_{i_1},\ldots,a_{i_k})\,. 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 { A^j_{a_{i_1,\ldots,i_k}}} for different { a_{i_1,\ldots,i_k}}.

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 ({ |{\psi}\rangle , \{A_{i}\}_{i \in S}, \{B_{j}\}_{j \in T}}). 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) { |T|} bits of entanglement less than the Clifford strategy. Slofstra further states that minimally entangled { \epsilon}-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


For the exact realm, the table below summarizes Slofstra and Tsirelson’s main results.
Person Strategy Bound(entangled bits)
Slofstra (Possibly) Non-Clifford { \log_{2}(N)}
Tsirelson Clifford { \left \lfloor{\frac{r}{2}}\right \rfloor}
Here, { r} is the largest integer such that { \binom{r + 1}{2} < |S| + |T|} and corresponds to the maximum-rank of an extremal point in the quantum correlation matrix corresponding to an optimal strategy. { N} is the minimum dimension of the representations of the Operators ({ \{B_{j}\}}).


In the approximate realm, the minimum entanglement dimension of the representation of the Operators from an { \epsilon}-Optimal Strategy is: min({ \mathcal{O}(\epsilon^{\frac{-1}{12}}), 2^{\left \lfloor{\frac{r}{2}}\right \rfloor}}). 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 { \leftrightarrow} 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 ({ |{\psi}\rangle , \{A_{i}\}_{i \in S}, \{B_{j}\}_{j \in T}}), a marginal constitutes { \{B_{j}\}_{j \in T}}, and the partial trace of { \psi} with respect to { H_{A}} ({ \rho_{B}}). It is also possible to dualize the definition for obtaining { \{A_{i}\}_{i \in S}} and { \rho_{A}}. 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 ({ |{\psi}\rangle , \{A_{i}\}_{i \in S}, \{B_{j}\}_{j \in T}}) is said to be degenerate if { \exists (P \in H_A)}, { (Q \in H_B)} such that: i) { P} commutes with all { A_i} and { (P \otimes {\mathbb{I}}) |{\psi}\rangle = |{\psi}\rangle} ii) { Q} commutes with all { B_j} and { ({\mathbb{I}} \otimes Q) |{\psi}\rangle = |{\psi}\rangle} 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 ({ d_{j}}) 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 {m \times n} XOR games G, {\exists \{c_{i} \geq 0 \hspace{1mm} | \hspace{1mm} i \in |S|\}}, such that, if {\{u_{i}\}_{i \in |S|}, \{v_{j}\}_{j \in |T|}} form an {\epsilon}-optimal vector strategy where {\epsilon \leq \frac{1}{4(m+n)}},

\displaystyle  \|\sum_{j\in|T|}G_{ij}v_{j} - c_{i}u_{i}\| \leq \sqrt{10}(m + n)^{\frac{1}{4}}\epsilon^{\frac{1}{4}}, \forall i  \ \ \ \ \ (11)

If { \epsilon = 0} and our strategy is perfectly optimal, we recover an exact estimation of the marginal biases:

\displaystyle  \sum_{j\in|T|}G_{ij}v_{j} = c_{i}u_{i}, \forall i  \ \ \ \ \ (12)

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 { d_{j} \geq 0}:

\displaystyle  \sum_{i\in[|S|]}G_{ij}u_{i} = d_{j}v_{j}, \forall j  \ \ \ \ \ (13)

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

\displaystyle  X_{j}^{2} = \mathbb{I}, \forall 1 \leq j \leq n  \ \ \ \ \ (14)

\displaystyle  (\sum_{j\in[|T|]}G_{ij}X_{j})^{2} = (c_{i})^{2}\cdot\mathbb{I}, \forall i  \ \ \ \ \ (15)

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 {m \times n} XOR game G (with no zero rows or columns) and a solution algebra {\mathcal{A}}, a collection of Linear Operators {\{B_{j}\}} and density matrix {\rho} are the marginal of an optimal strategy iff the map {X_{j} \rightarrow B_{j}} induces a density-matrix representation of {\mathcal{A}} and {\rho} commutes with {im(\mathcal{A})}. 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 ({ \{B_{j}\}}). 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 {m \times n} XOR game G (with no zero rows or columns) and a solution algebra {\mathcal{A}} with minimum dimension {N} among non-zero representations, the strategy for minimum entanglement uses {\log_{2}(N)} entangled bits. The proof for this corollary follows from the eigenspace decomposition of the joint Hilbert Space { H} in terms of { \rho}, which is preserved by the action of { im(\mathcal{A})}. As a result, each eigenspace decomposes into a finite sum of irreducible representations of { \mathcal{A}}. The minimum entanglement is realized when there is exactly one invariant subspace (with one irreducible representation). The entanglement used by such a representation is { \log_{2}(\text{dim}\,H)}.

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, { |{\psi}\rangle} refers to an arbitrary state in { H = H_{A} \otimes H_{B}} (the joint Hilbert space). We can write { |{\psi}\rangle = \sum_{i} |{i}\rangle \lambda |{i}\rangle} over some basis { \{{i}\}}, where { \lambda} is a linear map. Then, the partial trace of { \psi} over { H_{A}} is given by { \rho = \lambda\lambda^{*}}. Let { \mathcal{B}_{A}, \mathcal{B}_{B}} denote the algebra generated by { A_{1},..,A_{m}} and { B_{1},..,B_{n}}. 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 {A}, {B \in H_{A}, H_{B}},

\displaystyle  \|(A \otimes \mathbb{I} - \mathbb{I} \otimes B)|\psi\rangle\| \leq \|\lambda\overline{A} - B\lambda\|_{F}  \ \ \ \ \ (16)

This allows us to conclude that,

\displaystyle  \|(A \otimes \mathbb{I} - \mathbb{I} \otimes B)|\psi\rangle\| \leq \epsilon \implies \|\rho(B) - B\rho\|_{F} \leq 2\epsilon  \ \ \ \ \ (17)

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

\displaystyle  closure(\mathcal{B}_{B}\lambda H_{A}) = closure(\mathcal{B}_{A}\lambda^{*}H_{B}). \\  \ \ \ \ \ (18)

As a special case:

\displaystyle  closure(\mathcal{B}_{B}\lambda H_{A}) = H_{B} \leftrightarrow closure(\rho H_{B}) = H_{B}  \ \ \ \ \ (19)

Forward direction : We use the first lemma to prove commutativity of \rho with all B_{j}, and we use the second lemma to show that the closure of \rho is { H_{B}}. We first show the forward direction: Suppose we are given an optimal quantum strategy (|{\psi}\rangle , \{A_{i}\}_{i \in S}, \{B_{j}\}_{j \in T}) for a game { G}. Then, we fix our optimal vector strategy as:

\displaystyle  u_{i} = (A_{i} \otimes \mathbb{I})|\psi\rangle  \ \ \ \ \ (20)

\displaystyle  v_{j} = (\mathbb{I} \otimes B_{j})|\psi\rangle  \ \ \ \ \ (21)

We can now use Equations (11) and (13) to establish our optimal marginal biases to write a relationship between them and { |{\psi}\rangle} , and apply Lemma (16) to show commutativity and Lemma (17) to show that { im(\mathcal{A})} = cyclic({ B_{j}, \rho}). Using (13) with (20) and (21), we have:

\displaystyle  d_{j}(\mathbb{I}\otimes B_{j})|\psi\rangle = \sum_{i}G_{ij}(A_{i}\otimes\mathbb{I})|\psi\rangle  \ \ \ \ \ (22)

We can now use (17) with { \epsilon = 0} on (22) to see that { \rho} commutes with every { B_{j}}. Additionally, as the terms in (22) constitute linear combinations of { A_{i}} and { B_{j}}, we can compute the closure of their actions on { \lambda H_{A}} and { \lambda^{*} H_{B}}, which will be equivalent. Therefore, { im(\rho)} = { H_{B}}, which follows from the special case of (19). For the dual case, we substitute (20) and (21) into (12):

\displaystyle  c_{i}(A_{i}\otimes\mathbb{I})|\psi\rangle = \sum_{j}G_{ij}(\mathbb{I}\otimes B_{j})|\psi\rangle

On taking the norm of the above on both sides and using a little algebra, we finally obtain the fact that { \{B_{j}\}} satisfy predicate (15) making them the representations of { X_{j}}: { (\sum_{j}G_{ij}B_{j})^{2} = c_{i}^{2}{\mathbb{I}} } This shows that the map from { X_{j} \rightarrow B_{j}} computes a density matrix representation of { \mathcal{A}}, where { \rho} commutes with all { B_{j}}.
Backward Direction : The proof for the backward direction is much less involved: If we knew that { \{B_{j}\}, \rho} constituted the cyclic representation of { \mathcal{A}} with commutativity (with { B_{j}}), then we can use Lemma (19) to conclude that the image of { \rho} on { H} would form a subspace of { \lambda H}. We define: { \overline{A}_{i} = \frac{\sum_{j}G_{ij}B_{j}}{c_{i}} } allowing us to recover our original marginal biases { c_{i}} that satisfy (23) and therefore correspond to the optimal strategy. This shows us that { \{A_{i}\}}, { \{B_{j}\}} 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 {X_{1},..,X_{r}}, there exist one or two irreducible representations of dimension {2^{\left \lfloor{\frac{r}{2}}\right \rfloor}} 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 { \left \lfloor{\frac{r}{2}}\right \rfloor}. However, note that being Clifford means an extra constraint: { X_{i}X_{j} = -X_{j}X_{i}}, { \forall i, j} 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, { \{A_{i}\}}, { \{B_{j}\}} are constructed from a unique set of { \{u_{i}\}}, { \{v_{j}\}}. 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 { m \times n} XOR games { \{G\}} that correspond to generalizations of the CHSH games ({CL_{n}}), such that, the optimal strategy of minimal entanglement is Non-Clifford.


[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 \omega^*(G). Online, December 2014. Lecture Notes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s