Background
Nonlocal Games
A nonlocal game is a cooperative game, traditionally with two players named Alice and Bob and a single referee (also sometimes referred to as a verifier). The referee chooses inputs for each of Alice and Bob from a finite set of inputs via some fixed probability distribution. Alice and Bob, once they receive their inputs, may not communicate in any way, and must give outputs to the referee. The referee decides whether or not the game has been won according to some predicate function of the inputs and outputs.
The value of a nonlocal game on a class of strategies is defined as the supremum of the winning probabilities of all such strategies. The quantum value is the value on the class of quantum strategies (where Alice and Bob can share any finite amount of entanglement), and the classical value is the value on the class of classical strategies. The quantum advantage of a game can then be defined as the difference between these two quantities.
Interest in the quantum values of nonlocal games was popularized by Cleve, Høyer, Toner, and Watrous [9 ] . To use a famous example, in the CHSH game [8 ] , Alice and Bob each receive a single bit and must each output a single bit, winning if the parity (i.e., XOR) of their outputs equals the logical AND of their inputs. The classical value of this game is 3 4 = 0.75 \frac{3}{4}=0.75 4 3 = 0.75 , whereas the quantum value is cos 2 ( π 8 ) ≈ 0.85 \cos^{2}\left(\frac{\pi}{8}\right)\approx0.85 cos 2 ( 8 π ) ≈ 0.85 , so the game has positive quantum advantage. These games have been proposed as experiments to refute “local hidden variable” theories of quantum mechanics [3 ] , which would preclude any quantum advantage. Some such experiments have been successfully run [14 ] .
Building upon this work was the study of XOR games. An XOR game is defined as one where Alice and Bob may each respond with only a single bit, and the referee considers only the inputs and the parity (i.e., XOR) of the outputs when deciding whether the players won. It can be quickly observed that the CHSH game is an XOR game, as indeed is the m = 2 m=2 m = 2 case of the game we study. XOR games have received a substantial amount of study, from investigating their quantum values to bounding the entanglement needed to play optimally, and there is notably a method to compute the optimal solution for an XOR game via a semidefinite program [5 , 9 ] .
One interesting variation on the study of nonlocal games, and one that much of our paper will discuss, is analyzing the synchronous value of a nonlocal game [13 ] . A synchronous strategy is a strategy that guarantees that, if Alice and Bob are given the same input, then they will respond with the same output. Note that if we repeatedly give Alice and Bob the same input across multiple “rounds”, we do not require that they give the same output for each “round”, only that in each “round” Alice’s output matches Bob’s output. The synchronous value of a game for a class of strategies is defined as the supremum of the success probabilities of all synchronous strategies in that class.
Games that require the players to answer (classically impossible) questions about graphs have garnered significant recent research interest. One example of this is the study of the chromatic number and quantum chromatic number of a graph [6 ] . Both can be defined relative to a nonlocal game where Alice and Bob seek to convince a referee that they have a valid m m m -coloring of a graph G = ( V , E ) G=(V,E) G = ( V , E ) . The referee asks each of Alice and Bob what color a specific vertex (v a v_a v a and v b v_b v b , respectively) is. If given the same vertex, they must respond with the same color, and if given adjacent vertices, they must respond with different colors. The chromatic number of a graph G G G is defined as the minimum number of colors for which this graph coloring game has classical value 1. Likewise, the quantum chromatic number of G G G is the minimum number of colors where the graph coloring game has quantum value 1. Notably, not every graph’s quantum chromatic number equals its classical chromatic number: Cameron et al. give a graph with classical chromatic number 5 but quantum chromatic number 4 [6 ] . The graph coloring game on specifically complete graphs has received some special attention, which we will discuss in § 1.4 .
Graph theory has also been used as a tool to investigate values of nonlocal games. In particular, Chailloux et al. construct a “game graph” encoding the verifier’s predicate [7 ] , then bound both the classical and quantum values of a game by an efficiently computable quantity of this graph known as the Lovász theta number [7 , 15 ] .
Nonlocal games, and the quantum advantages that are achievable in some of them, have also shown some relevance to networking. Previous work has investigated how the superior correlation offered by shared entanglement could be used to improve coordination and load balancing in distributed or networked systems [2 , 12 ] .
The m m m -Coloring Game on an n n n -Node Complete Graph
In this paper, we will focus on the m m m -coloring game on the complete graph K n K_n K n . More precisely, Alice and Bob are given inputs x x x and y y y , respectively, from a set of size n n n (which we will represent as [ n ] : = { k ∈ N 0 ∣ k < n } [n] := \{k \in\mathbb{N}_0 \mid k < n\} [ n ] := { k ∈ N 0 ∣ k < n } ) and must give outputs a a a and b b b , respectively, from a set of size m m m (which we will represent as [ m ] [m] [ m ] ), winning when ( x = y ) ⇔ ( a = b ) (x = y) \Leftrightarrow(a = b) ( x = y ) ⇔ ( a = b ) .
To preserve symmetry, we will consider only input distributions π \pi π over [ n ] × [ n ] [n] \times[n] [ n ] × [ n ] that assign equal probability to every pair of inputs where x ≠ y x \ne y x = y and equal probability to every pair of inputs where x = y x = y x = y : i.e., letting p : = P [ x = y ] p := \mathbb{P}[x = y] p := P [ x = y ] , we have π ( x , x ) = p n \pi(x,x) = \frac{p}{n} π ( x , x ) = n p for each x ∈ [ n ] x \in[n] x ∈ [ n ] and π ( x , y ) = 1 − p n ( n − 1 ) \pi(x,y) = \frac{1-p}{n(n-1)} π ( x , y ) = n ( n − 1 ) 1 − p (or 0 when n = 1 n = 1 n = 1 ) whenever x ≠ y x \ne y x = y .
When m ≥ n m \ge n m ≥ n , Alice and Bob may always simply output their respective inputs, in which case the win condition becomes ( x = y ) ⇔ ( x = y ) (x = y) \Leftrightarrow(x = y) ( x = y ) ⇔ ( x = y ) , which is trivially always true and hence this strategy is clearly optimal. Also, when m = 1 m = 1 m = 1 , Alice and Bob both must output 0 and thus have no choice in strategy. Hence, we focus on the interesting case where 2 ≤ m < n 2 \le m < n 2 ≤ m < n .
Similarly, when p = 1 p = 1 p = 1 , the players always win if Alice and Bob both output 0 regardless of their inputs, and when p = 0 p = 0 p = 0 they always win if Alice always outputs 0 and Bob always outputs 1 (which is valid for all m ≥ 2 m \ge2 m ≥ 2 ), so we focus on the interesting case where p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) .
Applications in Distributed Computer Systems
This game can also be interpreted in a load-balancing scenario: imagine a networked system with m m m machines and n n n users. Users can submit jobs (queries that specify a user x x x and y y y respectively, which each correspond to one of the n n n vertices of K n K_n K n ) to two load balancers (Alice and Bob) far enough apart that classical communication between them is not viable. The load balancers must return a machine (a a a and b b b respectively, each corresponding to one of the m m m colors) on which the job should run. We prefer for jobs for the same user to run on the same machine, so if both jobs are for the same user (i.e., x = y x = y x = y ), then we will consider it a success if a = b a = b a = b . Jobs for different users should be spread across different machines, so if x ≠ y x \ne y x = y , a success would require that a ≠ b a \ne b a = b .
This framing also helps to justify the interest in p p p , the probability that Alice and Bob receive the same input. Increasing p p p can be seen as increasing the relative weight in the objective of equal-input scenarios, effectively increasing the penalty for routing one user’s jobs to two different machines relative to the penalty for placing two unrelated jobs on the same machine. Similarly, synchronous strategies for this game (i.e., strategies that guarantee that x = y ⇒ a = b x=y\Rightarrow a=b x = y ⇒ a = b ) can be thought of as strategies for the scenario where a given user’s jobs submitted in the same round absolutely must run on the same machine.
Previous Work
There are a few notable past results that will guide our work here. The first comes from Cameron et al., which states that the quantum chromatic number of a complete graph K n K_n K n is n n n : that is, it is impossible to always convince a verifier (i.e., win our game) of a coloring with m m m colors for any m < n m<n m < n . Thus, they show that the game we study has no perfect quantum strategy. We prove stronger results, bounding the value more tightly and finding the exact value in many cases.
Secondly, Cui et al., in their analysis of the Bipartite Perfect Matching game, establish that there is a quantum advantage for the 2-coloring game played on a uniform input distribution on K 3 K_3 K 3 , but that there is no advantage for K n K_n K n when n ≥ 4 n\geq4 n ≥ 4 [10 ] . This solves a special case of our game where m = 2 m=2 m = 2 and p = 1 n p=\frac{1}{n} p = n 1 .
Finally, Helton et al. bound the optimal synchronous value of the coloring game (on arbitrary graphs, not just complete ones) in terms of the graph correlation function [11 ] , which they compute explicitly for (most) complete graphs [13 ] . We use these theorems to prove that our quantum strategy is optimal in the synchronous case.
Main Results
Our results all concern input distributions where the players receive uniformly random equal inputs with probability p p p and uniformly random unequal inputs with probability 1 − p 1-p 1 − p .
In § 3.2 , we prove that the synchronous classical value of the game we study is
p + ( 1 − p ) ( 1 − ( ⌊ n m ⌋ − 1 ) n + ( ⌈ n m ⌉ + 1 ) ( n m o d m ) n ( n − 1 ) ) . p+(1-p)\left(1-\frac{\left(\left\lfloor\frac{n}{m}\right\rfloor-1\right)n+\left(\left\lceil\frac{n}{m}\right\rceil+1\right)(n\bmod m)}{n(n-1)}\right). p + ( 1 − p ) ( 1 − n ( n − 1 ) ( ⌊ m n ⌋ − 1 ) n + ( ⌈ m n ⌉ + 1 ) ( n mod m ) ) .
In § 3.3 , we prove that this value is the classical value of the game whenever p ≥ 2 m + 2 p\geq\frac{2}{m+2} p ≥ m + 2 2 .
In § 4.1 we present a synchronous quantum strategy for this game with value
p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) , p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right), p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) ,
which is notably the same expression as the classical value when n m o d m = 0 n\bmod m=0 n mod m = 0 . We prove in § 4.3 that this strategy is optimal across all synchronous quantum strategies. We then prove in § 4.4 that the same strategy is optimal across all quantum strategies when p ≥ 2 n − m ( m + 2 ) n − 2 m p\geq\frac{2n-m}{(m+2)n-2m} p ≥ ( m + 2 ) n − 2 m 2 n − m .
Letting r r r be the remainder of n n n divided by m m m , we then show in § 4.6 that this optimal strategy achieves an advantage (in terms of difference in value) of
( 1 − p ) ( r ( m − r ) m n ( n − 1 ) ) . (1-p)\left(\frac{r(m-r)}{mn(n-1)}\right). ( 1 − p ) ( mn ( n − 1 ) r ( m − r ) ) .
over the best classical synchronous strategies, as well as over the best classical strategies when p ≥ 2 m + 2 p\geq\frac{2}{m+2} p ≥ m + 2 2 . Notably, we show that this advantage is 0 if and only if m m m divides n n n .
Preliminaries
We can begin by establishing some helpful results and definitions.
Value
The value ω \omega ω of a strategy is simply defined as the probability that the players win the game when using that strategy. If we define c x y c_{xy} c x y as the probability that a = b a=b a = b given the input pair ( x , y ) (x,y) ( x , y ) , the value can be written as
∑ x = 0 n − 1 p n c x x + ∑ x = 0 n − 1 ∑ y ≠ x 1 − p n ( n − 1 ) ( 1 − c x y ) = p n ∑ x = 0 n − 1 c x x + 1 − p n ( n − 1 ) ∑ x = 0 n − 1 ∑ y ≠ x ( 1 − c x y ) . \sum_{x=0}^{n-1}\frac{p}{n}c_{xx}+\sum_{x=0}^{n-1}\sum_{y\ne x}\frac{1-p}{n(n-1)}(1-c_{xy})=\frac{p}{n}\sum_{x=0}^{n-1}c_{xx}+\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}\sum_{y\ne x}(1-c_{xy}). x = 0 ∑ n − 1 n p c xx + x = 0 ∑ n − 1 y = x ∑ n ( n − 1 ) 1 − p ( 1 − c x y ) = n p x = 0 ∑ n − 1 c xx + n ( n − 1 ) 1 − p x = 0 ∑ n − 1 y = x ∑ ( 1 − c x y ) .
We can insert a term to counteract the skipped index in the sums over y y y , giving
p n ∑ x = 0 n − 1 c x x − 1 − p n ( n − 1 ) ∑ x = 0 n − 1 ( 1 − c x x ) + 1 − p n ( n − 1 ) ∑ x = 0 n − 1 ∑ y = 0 n − 1 ( 1 − c x y ) . \frac{p}{n}\sum_{x=0}^{n-1}c_{xx}-\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}(1-c_{xx})+\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}(1-c_{xy}). n p x = 0 ∑ n − 1 c xx − n ( n − 1 ) 1 − p x = 0 ∑ n − 1 ( 1 − c xx ) + n ( n − 1 ) 1 − p x = 0 ∑ n − 1 y = 0 ∑ n − 1 ( 1 − c x y ) .
Rewriting this expression as a polynomial in the variables { c x y } \{c_{xy}\} { c x y } gives
( 1 − p ) n n − 1 − 1 − p n − 1 + ( p n + 1 − p n ( n − 1 ) ) ∑ x = 0 n − 1 c x x − 1 − p n ( n − 1 ) ∑ x = 0 n − 1 ∑ y = 0 n − 1 c x y . \frac{(1-p)n}{n-1}-\frac{1-p}{n-1}+\left(\frac{p}{n}+\frac{1-p}{n(n-1)}\right)\sum_{x=0}^{n-1}c_{xx}-\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}c_{xy}. n − 1 ( 1 − p ) n − n − 1 1 − p + ( n p + n ( n − 1 ) 1 − p ) x = 0 ∑ n − 1 c xx − n ( n − 1 ) 1 − p x = 0 ∑ n − 1 y = 0 ∑ n − 1 c x y .
The constant term in this polynomial can be simplified to 1 − p 1-p 1 − p .
It is then convenient to define
ξ : = ∑ x = 0 n − 1 c x x \xi:= \sum_{x=0}^{n-1}c_{xx} ξ := x = 0 ∑ n − 1 c xx
and
μ : = ∑ x = 0 n − 1 ∑ y = 0 n − 1 c x y . \mu:= \sum_{x=0}^{n-1}\sum_{y=0}^{n-1}c_{xy}. μ := x = 0 ∑ n − 1 y = 0 ∑ n − 1 c x y .
Since 0 ≤ c x y ≤ 1 0\le c_{xy}\le1 0 ≤ c x y ≤ 1 for all ( x , y ) ∈ [ n ] 2 (x,y)\in[n]^2 ( x , y ) ∈ [ n ] 2 , 0 ≤ ξ ≤ n 0\le\xi\le n 0 ≤ ξ ≤ n and 0 ≤ μ ≤ n 2 0\le\mu\le n^2 0 ≤ μ ≤ n 2 .
Also, μ − ξ = ∑ x = 0 n − 1 ∑ y = 0 n − 1 c x y − ∑ x = 0 n − 1 c x x = ∑ x = 0 n − 1 ∑ y ≠ x c x y ≥ 0 \mu-\xi=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}c_{xy}-\sum_{x=0}^{n-1}c_{xx}=\sum_{x=0}^{n-1}\sum_{y\ne x}c_{xy}\ge0 μ − ξ = ∑ x = 0 n − 1 ∑ y = 0 n − 1 c x y − ∑ x = 0 n − 1 c xx = ∑ x = 0 n − 1 ∑ y = x c x y ≥ 0 , so ξ ≤ μ \xi\le\mu ξ ≤ μ .
We can then write the value in terms of these abbreviations:
ω = 1 − p + ( p n + 1 − p n ( n − 1 ) ) ξ − 1 − p n ( n − 1 ) μ . \omega=1-p+\left(\frac{p}{n}+\frac{1-p}{n(n-1)}\right)\xi-\frac{1-p}{n(n-1)}\mu. ω = 1 − p + ( n p + n ( n − 1 ) 1 − p ) ξ − n ( n − 1 ) 1 − p μ .
We can ignore the constant term during optimization since it does not depend on the strategy. Furthermore, 1 − p > 0 1-p>0 1 − p > 0 whenever p < 1 p<1 p < 1 , and n ( n − 1 ) > 0 n(n-1)>0 n ( n − 1 ) > 0 for all n ≥ 2 n\ge2 n ≥ 2 , so we can multiply the rest by n ( n − 1 ) 1 − p \frac{n(n-1)}{1-p} 1 − p n ( n − 1 ) without changing signs, giving the new objective
ν : = ( p ( n − 1 ) 1 − p + 1 ) ξ − μ . \nu:=\left(\frac{p(n-1)}{1-p}+1\right)\xi-\mu. ν := ( 1 − p p ( n − 1 ) + 1 ) ξ − μ .
We can then convert from ν \nu ν to the value ω \omega ω via
ω = 1 − p + 1 − p n ( n − 1 ) ν \omega= 1-p+\frac{1-p}{n(n-1)}\nu ω = 1 − p + n ( n − 1 ) 1 − p ν
We will now let s : = p ( n − 1 ) 1 − p + 1 s := \frac{p(n-1)}{1-p}+1 s := 1 − p p ( n − 1 ) + 1 denote the coefficient of ξ \xi ξ in ν \nu ν ; then
s − p s = s ( 1 − p ) = p ( n − 1 ) + 1 − p = p n − p − p + 1 = p ( n − 2 ) + 1 , s-ps=s(1-p)=p(n-1)+1-p=pn-p-p+1=p(n-2)+1, s − p s = s ( 1 − p ) = p ( n − 1 ) + 1 − p = p n − p − p + 1 = p ( n − 2 ) + 1 ,
so s − 1 = p ( n + s − 2 ) s-1=p(n+s-2) s − 1 = p ( n + s − 2 ) and thus p = s − 1 n + s − 2 p=\frac{s-1}{n+s-2} p = n + s − 2 s − 1 .
Lemma 2.1.1. s s s is monotonically increasing with respect to p p p on the domain p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) .
Proof. Since n > 1 n>1 n > 1 , the numerator p ( n − 1 ) p(n-1) p ( n − 1 ) in p ( n − 1 ) 1 − p \frac{p(n-1)}{1-p} 1 − p p ( n − 1 ) , the non-constant term of s s s , is monotonically increasing in p p p and positive whenever p > 0 p>0 p > 0 and thus all p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) .
Also, the denominator 1 − p 1-p 1 − p is positive on p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) and monotonically decreasing in p p p .
Thus, the fraction p ( n − 1 ) 1 − p \frac{p(n-1)}{1-p} 1 − p p ( n − 1 ) is positive and increasing in magnitude on p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , so p ( n − 1 ) 1 − p \frac{p(n-1)}{1-p} 1 − p p ( n − 1 ) , and thus s = p ( n − 1 ) 1 − p + 1 s=\frac{p(n-1)}{1-p}+1 s = 1 − p p ( n − 1 ) + 1 , are increasing on p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , as desired.
The coefficient of ξ \xi ξ is positive and the coefficient of μ \mu μ is negative for all p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , so any optimal strategy minimizes μ \mu μ for its value of ξ \xi ξ and conversely maximizes ξ \xi ξ for its value of μ \mu μ .
We sometimes require that Alice and Bob play synchronous strategies: i.e., strategies where P [ a = b ∣ x = y ] = 1 \mathbb{P}[a=b\mid x=y]=1 P [ a = b ∣ x = y ] = 1 , which fixes ξ = ∑ x = 0 n − 1 c x x = ∑ x = 0 n − 1 1 = n \xi=\sum_{x=0}^{n-1}c_{xx}=\sum_{x=0}^{n-1}1=n ξ = ∑ x = 0 n − 1 c xx = ∑ x = 0 n − 1 1 = n . In this case, the goal is simply to minimize μ \mu μ subject to the synchronous constraint.
Theorem 2.1.2. If a synchronous strategy is optimal for some p ∗ ∈ [ 0 , 1 ] p^* \in[0,1] p ∗ ∈ [ 0 , 1 ] , it is optimal for all p ∈ [ p ∗ , 1 ] p \in[p^*,1] p ∈ [ p ∗ , 1 ] as well.
Proof. Since ξ \xi ξ and μ \mu μ do not depend on p p p , any strategy’s value is linear in p p p .
Any synchronous strategy has value 1 (and hence is optimal) at p = 1 p=1 p = 1 .
Hence, if some synchronous strategy S S S is optimal at p = p ∗ p=p^* p = p ∗ , any other strategy S ′ S' S ′ will have nonstrictly lower value at p = p ∗ p=p^* p = p ∗ and p = 1 p=1 p = 1 , and thus the value of S ′ S' S ′ cannot cross above that of S S S at any p ∈ [ p ∗ , 1 ] p \in[p^*,1] p ∈ [ p ∗ , 1 ] .
Mixed Strategies
We allow the players to use mixed (i.e., random) strategies, and since Alice and Bob can communicate before receiving their inputs, they may have access to shared random values, so their choices of strategies may not be independent.
Examples of mixed strategies in our game include classical random functions, randomly chosen measurement operators, and shared random classical values or mixed quantum states.
Formally, we can describe mixed strategies as distributions over the space of pure strategies.
However, the value of such a strategy is then a convex combination (weighted by probability) of values of pure strategies and hence cannot exceed the supremum of those values.
Thus, when searching for optima, we need only consider pure strategies.
Classical Strategies
When giving their respective outputs, each player knows only their own input, and has no information about the other player’s input or output (beyond the prior of their strategy).
A pure classical strategy for this game is then given by a pair ( a , b ) ∈ ( [ n ] → [ m ] ) 2 (a,b) \in([n] \to[m])^2 ( a , b ) ∈ ([ n ] → [ m ] ) 2 of deterministic functions specifying the players’ outputs in response to each input.
Values of Classical Strategies
The value of such a strategy pair can be computed as
ω ( a , b ) = P [ a ( x ) = b ( y ) ↔ x = y ∣ ( x , y ) ∼ π [ n ] 2 ] . \omega(a,b) = \mathbb{P}\left[a(x) = b(y) \leftrightarrow x = y \mid(x,y) \sim\pi_{[n]^2}\right]. ω ( a , b ) = P [ a ( x ) = b ( y ) ↔ x = y ∣ ( x , y ) ∼ π [ n ] 2 ] .
Alternatively, c x y : = P [ a = b ∣ ( x , y ) ] = 1 c_{xy} := \mathbb{P}[a=b \mid(x,y)] = 1 c x y := P [ a = b ∣ ( x , y )] = 1 if a ( x ) = b ( y ) a(x)=b(y) a ( x ) = b ( y ) and c x y = 0 c_{xy}=0 c x y = 0 otherwise, so
ξ : = ∑ x = 0 n − 1 c x x = ∣ { x ∈ [ n ] ∣ a ( x ) = b ( x ) } ∣ \xi:= \sum_{x=0}^{n-1} c_{xx} = \left|\{x \in[n] \mid a(x)=b(x)\}\right| ξ := x = 0 ∑ n − 1 c xx = ∣ { x ∈ [ n ] ∣ a ( x ) = b ( x )} ∣
and
μ : = ∑ x = 0 n − 1 ∑ y = 0 n − 1 c x y = ∣ { ( x , y ) ∈ [ n ] 2 ∣ a ( x ) = b ( y ) } ∣ . \mu:= \sum_{x=0}^{n-1}\sum_{y=0}^{n-1} c_{xy} = \left|\{(x,y) \in[n]^2 \mid a(x)=b(y)\}\right|. μ := x = 0 ∑ n − 1 y = 0 ∑ n − 1 c x y = {( x , y ) ∈ [ n ] 2 ∣ a ( x ) = b ( y )} .
Partitioning the former set according to output value gives ξ = ∑ k = 0 m − 1 ξ k \xi= \sum_{k=0}^{m-1} \xi_k ξ = ∑ k = 0 m − 1 ξ k , where
ξ k : = ∣ { x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } ∣ . \xi_k := \left|\{x \in[n] \mid a(x)=b(x)=k\}\right|. ξ k := ∣ { x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } ∣ .
Partitioning the latter set according to output value gives μ = ∑ k = 0 m − 1 μ k \mu= \sum_{k=0}^{m-1} \mu_k μ = ∑ k = 0 m − 1 μ k , where
μ k : = ∣ { ( x , y ) ∈ [ n ] 2 ∣ a ( x ) = b ( y ) = k } ∣ = ∣ { x ∈ [ n ] ∣ a ( x ) = k } ∣ ⋅ ∣ { y ∈ [ n ] ∣ b ( y ) = k } ∣ . \mu_k := \left|\{(x,y) \in[n]^2 \mid a(x)=b(y)=k\}\right| = \left|\{x \in[n] \mid a(x)=k\}\right| \cdot\left|\{y \in[n] \mid b(y)=k\}\right|. μ k := {( x , y ) ∈ [ n ] 2 ∣ a ( x ) = b ( y ) = k } = ∣ { x ∈ [ n ] ∣ a ( x ) = k } ∣ ⋅ ∣ { y ∈ [ n ] ∣ b ( y ) = k } ∣ .
Defining a k : = ∣ { x ∈ [ n ] ∣ a ( x ) = k } ∣ a_k := \left|\{x \in[n] \mid a(x)=k\}\right| a k := ∣ { x ∈ [ n ] ∣ a ( x ) = k } ∣ and b k : = ∣ { y ∈ [ n ] ∣ b ( y ) = k } ∣ b_k := \left|\{y \in[n] \mid b(y)=k\}\right| b k := ∣ { y ∈ [ n ] ∣ b ( y ) = k } ∣ gives μ = ∑ k = 0 m − 1 a k b k \mu= \sum_{k=0}^{m-1} a_kb_k μ = ∑ k = 0 m − 1 a k b k .
Lemma 3.1.1. For any output k k k , we must have ξ k ≤ a k \xi_k \leq a_k ξ k ≤ a k and ξ k ≤ b k \xi_k \leq b_k ξ k ≤ b k .
Proof. { x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } ⊆ { x ∈ [ n ] ∣ a ( x ) = k } \{x \in[n] \mid a(x)=b(x)=k\} \subseteq\{x \in[n] \mid a(x)=k\} { x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } ⊆ { x ∈ [ n ] ∣ a ( x ) = k } , so ξ k ≤ a k \xi_k \leq a_k ξ k ≤ a k .
Likewise, { x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } ⊆ { x ∈ [ n ] ∣ b ( x ) = k } \{x \in[n] \mid a(x)=b(x)=k\} \subseteq\{x \in[n] \mid b(x)=k\} { x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } ⊆ { x ∈ [ n ] ∣ b ( x ) = k } , so ξ k ≤ b k \xi_k \leq b_k ξ k ≤ b k .
Lemma 3.1.2. Any valid classical strategy has μ ≥ ∑ k = 0 m − 1 ξ k 2 \mu\geq\sum_{k=0}^{m-1} \xi_k^2 μ ≥ ∑ k = 0 m − 1 ξ k 2 .
Proof. By Lemma 3.1.1 , ξ k 2 = ξ k ξ k ≤ a k b k = μ k \xi_k^2 = \xi_k\xi_k \leq a_kb_k = \mu_k ξ k 2 = ξ k ξ k ≤ a k b k = μ k for each k k k , so μ = ∑ k = 0 m − 1 μ k ≥ ∑ k = 0 m − 1 ξ k 2 \mu= \sum_{k=0}^{m-1} \mu_k \geq\sum_{k=0}^{m-1} \xi_k^2 μ = ∑ k = 0 m − 1 μ k ≥ ∑ k = 0 m − 1 ξ k 2 .
Lemma 3.1.3. For fixed ξ = ∑ k = 0 m − 1 ξ k \xi= \sum_{k=0}^{m-1}\xi_k ξ = ∑ k = 0 m − 1 ξ k , the quantity ∑ k = 0 m − 1 ξ k 2 \sum_{k=0}^{m-1}\xi_k^2 ∑ k = 0 m − 1 ξ k 2 is minimized when exactly ξ m o d m \xi\bmod m ξ mod m of the ξ k \xi_k ξ k equal ⌊ ξ m ⌋ + 1 \left\lfloor\frac{\xi}{m}\right\rfloor+1 ⌊ m ξ ⌋ + 1 , and the rest equal ⌊ ξ m ⌋ \left\lfloor\frac{\xi}{m}\right\rfloor ⌊ m ξ ⌋ .
Proof. If ξ h − ξ l > 1 \xi_h-\xi_l>1 ξ h − ξ l > 1 for some ( h , l ) ∈ [ m ] 2 (h,l)\in[m]^2 ( h , l ) ∈ [ m ] 2 , we could take any x x x for which a ( x ) = b ( x ) = h a(x)=b(x)=h a ( x ) = b ( x ) = h (which must exist since ξ h > 1 + ξ l ≥ 1 \xi_h>1+\xi_l\ge1 ξ h > 1 + ξ l ≥ 1 ) and set a ( x ) = b ( x ) = l a(x)=b(x)=l a ( x ) = b ( x ) = l instead.
Then ξ h \xi_h ξ h decreases by 1, ξ l \xi_l ξ l increases by 1, and no other ξ k \xi_k ξ k changes, which adds
( ξ h − 1 ) 2 − ξ h 2 + ( ξ l + 1 ) 2 − ξ l 2 = − 2 ξ h + 1 + 2 ξ l + 1 = 2 ( ξ l + 1 − ξ h ) < 2 ⋅ 0 = 0 (\xi_h-1)^2-\xi_h^2+(\xi_l+1)^2-\xi_l^2=-2\xi_h+1+2\xi_l+1=2(\xi_l+1-\xi_h)<2\cdot0=0 ( ξ h − 1 ) 2 − ξ h 2 + ( ξ l + 1 ) 2 − ξ l 2 = − 2 ξ h + 1 + 2 ξ l + 1 = 2 ( ξ l + 1 − ξ h ) < 2 ⋅ 0 = 0
to ∑ k = 0 m − 1 ξ k 2 \sum_{k=0}^{m-1}\xi_k^2 ∑ k = 0 m − 1 ξ k 2 : strategies whose values of ξ k \xi_k ξ k differ by more than 1 cannot attain the minimum.
Any strategy attaining the minimum then has ξ k ∈ { q ξ , q ξ + 1 } \xi_k\in\{q_\xi,q_\xi+1\} ξ k ∈ { q ξ , q ξ + 1 } for all k ∈ [ m ] k\in[m] k ∈ [ m ] for some q ξ q_\xi q ξ .
We can further assume without loss of generality that ξ k = q ξ \xi_k=q_\xi ξ k = q ξ for some k ∈ [ m ] k\in[m] k ∈ [ m ] , since if all ξ k = q ξ + 1 \xi_k=q_\xi+1 ξ k = q ξ + 1 we could just choose q ξ q_\xi q ξ to be q ξ + 1 q_\xi+1 q ξ + 1 . Then letting r ξ : = ∣ { k ∈ [ m ] ∣ ξ k = q ξ + 1 } ∣ r_\xi:=|\{k\in[m]\mid\xi_k=q_\xi+1\}| r ξ := ∣ { k ∈ [ m ] ∣ ξ k = q ξ + 1 } ∣ ,
ξ = ∑ k = 0 m − 1 ξ k = ( m − r ξ ) q ξ + r ξ ( q ξ + 1 ) = m q ξ − r ξ q ξ + r ξ q ξ + r ξ = m q ξ + r ξ , \xi=\sum_{k=0}^{m-1}\xi_k=(m-r_\xi)q_\xi+r_\xi(q_\xi+1)=mq_\xi-r_\xi q_\xi+r_\xi q_\xi+r_\xi=mq_\xi+r_\xi, ξ = k = 0 ∑ m − 1 ξ k = ( m − r ξ ) q ξ + r ξ ( q ξ + 1 ) = m q ξ − r ξ q ξ + r ξ q ξ + r ξ = m q ξ + r ξ ,
and since r ξ r_\xi r ξ is the cardinality of a proper subset of [ m ] [m] [ m ] , r ξ ∈ [ 0 , m ) r_\xi\in[0,m) r ξ ∈ [ 0 , m ) .
Therefore, by the Division Algorithm, r ξ = ξ m o d m r_\xi=\xi\bmod m r ξ = ξ mod m and q ξ = ⌊ ξ m ⌋ q_\xi=\left\lfloor\frac{\xi}{m}\right\rfloor q ξ = ⌊ m ξ ⌋ , as desired.
Lemma 3.1.4. The minimum value of ∑ k = 0 m − 1 ξ k 2 \sum_{k=0}^{m-1}\xi_k^2 ∑ k = 0 m − 1 ξ k 2 for any fixed ξ = ∑ k = 0 m − 1 ξ k \xi=\sum_{k=0}^{m-1}\xi_k ξ = ∑ k = 0 m − 1 ξ k is exactly
⌊ ξ m ⌋ 2 ( m − ( ξ m o d m ) ) + ( ⌊ ξ m ⌋ + 1 ) 2 ( ξ m o d m ) . \left\lfloor\frac{\xi}{m}\right\rfloor^2(m-(\xi\bmod m))+\left(\left\lfloor\frac{\xi}{m}\right\rfloor+1\right)^2(\xi\bmod m). ⌊ m ξ ⌋ 2 ( m − ( ξ mod m )) + ( ⌊ m ξ ⌋ + 1 ) 2 ( ξ mod m ) .
Proof. This is the value of ∑ k = 0 m − 1 ξ k 2 \sum_{k=0}^{m-1}\xi_k^2 ∑ k = 0 m − 1 ξ k 2 attained by the minimizer, as proven in Lemma 3.1.3 .
Synchronous Classical Strategies
In order to satisfy the definition that Alice and Bob always give equal outputs when given equal inputs, synchronous strategies must have a ( x ) = b ( x ) a(x)=b(x) a ( x ) = b ( x ) for all x ∈ [ n ] x\in[n] x ∈ [ n ] (i.e., a = b a=b a = b ), so
{ x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } = { x ∈ [ n ] ∣ a ( x ) = k } = { x ∈ [ n ] ∣ b ( x ) = k } \{x\in[n]\mid a(x)=b(x)=k\}=\{x\in[n]\mid a(x)=k\}=\{x\in[n]\mid b(x)=k\} { x ∈ [ n ] ∣ a ( x ) = b ( x ) = k } = { x ∈ [ n ] ∣ a ( x ) = k } = { x ∈ [ n ] ∣ b ( x ) = k }
and thus ξ k = a k = b k \xi_k=a_k=b_k ξ k = a k = b k , so μ = ∑ k = 0 m − 1 a k b k = ∑ k = 0 m − 1 ξ k ξ k = ∑ k = 0 m − 1 ξ k 2 \mu=\sum_{k=0}^{m-1}a_kb_k=\sum_{k=0}^{m-1}\xi_k\xi_k=\sum_{k=0}^{m-1}\xi_k^2 μ = ∑ k = 0 m − 1 a k b k = ∑ k = 0 m − 1 ξ k ξ k = ∑ k = 0 m − 1 ξ k 2 exactly.
Also, ξ = ∑ k = 0 m − 1 ξ k = ∑ k = 0 m − 1 a k = n \xi=\sum_{k=0}^{m-1}\xi_k=\sum_{k=0}^{m-1}a_k=n ξ = ∑ k = 0 m − 1 ξ k = ∑ k = 0 m − 1 a k = n , confirming that such strategies are indeed synchronous.
We now define r : = n m o d m r:=n\bmod m r := n mod m and q : = ⌊ n m ⌋ q:=\left\lfloor\frac{n}{m}\right\rfloor q := ⌊ m n ⌋ , so that n = q m + r n=qm+r n = q m + r and r ∈ [ 0 , m ) r\in[0,m) r ∈ [ 0 , m ) .
Theorem 3.2.1. The optimal classical synchronous strategy has μ = q 2 ( m − r ) + ( q + 1 ) 2 r \mu=q^2(m-r)+(q+1)^2r μ = q 2 ( m − r ) + ( q + 1 ) 2 r .
Proof. For synchronous strategies, μ = ∑ k = 0 m − 1 ξ k 2 \mu=\sum_{k=0}^{m-1}\xi_k^2 μ = ∑ k = 0 m − 1 ξ k 2 exactly and ξ = n \xi=n ξ = n , so by Lemma 3.1.4 , the minimum value of μ \mu μ across all synchronous strategies is exactly q 2 ( m − r ) + ( q + 1 ) 2 r q^2(m-r)+(q+1)^2r q 2 ( m − r ) + ( q + 1 ) 2 r .
Remark. One explicit strategy that attains this μ \mu μ has a ( x ) = b ( x ) = x m o d m a(x)=b(x)=x\bmod m a ( x ) = b ( x ) = x mod m for all x ∈ [ n ] x\in[n] x ∈ [ n ] .
Remark. The optimal synchronous strategy distributes inputs across outputs as uniformly as possible, which parallels the saturation condition for the Cauchy-Schwarz inequality invoked in bounding the quantum optima, except that indivisibility may prevent the numbers of inputs allocated to each output from being exactly equal in the classical case.
Theorem 3.2.2. The classical synchronous value of this game is
p + ( 1 − p ) ( 1 − ( q − 1 ) n + ( q + 1 ) r n ( n − 1 ) ) . p+(1-p)\left(1-\frac{(q-1)n+(q+1)r}{n(n-1)}\right). p + ( 1 − p ) ( 1 − n ( n − 1 ) ( q − 1 ) n + ( q + 1 ) r ) .
Proof. Recall that we can write the strategy’s value in terms of ξ \xi ξ and μ \mu μ .
ω = 1 − p + ( p n + 1 − p n ( n − 1 ) ) ξ − 1 − p n ( n − 1 ) μ . \omega=1-p+\left(\frac{p}{n}+\frac{1-p}{n(n-1)}\right)\xi-\frac{1-p}{n(n-1)}\mu. ω = 1 − p + ( n p + n ( n − 1 ) 1 − p ) ξ − n ( n − 1 ) 1 − p μ .
By Theorem 3.2.1 , the optimal classical synchronous strategy has μ = q 2 ( m − r ) + ( q + 1 ) 2 r \mu=q^2(m-r)+(q+1)^2r μ = q 2 ( m − r ) + ( q + 1 ) 2 r , so
ω = 1 − p + ( p n + 1 − p n ( n − 1 ) ) n − 1 − p n ( n − 1 ) ( q 2 ( m − r ) + ( q + 1 ) 2 r ) = 1 − p + p + 1 − p n − 1 − 1 − p n ( n − 1 ) ( q 2 ( m − r ) + ( q + 1 ) 2 r ) = p + ( 1 − p ) ( 1 + n − ( q 2 ( m − r ) + ( q + 1 ) 2 r ) n ( n − 1 ) ) . \begin{aligned}
\omega=1-p+\left(\frac{p}{n}+\frac{1-p}{n(n-1)}\right)n-\frac{1-p}{n(n-1)}\left(q^2(m-r)+(q+1)^2r\right) \\
&=1-p+p+\frac{1-p}{n-1}-\frac{1-p}{n(n-1)}\left(q^2(m-r)+(q+1)^2r\right) \\
&=p+(1-p)\left(1+\frac{n-\left(q^2(m-r)+(q+1)^2r\right)}{n(n-1)}\right).
\end{aligned} ω = 1 − p + ( n p + n ( n − 1 ) 1 − p ) n − n ( n − 1 ) 1 − p ( q 2 ( m − r ) + ( q + 1 ) 2 r ) = 1 − p + p + n − 1 1 − p − n ( n − 1 ) 1 − p ( q 2 ( m − r ) + ( q + 1 ) 2 r ) = p + ( 1 − p ) ( 1 + n ( n − 1 ) n − ( q 2 ( m − r ) + ( q + 1 ) 2 r ) ) .
Since n = m q + r n=mq+r n = m q + r , we can simplify the term q 2 ( m − r ) + ( q + 1 ) 2 r q^2(m-r)+(q+1)^2r q 2 ( m − r ) + ( q + 1 ) 2 r to
q 2 m − q 2 r + ( q 2 + 2 q + 1 ) r = q 2 m + 2 q r + r = q ( m q + r ) + q r + r = q n + ( q + 1 ) r . q^2m-q^2r+(q^2+2q+1)r=q^2m+2qr+r=q(mq+r)+qr+r=qn+(q+1)r. q 2 m − q 2 r + ( q 2 + 2 q + 1 ) r = q 2 m + 2 q r + r = q ( m q + r ) + q r + r = q n + ( q + 1 ) r .
Therefore, as desired,
ω = p + ( 1 − p ) ( 1 + n − ( q n + ( q + 1 ) r ) n ( n − 1 ) ) = p + ( 1 − p ) ( 1 − ( q − 1 ) n + ( q + 1 ) r n ( n − 1 ) ) . \omega=p+(1-p)\left(1+\frac{n-(qn+(q+1)r)}{n(n-1)}\right)=p+(1-p)\left(1-\frac{(q-1)n+(q+1)r}{n(n-1)}\right). ω = p + ( 1 − p ) ( 1 + n ( n − 1 ) n − ( q n + ( q + 1 ) r ) ) = p + ( 1 − p ) ( 1 − n ( n − 1 ) ( q − 1 ) n + ( q + 1 ) r ) .
Classical Value
We now prove that the synchronous strategy yielded by Theorem 3.2.1 is optimal among all classical strategies if the probability p p p that Alice and Bob get equal inputs is at least 2 m + 2 \frac{2}{m+2} m + 2 2 .
Recall that we defined s : = p ( n − 1 ) 1 − p + 1 s:=\frac{p(n-1)}{1-p}+1 s := 1 − p p ( n − 1 ) + 1 , and that s s s is monotonic in p p p by Lemma 2.1.1 .
Lemma 3.3.1. Classically, a synchronous strategy is optimal when s = 2 ⌊ n − 1 m ⌋ + 1 s=2\left\lfloor\frac{n-1}{m}\right\rfloor+1 s = 2 ⌊ m n − 1 ⌋ + 1 .
Proof. By Lemmas 3.1.2 and 3.1.4 ,
μ ≥ ∑ k = 0 m − 1 ξ k 2 ≥ ⌊ ξ m ⌋ 2 ( m − ( ξ m o d m ) ) + ( ⌊ ξ m ⌋ + 1 ) 2 ( ξ m o d m ) . \mu\ge\sum_{k=0}^{m-1}\xi_k^2 \ge\left\lfloor\frac{\xi}{m}\right\rfloor^2(m-(\xi\bmod m))+\left(\left\lfloor\frac{\xi}{m}\right\rfloor+1\right)^2(\xi\bmod m). μ ≥ k = 0 ∑ m − 1 ξ k 2 ≥ ⌊ m ξ ⌋ 2 ( m − ( ξ mod m )) + ( ⌊ m ξ ⌋ + 1 ) 2 ( ξ mod m ) .
If m ∣ ξ m\mid\xi m ∣ ξ , we have ⌊ ξ m ⌋ = ⌊ ξ − 1 m ⌋ + 1 \left\lfloor\frac{\xi}{m}\right\rfloor=\left\lfloor\frac{\xi-1}{m}\right\rfloor+1 ⌊ m ξ ⌋ = ⌊ m ξ − 1 ⌋ + 1 , so reducing ξ \xi ξ by 1 1 1 decreases the bound on μ \mu μ by
⌊ ξ m ⌋ 2 − ( ⌊ ξ m ⌋ − 1 ) 2 = 2 ⌊ ξ m ⌋ − 1 = 2 ⌊ ξ − 1 m ⌋ + 1. \left\lfloor\frac{\xi}{m}\right\rfloor^2-\left(\left\lfloor\frac{\xi}{m}\right\rfloor-1\right)^2=2\left\lfloor\frac{\xi}{m}\right\rfloor-1=2\left\lfloor\frac{\xi-1}{m}\right\rfloor+1. ⌊ m ξ ⌋ 2 − ( ⌊ m ξ ⌋ − 1 ) 2 = 2 ⌊ m ξ ⌋ − 1 = 2 ⌊ m ξ − 1 ⌋ + 1.
Otherwise, ⌊ ξ m ⌋ = ⌊ ξ − 1 m ⌋ \left\lfloor\frac{\xi}{m}\right\rfloor=\left\lfloor\frac{\xi-1}{m}\right\rfloor ⌊ m ξ ⌋ = ⌊ m ξ − 1 ⌋ , so reducing ξ \xi ξ by 1 1 1 again decreases the bound on μ \mu μ by
( ⌊ ξ m ⌋ + 1 ) 2 − ⌊ ξ m ⌋ 2 = 2 ⌊ ξ m ⌋ + 1 = 2 ⌊ ξ − 1 m ⌋ + 1. \left(\left\lfloor\frac{\xi}{m}\right\rfloor+1\right)^2-\left\lfloor\frac{\xi}{m}\right\rfloor^2=2\left\lfloor\frac{\xi}{m}\right\rfloor+1=2\left\lfloor\frac{\xi-1}{m}\right\rfloor+1. ( ⌊ m ξ ⌋ + 1 ) 2 − ⌊ m ξ ⌋ 2 = 2 ⌊ m ξ ⌋ + 1 = 2 ⌊ m ξ − 1 ⌋ + 1.
Furthermore, since 2 ⌊ ξ − 1 m ⌋ + 1 2\left\lfloor\frac{\xi-1}{m}\right\rfloor+1 2 ⌊ m ξ − 1 ⌋ + 1 is (nonstrictly) monotonic in ξ \xi ξ , by induction on ξ \xi ξ , reducing ξ \xi ξ by any amount h ∈ Z + h\in\mathbb{Z}^{+} h ∈ Z + decreases the bound on μ \mu μ by at most h ( 2 ⌊ ξ − 1 m ⌋ + 1 ) h\left(2\left\lfloor\frac{\xi-1}{m}\right\rfloor+1\right) h ( 2 ⌊ m ξ − 1 ⌋ + 1 ) .
By Theorem 3.2.1 , μ = q 2 ( m − r ) + ( q + 1 ) 2 r \mu=q^2(m-r)+(q+1)^2r μ = q 2 ( m − r ) + ( q + 1 ) 2 r is attained by some synchronous strategy.
Therefore, ( 2 ⌊ n − 1 m ⌋ + 1 ) ( n − ξ ) ≥ q 2 ( m − r ) + ( q + 1 ) 2 r − μ \left(2\left\lfloor\frac{n-1}{m}\right\rfloor+1\right)(n-\xi)\ge q^2(m-r)+(q+1)^2r-\mu ( 2 ⌊ m n − 1 ⌋ + 1 ) ( n − ξ ) ≥ q 2 ( m − r ) + ( q + 1 ) 2 r − μ , so
( 2 ⌊ n − 1 m ⌋ + 1 ) n − ( q 2 ( m − r ) + ( q + 1 ) 2 r ) ≥ ( 2 ⌊ n − 1 m ⌋ + 1 ) ξ − μ . \left(2\left\lfloor\frac{n-1}{m}\right\rfloor+1\right)n-\left(q^2(m-r)+(q+1)^2r\right)\ge\left(2\left\lfloor\frac{n-1}{m}\right\rfloor+1\right)\xi-\mu. ( 2 ⌊ m n − 1 ⌋ + 1 ) n − ( q 2 ( m − r ) + ( q + 1 ) 2 r ) ≥ ( 2 ⌊ m n − 1 ⌋ + 1 ) ξ − μ .
the synchronous strategy has at least as large a value of ν : = ξ δ − μ \nu:=\xi\delta-\mu ν := ξ δ − μ , and hence at least as large a value ω \omega ω , as any other strategy at s = 2 ⌊ n − 1 m ⌋ + 1 s=2\left\lfloor\frac{n-1}{m}\right\rfloor+1 s = 2 ⌊ m n − 1 ⌋ + 1 .
Theorem 3.3.2. Classically, a synchronous strategy is optimal for all p ≥ 2 m + 2 p\ge\frac{2}{m+2} p ≥ m + 2 2 .
Proof. Since n > 1 n>1 n > 1 and ⌊ n − 1 m ⌋ ≤ n − 1 m \left\lfloor\frac{n-1}{m}\right\rfloor\le\frac{n-1}{m} ⌊ m n − 1 ⌋ ≤ m n − 1 , the value of p p p corresponding to s = 2 ⌊ n − 1 m ⌋ + 1 s=2\left\lfloor\frac{n-1}{m}\right\rfloor+1 s = 2 ⌊ m n − 1 ⌋ + 1 is
p = ( 2 ⌊ n − 1 m ⌋ + 1 ) − 1 n + ( 2 ⌊ n − 1 m ⌋ + 1 ) − 2 = 2 ⌊ n − 1 m ⌋ n + 2 ⌊ n − 1 m ⌋ − 1 ≤ 2 n − 1 m n − 1 + 2 n − 1 m = 2 m + 2 . p=\frac{\left(2\left\lfloor\frac{n-1}{m}\right\rfloor+1\right)-1}{n+\left(2\left\lfloor\frac{n-1}{m}\right\rfloor+1\right)-2}
=\frac{2\left\lfloor\frac{n-1}{m}\right\rfloor}{n+2\left\lfloor\frac{n-1}{m}\right\rfloor-1}
\le\frac{2\frac{n-1}{m}}{n-1+2\frac{n-1}{m}}
=\frac{2}{m+2}. p = n + ( 2 ⌊ m n − 1 ⌋ + 1 ) − 2 ( 2 ⌊ m n − 1 ⌋ + 1 ) − 1 = n + 2 ⌊ m n − 1 ⌋ − 1 2 ⌊ m n − 1 ⌋ ≤ n − 1 + 2 m n − 1 2 m n − 1 = m + 2 2 .
By Lemma 3.3.1 , a synchronous strategy is optimal at s = 2 ⌊ n − 1 m ⌋ + 1 s=2\left\lfloor\frac{n-1}{m}\right\rfloor+1 s = 2 ⌊ m n − 1 ⌋ + 1 and thus at some p ≤ 2 m + 2 p\le\frac{2}{m+2} p ≤ m + 2 2 . Therefore, by Theorem 2.1.2 , it is optimal for all p ≥ 2 m + 2 p\ge\frac{2}{m+2} p ≥ m + 2 2 , as desired.
Theorem 3.3.3. When p ≥ 2 m + 2 p\ge\frac{2}{m+2} p ≥ m + 2 2 , the classical value of this game is
p + ( 1 − p ) ( 1 − ( q − 1 ) n + ( q + 1 ) r n ( n − 1 ) ) . p+(1-p)\left(1-\frac{(q-1)n+(q+1)r}{n(n-1)}\right). p + ( 1 − p ) ( 1 − n ( n − 1 ) ( q − 1 ) n + ( q + 1 ) r ) .
Proof. By Theorem 3.3.2, the strategy defined in § 3.2 is optimal among classical strategies.
Then our game’s value equals the value of this strategy, which by Theorem 3.2.2 is
p + ( 1 − p ) ( 1 − ( q − 1 ) n + ( q + 1 ) r n ( n − 1 ) ) . p+(1-p)\left(1-\frac{(q-1)n+(q+1)r}{n(n-1)}\right). p + ( 1 − p ) ( 1 − n ( n − 1 ) ( q − 1 ) n + ( q + 1 ) r ) .
Other Classical Strategies
Having shown that a synchronous strategy is optimal whenever p ≥ 2 m + 2 p \ge\frac{2}{m+2} p ≥ m + 2 2 , we now turn our attention to determining which classical strategies could be optimal when p p p is small.
Recall that a k : = ∣ { x ∣ a ( x ) = k } ∣ a_k := |\{x \mid a(x) = k\}| a k := ∣ { x ∣ a ( x ) = k } ∣ , b k : = ∣ { y ∣ b ( y ) = k } ∣ b_k := |\{y \mid b(y) = k\}| b k := ∣ { y ∣ b ( y ) = k } ∣ , and ξ k : = ∣ { x ∣ a ( x ) = b ( x ) = k } ∣ \xi_k := |\{x \mid a(x) = b(x) = k\}| ξ k := ∣ { x ∣ a ( x ) = b ( x ) = k } ∣ .
Lemma 3.4.1. For any fixed valid set of values a k a_k a k and b k b_k b k , there exists a strategy that attains ξ = ∑ k = 0 m − 1 min ( a k , b k ) \xi= \sum_{k=0}^{m-1} \min(a_k,b_k) ξ = ∑ k = 0 m − 1 min ( a k , b k ) , and any such strategy must have ξ k = min ( a k , b k ) \xi_k = \min(a_k,b_k) ξ k = min ( a k , b k ) for every k ∈ [ m ] k \in[m] k ∈ [ m ] .
Proof. Alice and Bob iterate together through all k ∈ [ m ] k \in[m] k ∈ [ m ] , keeping track of which inputs (in sorted order) they have allocated. They each allocate the first min ( a k , b k ) \min(a_k,b_k) min ( a k , b k ) of their remaining inputs to output k k k , which by induction will always be the same min ( a k , b k ) \min(a_k,b_k) min ( a k , b k ) inputs. They then allocate the last a k − min ( a k , b k ) a_k - \min(a_k,b_k) a k − min ( a k , b k ) and b k − min ( a k , b k ) b_k - \min(a_k,b_k) b k − min ( a k , b k ) , respectively, of their remaining inputs to output k k k ; at most one of these quantities will be nonzero. Hence, ξ k = min ( a k , b k ) \xi_k = \min(a_k,b_k) ξ k = min ( a k , b k ) .
Alice and Bob then agree on the first ∑ k = 0 m − 1 min ( a k , b k ) \sum_{k=0}^{m-1} \min(a_k,b_k) ∑ k = 0 m − 1 min ( a k , b k ) inputs, so ξ = ∑ k = 0 m − 1 min ( a k , b k ) \xi= \sum_{k=0}^{m-1} \min(a_k,b_k) ξ = ∑ k = 0 m − 1 min ( a k , b k ) .
Furthermore, Alice allocates exactly min ( a k , b k ) + a k − min ( a k , b k ) = a k \min(a_k,b_k) + a_k - \min(a_k,b_k) = a_k min ( a k , b k ) + a k − min ( a k , b k ) = a k inputs to each output k k k , and likewise Bob allocates exactly min ( a k , b k ) + b k − min ( a k , b k ) = b k \min(a_k,b_k) + b_k - \min(a_k,b_k) = b_k min ( a k , b k ) + b k − min ( a k , b k ) = b k inputs to each output k k k , as desired. Since ∑ k = 0 m − 1 a k = ∑ k = 0 m − 1 b k = n \sum_{k=0}^{m-1} a_k = \sum_{k=0}^{m-1} b_k = n ∑ k = 0 m − 1 a k = ∑ k = 0 m − 1 b k = n and the players’ pointers each meet in the middle, our algorithm will only allocate each input exactly once, as desired.
By Lemma 3.1.1 , ξ k ≤ a k \xi_k \le a_k ξ k ≤ a k and ξ k ≤ b k \xi_k \le b_k ξ k ≤ b k , and thus ξ k ≤ min ( a k , b k ) \xi_k \le\min(a_k,b_k) ξ k ≤ min ( a k , b k ) , for each k k k . Therefore, any strategy with ξ k ≠ min ( a k , b k ) \xi_k \ne\min(a_k,b_k) ξ k = min ( a k , b k ) for any k ∈ [ m ] k \in[m] k ∈ [ m ] must have ξ < ∑ k = 0 m − 1 min ( a k , b k ) \xi< \sum_{k=0}^{m-1} \min(a_k,b_k) ξ < ∑ k = 0 m − 1 min ( a k , b k ) .
Since μ = ∑ k = 0 m − 1 a k b k \mu= \sum_{k=0}^{m-1} a_kb_k μ = ∑ k = 0 m − 1 a k b k is fully determined by the values of the a k a_k a k and b k b_k b k , any optimal strategy must maximize ξ \xi ξ given its values of a k a_k a k and b k b_k b k , and thus by Lemma 3.4.1 must satisfy ξ k = min ( a k , b k ) \xi_k = \min(a_k,b_k) ξ k = min ( a k , b k ) for every k ∈ [ m ] k \in[m] k ∈ [ m ] . The players must dump their remaining n − ξ n-\xi n − ξ inputs not accounted for by the ξ k \xi_k ξ k into disjoint subsets of [ m ] [m] [ m ] : if Alice and Bob both dumped an input into some output k k k , either ξ k \xi_k ξ k would increase or ξ k ≠ min ( a k , b k ) \xi_k \ne\min(a_k,b_k) ξ k = min ( a k , b k ) . Then the increase in μ = ∑ k = 0 m − 1 a k b k \mu= \sum_{k=0}^{m-1} a_kb_k μ = ∑ k = 0 m − 1 a k b k that Alice or Bob incurs by dumping one of their inputs into some output k k k must be exactly ξ k \xi_k ξ k , so they minimize μ \mu μ by dumping their respective remaining n − ξ n-\xi n − ξ inputs into the outputs (hereafter, u u u and v v v ) with the least and second least values of ξ k \xi_k ξ k .
Assuming now that m ≥ 3 m \ge3 m ≥ 3 , we have ξ u ≤ ξ v ≤ ξ k \xi_u \le\xi_v \le\xi_k ξ u ≤ ξ v ≤ ξ k for all k ∈ { u , v } k \in\{u,v\} k ∈ { u , v } , so
μ = ∑ k = 0 m − 1 ξ k 2 − ξ u 2 − ξ v 2 + ξ u ( ξ u + n − ξ ) + ξ v ( ξ v + n − ξ ) = ∑ k = 0 m − 1 ξ k 2 + ( n − ξ ) ( ξ u + ξ v ) . \mu= \sum_{k=0}^{m-1} \xi_k^2 - \xi_u^2 - \xi_v^2 + \xi_u(\xi_u+n-\xi) + \xi_v(\xi_v+n-\xi) = \sum_{k=0}^{m-1} \xi_k^2 + (n-\xi)(\xi_u+\xi_v). μ = k = 0 ∑ m − 1 ξ k 2 − ξ u 2 − ξ v 2 + ξ u ( ξ u + n − ξ ) + ξ v ( ξ v + n − ξ ) = k = 0 ∑ m − 1 ξ k 2 + ( n − ξ ) ( ξ u + ξ v ) .
Then for any fixed value of ξ u + ξ v \xi_u+\xi_v ξ u + ξ v , we can minimize μ \mu μ by separately minimizing ξ u 2 + ξ v 2 \xi_u^2+\xi_v^2 ξ u 2 + ξ v 2 (subject to the fixed value of ξ u + ξ v \xi_u+\xi_v ξ u + ξ v ) and ∑ k ∉ { u , v } ξ k 2 \sum_{k\notin\{u,v\}}\xi_k^2 ∑ k ∈ / { u , v } ξ k 2 subject to ∑ k ∉ { u , v } ξ k = ξ − ( ξ u + ξ v ) \sum_{k\notin\{u,v\}}\xi_k = \xi- (\xi_u+\xi_v) ∑ k ∈ / { u , v } ξ k = ξ − ( ξ u + ξ v ) .
By Lemma 3.1.3 (with m = 2 m=2 m = 2 and the fixed sum as ξ u + ξ v \xi_u+\xi_v ξ u + ξ v ), ξ u 2 + ξ v 2 \xi_u^2+\xi_v^2 ξ u 2 + ξ v 2 is minimized when ξ u = ⌊ ξ u + ξ v 2 ⌋ \xi_u = \left\lfloor\frac{\xi_u+\xi_v}{2} \right\rfloor ξ u = ⌊ 2 ξ u + ξ v ⌋ , and ξ v = ⌈ ξ u + ξ v 2 ⌉ \xi_v = \left\lceil\frac{\xi_u+\xi_v}{2} \right\rceil ξ v = ⌈ 2 ξ u + ξ v ⌉ if ξ u + ξ v \xi_u+\xi_v ξ u + ξ v is even and ξ v = ⌊ ξ u + ξ v 2 ⌋ + 1 \xi_v = \left\lfloor\frac{\xi_u+\xi_v}{2} \right\rfloor+ 1 ξ v = ⌊ 2 ξ u + ξ v ⌋ + 1 otherwise.
Similarly, by Lemma 3.1.3 on the remaining m − 2 m-2 m − 2 terms (with the fixed sum as ξ − ( ξ u + ξ v ) \xi-(\xi_u+\xi_v) ξ − ( ξ u + ξ v ) ), ∑ k ∉ { u , v } ξ k 2 \sum_{k\notin\{u,v\}}\xi_k^2 ∑ k ∈ / { u , v } ξ k 2 is minimized when ξ k = ⌊ ξ − ( ξ u + ξ v ) m − 2 ⌋ + 1 \xi_k = \left\lfloor\frac{\xi-(\xi_u+\xi_v)}{m-2} \right\rfloor+ 1 ξ k = ⌊ m − 2 ξ − ( ξ u + ξ v ) ⌋ + 1 for exactly ( ξ − ( ξ u + ξ v ) ) m o d ( m − 2 ) (\xi-(\xi_u+\xi_v)) \bmod(m-2) ( ξ − ( ξ u + ξ v )) mod ( m − 2 ) values of k k k and ξ k = ⌊ ξ − ( ξ u + ξ v ) m − 2 ⌋ \xi_k = \left\lfloor\frac{\xi-(\xi_u+\xi_v)}{m-2}\right\rfloor ξ k = ⌊ m − 2 ξ − ( ξ u + ξ v ) ⌋ for the rest.
Given values for ξ \xi ξ and ξ u + ξ v \xi_u+\xi_v ξ u + ξ v , we then know the optimal strategy.
Since ξ u ≤ ξ k \xi_u \leq\xi_k ξ u ≤ ξ k for all k ∈ [ m ] k \in[m] k ∈ [ m ] , m ξ u = ∑ k = 0 m − 1 ξ u ≤ ∑ k = 0 m − 1 ξ k = ξ m\xi_u = \sum_{k=0}^{m-1}\xi_u \leq\sum_{k=0}^{m-1}\xi_k = \xi m ξ u = ∑ k = 0 m − 1 ξ u ≤ ∑ k = 0 m − 1 ξ k = ξ and thus ξ u ≤ ξ m \xi_u \leq\frac{\xi}{m} ξ u ≤ m ξ . Also, in order to be optimal, we must have ξ v ≤ ⌊ ξ u + ξ v 2 ⌋ + 1 ≤ ξ u + 1 \xi_v \leq\left\lfloor\frac{\xi_u+\xi_v}{2}\right\rfloor+ 1 \leq\xi_u+1 ξ v ≤ ⌊ 2 ξ u + ξ v ⌋ + 1 ≤ ξ u + 1 , so ξ u + ξ v ≤ 2 ξ u + 1 ≤ 2 ξ m + 1 \xi_u+\xi_v \leq2\xi_u+1 \leq2\frac{\xi}{m}+1 ξ u + ξ v ≤ 2 ξ u + 1 ≤ 2 m ξ + 1 .
Therefore, for any ( n , m ) (n,m) ( n , m ) , the number of strategies that might be optima at any p p p is at most
∑ ξ = 0 n ( 2 ξ m + 2 ) = 2 m ( ∑ ξ = 0 n ξ ) + 2 ( n + 1 ) = 2 m ⋅ n ( n + 1 ) 2 + 2 ( n + 1 ) = ( n m + 2 ) ( n + 1 ) . \sum_{\xi=0}^{n}\left(2\frac{\xi}{m}+2\right)=\frac{2}{m}\left(\sum_{\xi=0}^{n}\xi\right)+2(n+1)=\frac{2}{m}\cdot\frac{n(n+1)}{2}+2(n+1)=\left(\frac{n}{m}+2\right)(n+1). ξ = 0 ∑ n ( 2 m ξ + 2 ) = m 2 ξ = 0 ∑ n ξ + 2 ( n + 1 ) = m 2 ⋅ 2 n ( n + 1 ) + 2 ( n + 1 ) = ( m n + 2 ) ( n + 1 ) .
We can then iterate through these strategies in time O ( n 2 m ) O\left(\frac{n^2}{m}\right) O ( m n 2 ) , and computing each of these strategies’ values of ν \nu ν requires O ( 1 ) O(1) O ( 1 ) arithmetic operations, so finding the optimal classical strategy at a given value of p p p is computationally efficient for m ≥ 3 m \geq3 m ≥ 3 .
Computing the value of p p p at which each such strategy’s value intersects (i.e., equals) that of the synchronous strategy from § 3.2 also uses O ( 1 ) O(1) O ( 1 ) arithmetic operations, so we can find the threshold for p p p at which the synchronous strategy becomes optimal in O ( n 2 m ) O\left(\frac{n^2}{m}\right) O ( m n 2 ) time as well.
Quantum Strategies
We now consider strategies where Alice and Bob are allowed to share an arbitrarily large finite-dimensional entangled quantum state before receiving inputs; they still may not communicate once they receive their inputs. We use the definition found in definition 4.1 of [16 ] , where a quantum strategy consists of a bipartite pure state shared between Alice and Bob, who each apply a different complete set of projective measurements (PVMs) for each input.
In this section, we will present a synchronous quantum strategy for our coloring game. We will refine this strategy to a more elegant form that highlights that the entanglement seems to be used to account for the fact that m m m fails to divide n n n (which precludes Alice and Bob from classically assigning the same number of inputs to each output). We will then show that strategy is optimal across quantum synchronous strategies, as well as across all quantum strategies when p p p (the probability that the players receive equal inputs) is at least 2 n − m ( m + 2 ) n − 2 m \frac{2n-m}{(m+2)n-2m} ( m + 2 ) n − 2 m 2 n − m .
An Optimal Synchronous Quantum Strategy
Recall the definition of a synchronous strategy: Alice and Bob must always give the same output when given the same input. Note that this restriction does not imply that they have a fixed output for each input, only that their outputs are equal if their inputs were equal. Let D ∈ C m × m D \in\mathbb{C}^{m\times m} D ∈ C m × m be the diagonal matrix with D k k = ω n k : = e 2 π i k / n D_{kk}=\omega_n^k:=e^{2\pi i k/n} D k k = ω n k := e 2 π ik / n for all k ∈ [ m ] k \in[m] k ∈ [ m ] .
Let F F F be the m × m m\times m m × m Fourier matrix: i.e., F k l = ω m k l m F_{kl}=\frac{\omega_m^{kl}}{\sqrt{m}} F k l = m ω m k l where ω m : = e 2 π i / m \omega_m:=e^{2\pi i/m} ω m := e 2 π i / m .
Alice and Bob initially have one half each of the m m m -dimensional Bell state 1 m ∑ k = 0 m − 1 ∣ k ⟩ ∣ k ⟩ \frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}|k\rangle|k\rangle m 1 ∑ k = 0 m − 1 ∣ k ⟩ ∣ k ⟩ .
Alice applies the unitary operator F ∗ D − x F^{*}D^{-x} F ∗ D − x (where U ∗ U^{*} U ∗ denotes the entrywise conjugate of U U U ) upon receiving her input x ∈ [ n ] x\in[n] x ∈ [ n ] , and Bob applies F D y FD^{y} F D y upon receiving input y ∈ [ n ] y\in[n] y ∈ [ n ] , after which both players measure in the standard basis and output their measurement result.
The state after they apply their respective operators is
( ( F ∗ D − x ) ⊗ ( F D y ) ) ( 1 m ∑ k = 0 m − 1 ∣ k ⟩ ∣ k ⟩ ) = 1 m ∑ k = 0 m − 1 ( ( F ∗ D − x ∣ k ⟩ ) ⊗ ( F D y ∣ k ⟩ ) ) = 1 m ∑ k = 0 m − 1 ( ( F ∗ ( D k k ) − x ∣ k ⟩ ) ⊗ ( F ( D k k ) y ∣ k ⟩ ) ) = 1 m ∑ k = 0 m − 1 ( ( F ∗ ( ω n k ) − x ∣ k ⟩ ) ⊗ ( F ( ω n k ) y ∣ k ⟩ ) ) = 1 m ∑ k = 0 m − 1 ( ( F ∗ ω n − k x ∣ k ⟩ ) ⊗ ( F ω n k y ∣ k ⟩ ) ) = 1 m ∑ k = 0 m − 1 ω n k y − k x ( ( F ∗ ∣ k ⟩ ) ⊗ ( F ∣ k ⟩ ) ) . \begin{aligned}
&\left((F^{*}D^{-x})\otimes(FD^{y})\right)\left(\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}|k\rangle|k\rangle\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\left((F^{*}D^{-x}|k\rangle)\otimes(FD^{y}|k\rangle)\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\left((F^{*}(D_{kk})^{-x}|k\rangle)\otimes(F(D_{kk})^{y}|k\rangle)\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\left((F^{*}(\omega_n^k)^{-x}|k\rangle)\otimes(F(\omega_n^k)^y|k\rangle)\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\left((F^{*}\omega_n^{-kx}|k\rangle)\otimes(F\omega_n^{ky}|k\rangle)\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\omega_n^{ky-kx}\left((F^{*}|k\rangle)\otimes(F|k\rangle)\right).
\end{aligned} ( ( F ∗ D − x ) ⊗ ( F D y ) ) ( m 1 k = 0 ∑ m − 1 ∣ k ⟩ ∣ k ⟩ ) = m 1 k = 0 ∑ m − 1 ( ( F ∗ D − x ∣ k ⟩) ⊗ ( F D y ∣ k ⟩) ) = m 1 k = 0 ∑ m − 1 ( ( F ∗ ( D k k ) − x ∣ k ⟩) ⊗ ( F ( D k k ) y ∣ k ⟩) ) = m 1 k = 0 ∑ m − 1 ( ( F ∗ ( ω n k ) − x ∣ k ⟩) ⊗ ( F ( ω n k ) y ∣ k ⟩) ) = m 1 k = 0 ∑ m − 1 ( ( F ∗ ω n − k x ∣ k ⟩) ⊗ ( F ω n k y ∣ k ⟩) ) = m 1 k = 0 ∑ m − 1 ω n k y − k x ( ( F ∗ ∣ k ⟩) ⊗ ( F ∣ k ⟩) ) .
The amplitude of any basis state ∣ j ⟩ ∣ j ⟩ |j\rangle|j\rangle ∣ j ⟩ ∣ j ⟩ with j ∈ [ m ] j\in[m] j ∈ [ m ] is then
1 m ∑ k = 0 m − 1 ω n k y − k x ( ( F ∗ ∣ k ⟩ ) j ) ( ( F ∣ k ⟩ ) j ) = 1 m ∑ k = 0 m − 1 ω n k y − k x ( ( F ∗ ) j k ) ( ( F ) j k ) = 1 m ∑ k = 0 m − 1 ω n k y − k x ( ω m j k m ) ∗ ( ω m j k m ) = 1 m ∑ k = 0 m − 1 ω n k y − k x ( ω m − j k m ) ( ω m j k m ) = m − 3 / 2 ∑ k = 0 m − 1 ω n k y − k x ω m − j k + j k = m − 3 / 2 ∑ k = 0 m − 1 ω n k y − k x ω m 0 = m − 3 / 2 ∑ k = 0 m − 1 ω n k ( y − x ) . \begin{aligned}
&\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\omega_n^{ky-kx}\left((F^{*}|k\rangle)_j\right)\left((F|k\rangle)_j\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\omega_n^{ky-kx}\left((F^{*})_{jk}\right)\left((F)_{jk}\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\omega_n^{ky-kx}\left(\frac{\omega_m^{jk}}{\sqrt{m}}\right)^{*}\left(\frac{\omega_m^{jk}}{\sqrt{m}}\right)\\
&=\frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\omega_n^{ky-kx}\left(\frac{\omega_m^{-jk}}{\sqrt{m}}\right)\left(\frac{\omega_m^{jk}}{\sqrt{m}}\right)\\
&=m^{-3/2}\sum_{k=0}^{m-1}\omega_n^{ky-kx}\omega_m^{-jk+jk}\\
&=m^{-3/2}\sum_{k=0}^{m-1}\omega_n^{ky-kx}\omega_m^0\\
&=m^{-3/2}\sum_{k=0}^{m-1}\omega_n^{k(y-x)}.
\end{aligned} m 1 k = 0 ∑ m − 1 ω n k y − k x ( ( F ∗ ∣ k ⟩ ) j ) ( ( F ∣ k ⟩ ) j ) = m 1 k = 0 ∑ m − 1 ω n k y − k x ( ( F ∗ ) j k ) ( ( F ) j k ) = m 1 k = 0 ∑ m − 1 ω n k y − k x ( m ω m j k ) ∗ ( m ω m j k ) = m 1 k = 0 ∑ m − 1 ω n k y − k x ( m ω m − j k ) ( m ω m j k ) = m − 3/2 k = 0 ∑ m − 1 ω n k y − k x ω m − j k + j k = m − 3/2 k = 0 ∑ m − 1 ω n k y − k x ω m 0 = m − 3/2 k = 0 ∑ m − 1 ω n k ( y − x ) .
The probability of measuring each such state is then
∣ m − 3 / 2 ∑ k = 0 m − 1 ω n k ( y − x ) ∣ 2 = ( m − 3 / 2 ∑ k = 0 m − 1 ω n k ( y − x ) ) ∗ ( m − 3 / 2 ∑ l = 0 m − 1 ω n l ( y − x ) ) = m − 3 ( ∑ k = 0 m − 1 ( ω n k ( y − x ) ) ∗ ) ( ∑ l = 0 m − 1 ω n l ( y − x ) ) = m − 3 ( ∑ k = 0 m − 1 ω n − k ( y − x ) ) ( ∑ l = 0 m − 1 ω n l ( y − x ) ) = m − 3 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n − k ( y − x ) ω n l ( y − x ) = m − 3 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n ( l − k ) ( y − x ) . \begin{aligned}
\left|m^{-3/2}\sum_{k=0}^{m-1}\omega_n^{k(y-x)}\right|^2
&=\left(m^{-3/2}\sum_{k=0}^{m-1}\omega_n^{k(y-x)}\right)^*
\left(m^{-3/2}\sum_{l=0}^{m-1}\omega_n^{l(y-x)}\right)\\
&=m^{-3}\left(\sum_{k=0}^{m-1}\left(\omega_n^{k(y-x)}\right)^*\right)
\left(\sum_{l=0}^{m-1}\omega_n^{l(y-x)}\right)\\
&=m^{-3}\left(\sum_{k=0}^{m-1}\omega_n^{-k(y-x)}\right)
\left(\sum_{l=0}^{m-1}\omega_n^{l(y-x)}\right)\\
&=m^{-3}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{-k(y-x)}\omega_n^{l(y-x)}\\
&=m^{-3}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{(l-k)(y-x)}.
\end{aligned} m − 3/2 k = 0 ∑ m − 1 ω n k ( y − x ) 2 = ( m − 3/2 k = 0 ∑ m − 1 ω n k ( y − x ) ) ∗ ( m − 3/2 l = 0 ∑ m − 1 ω n l ( y − x ) ) = m − 3 ( k = 0 ∑ m − 1 ( ω n k ( y − x ) ) ∗ ) ( l = 0 ∑ m − 1 ω n l ( y − x ) ) = m − 3 ( k = 0 ∑ m − 1 ω n − k ( y − x ) ) ( l = 0 ∑ m − 1 ω n l ( y − x ) ) = m − 3 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n − k ( y − x ) ω n l ( y − x ) = m − 3 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n ( l − k ) ( y − x ) .
There is one such state for each j ∈ [ m ] j \in[m] j ∈ [ m ] , so the probability of measuring any one of them is
∑ j = 0 m − 1 m − 3 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n ( l − k ) ( y − x ) = m ⋅ m − 3 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n ( l − k ) ( y − x ) = m − 2 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n ( l − k ) ( y − x ) . \sum_{j=0}^{m-1}m^{-3}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{(l-k)(y-x)}
=m\cdot m^{-3}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{(l-k)(y-x)}
=m^{-2}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{(l-k)(y-x)}. j = 0 ∑ m − 1 m − 3 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n ( l − k ) ( y − x ) = m ⋅ m − 3 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n ( l − k ) ( y − x ) = m − 2 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n ( l − k ) ( y − x ) .
Theorem 4.1.1. The strategy defined in this section is synchronous (and hence ξ = n \xi= n ξ = n ).
Proof. When Alice and Bob receive equal inputs, y = x y=x y = x , so y − x = 0 y-x=0 y − x = 0 and this sum becomes
m − 2 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n ( l − k ) 0 = m − 2 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n 0 = m − 2 ∑ k = 0 m − 1 ∑ l = 0 m − 1 1 = m − 2 ∑ k = 0 m − 1 m = m − 2 ⋅ m 2 = 1. m^{-2}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{(l-k)0}
=m^{-2}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^0
=m^{-2}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}1
=m^{-2}\sum_{k=0}^{m-1}m
=m^{-2}\cdot m^2=1. m − 2 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n ( l − k ) 0 = m − 2 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n 0 = m − 2 k = 0 ∑ m − 1 l = 0 ∑ m − 1 1 = m − 2 k = 0 ∑ m − 1 m = m − 2 ⋅ m 2 = 1. Hence, Alice and Bob always win when x = y x=y x = y , so the strategy is synchronous, as desired. □
Recall that we defined μ \mu μ for a given strategy as the sum across all input pairs ( x , y ) ∈ [ n ] 2 (x,y) \in[n]^2 ( x , y ) ∈ [ n ] 2 of the probabilities that the players give equal outputs.
Theorem 4.1.2. The strategy defined in this section has μ = n 2 m \mu= \frac{n^2}{m} μ = m n 2 .
Proof. We sum the probability of measuring equal values across all x x x and y y y to get
μ = ∑ x = 0 n − 1 ∑ y = 0 n − 1 m − 2 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n ( l − k ) ( y − x ) = m − 2 ∑ x = 0 n − 1 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n − x ( l − k ) ∑ y = 0 n − 1 ω n y ( l − k ) . \mu=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}m^{-2}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{(l-k)(y-x)}
=m^{-2}\sum_{x=0}^{n-1}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{-x(l-k)}\sum_{y=0}^{n-1}\omega_n^{y(l-k)}. μ = x = 0 ∑ n − 1 y = 0 ∑ n − 1 m − 2 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n ( l − k ) ( y − x ) = m − 2 x = 0 ∑ n − 1 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n − x ( l − k ) y = 0 ∑ n − 1 ω n y ( l − k ) .
If l = k l=k l = k , the terms in the innermost sum fail to interfere:
ω n − x ( l − k ) ∑ y = 0 n − 1 ω n y ( l − k ) = ω n − x ⋅ 0 ∑ y = 0 n − 1 ω n y ⋅ 0 = ω n 0 ∑ y = 0 n − 1 ω n 0 = 1 ∑ y = 0 n − 1 1 = 1 ⋅ n = n . \omega_n^{-x(l-k)}\sum_{y=0}^{n-1}\omega_n^{y(l-k)}
=\omega_n^{-x\cdot0}\sum_{y=0}^{n-1}\omega_n^{y\cdot0}
=\omega_n^0\sum_{y=0}^{n-1}\omega_n^0
=1\sum_{y=0}^{n-1}1
=1\cdot n=n. ω n − x ( l − k ) y = 0 ∑ n − 1 ω n y ( l − k ) = ω n − x ⋅ 0 y = 0 ∑ n − 1 ω n y ⋅ 0 = ω n 0 y = 0 ∑ n − 1 ω n 0 = 1 y = 0 ∑ n − 1 1 = 1 ⋅ n = n .
Otherwise, l ≠ k l \ne k l = k (mod n n n ) (since 0 ≤ l , k < m 0 \le l,k < m 0 ≤ l , k < m and thus ∣ l − k ∣ < m ≤ n |l-k| < m \le n ∣ l − k ∣ < m ≤ n ), so ω n l − k ≠ 1 \omega_n^{l-k} \ne1 ω n l − k = 1 and the terms will interfere. By the standard formula for the sum of a finite geometric series,
∑ y = 0 n − 1 ω n y ( l − k ) = ∑ y = 0 n − 1 ( ω n l − k ) y = 1 − ( ω n l − k ) n 1 − ω n l − k = 1 − ( ω n n ) l − k 1 − ω n l − k = 1 − 1 l − k 1 − ω n l − k = 1 − 1 1 − ω n l − k = 0. \sum_{y=0}^{n-1}\omega_n^{y(l-k)}=\sum_{y=0}^{n-1}(\omega_n^{l-k})^y=\frac{1-(\omega_n^{l-k})^n}{1-\omega_n^{l-k}}=\frac{1-(\omega_n^n)^{l-k}}{1-\omega_n^{l-k}}=\frac{1-1^{l-k}}{1-\omega_n^{l-k}}=\frac{1-1}{1-\omega_n^{l-k}}=0. y = 0 ∑ n − 1 ω n y ( l − k ) = y = 0 ∑ n − 1 ( ω n l − k ) y = 1 − ω n l − k 1 − ( ω n l − k ) n = 1 − ω n l − k 1 − ( ω n n ) l − k = 1 − ω n l − k 1 − 1 l − k = 1 − ω n l − k 1 − 1 = 0.
Note that the denominator is 0 (and hence the calculation fails) exactly when ω n l − k = 1 \omega_n^{l-k}=1 ω n l − k = 1 .
Hence, for each k k k exactly one l l l (i.e., l = k l=k l = k ) yields a sum of n n n and the others yield 0, so
∑ l = 0 m − 1 ω n − x ( l − k ) ∑ y = 0 n − 1 ω n y ( l − k ) = 1 ⋅ n + ( m − 1 ) ⋅ 0 = n \sum_{l=0}^{m-1}\omega_n^{-x(l-k)}\sum_{y=0}^{n-1}\omega_n^{y(l-k)}=1\cdot n+(m-1)\cdot0=n l = 0 ∑ m − 1 ω n − x ( l − k ) y = 0 ∑ n − 1 ω n y ( l − k ) = 1 ⋅ n + ( m − 1 ) ⋅ 0 = n
for all k ∈ [ m ] k \in[m] k ∈ [ m ] and all x ∈ [ n ] x \in[n] x ∈ [ n ] , and hence, as desired,
μ = m − 2 ∑ x = 0 n − 1 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n − x ( l − k ) ∑ y = 0 n − 1 ω n y ( l − k ) = m − 2 ∑ x = 0 n − 1 ∑ k = 0 m − 1 n = m − 2 ⋅ n ⋅ m ⋅ n = n 2 m . \mu=m^{-2}\sum_{x=0}^{n-1}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{-x(l-k)}\sum_{y=0}^{n-1}\omega_n^{y(l-k)}=m^{-2}\sum_{x=0}^{n-1}\sum_{k=0}^{m-1}n=m^{-2}\cdot n\cdot m\cdot n=\frac{n^2}{m}. μ = m − 2 x = 0 ∑ n − 1 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n − x ( l − k ) y = 0 ∑ n − 1 ω n y ( l − k ) = m − 2 x = 0 ∑ n − 1 k = 0 ∑ m − 1 n = m − 2 ⋅ n ⋅ m ⋅ n = m n 2 .
Recall that we defined p p p as the probability that the players receive equal inputs.
Theorem 4.1.3. The value of the strategy defined in this section is p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right) p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) .
Proof. Recall that we can write the strategy’s value in terms of ξ \xi ξ and μ \mu μ :
ω = 1 − p + ( p n + 1 − p n ( n − 1 ) ) ξ − 1 − p n ( n − 1 ) μ . \omega=1-p+\left(\frac{p}{n}+\frac{1-p}{n(n-1)}\right)\xi-\frac{1-p}{n(n-1)}\mu. ω = 1 − p + ( n p + n ( n − 1 ) 1 − p ) ξ − n ( n − 1 ) 1 − p μ . By Theorem 4.1.1 , ξ = n \xi=n ξ = n , and by Theorem 4.1.2 , μ = n 2 m \mu=\frac{n^2}{m} μ = m n 2 , giving
ω = 1 − p + ( p n + 1 − p n ( n − 1 ) ) n − 1 − p n ( n − 1 ) n 2 m \omega=1-p+\left(\frac{p}{n}+\frac{1-p}{n(n-1)}\right)n-\frac{1-p}{n(n-1)}\frac{n^2}{m} ω = 1 − p + ( n p + n ( n − 1 ) 1 − p ) n − n ( n − 1 ) 1 − p m n 2 = 1 − p + p + 1 − p n − 1 − ( 1 − p ) n ( n − 1 ) m =1-p+p+\frac{1-p}{n-1}-\frac{(1-p)n}{(n-1)m} = 1 − p + p + n − 1 1 − p − ( n − 1 ) m ( 1 − p ) n = p + ( 1 − p ) ( 1 + 1 n − 1 − n ( n − 1 ) m ) =p+(1-p)\left(1+\frac{1}{n-1}-\frac{n}{(n-1)m}\right) = p + ( 1 − p ) ( 1 + n − 1 1 − ( n − 1 ) m n ) = p + ( 1 − p ) ( 1 − n − m ( n − 1 ) m ) . =p+(1-p)\left(1-\frac{n-m}{(n-1)m}\right). = p + ( 1 − p ) ( 1 − ( n − 1 ) m n − m ) . :::`
Using Fewer Measurement Bases
When n ≥ 2 m n \ge2m n ≥ 2 m , we can attain the same success probability using a strategy that drastically reduces the number of distinct measurement operations Alice and Bob must be able to apply.
For any k ≥ 0 k \ge0 k ≥ 0 and n ≥ m n \ge m n ≥ m , consider the case of our game with n + k m n+km n + k m inputs and m m m outputs.
Theorem 4.2.1. The strategy where Alice and Bob each play the quantum strategy from § 4.1 for the ( n , m ) (n,m) ( n , m ) game on the first n n n inputs and assign the remaining k m km k m inputs evenly and identically across [ m ] [m] [ m ] has the same value as the strategy from § 4.1 for the ( n + k m , m ) (n+km,m) ( n + k m , m ) game.
Proof. This strategy is synchronous on the first n n n inputs (by Theorem 4.1.1 ) and the other k m km k m inputs (since the players assign inputs identically), and hence is synchronous overall.
When both players’ inputs are distinct and among the first n n n , their losing probability is n − m m ( n − 1 ) \frac{n-m}{m(n-1)} m ( n − 1 ) n − m , given by that of the quantum strategy, specifically the complement of the coefficient of 1 − p 1-p 1 − p in the quantum strategy’s value (as computed in Theorem 4.1.3 ).
If only one input is among the first n n n , the inputs must be distinct; for each measurement outcome, there are exactly k k k inputs (out of k m km k m ) the other player could receive that would result in equal outputs (and hence a loss), so the losing probability in this case is k k m = 1 m \frac{k}{km}=\frac{1}{m} k m k = m 1 .
Finally, for each of Alice’s k m km k m inputs not among the first n n n , there are k − 1 k-1 k − 1 inputs for Bob not among the first n n n or equal to Alice’s that result in equal outputs (and hence a loss).
Thus, when given different inputs, we lose with probability
n ( n − 1 ) n − m m ( n − 1 ) + 2 n k m 1 m + k m ( k − 1 ) ( n + k m ) ( n + k m − 1 ) = n ( n − m ) + m ( 2 n k + k m ( k − 1 ) ) m ( n + k m ) ( n + k m − 1 ) = n 2 − n m + 2 n k m + k m 2 ( k − 1 ) m ( n + k m ) ( n + k m − 1 ) = n 2 − n m + n k m + n k m + k 2 m 2 − k m 2 m ( n + k m ) ( n + k m − 1 ) = n 2 + n k m − n m + n k m + k 2 m 2 − k m 2 m ( n + k m ) ( n + k m − 1 ) = n ( n + k m − m ) + k m ( n + k m − m ) m ( n + k m ) ( n + k m − 1 ) = ( n + k m ) ( n + k m − m ) m ( n + k m ) ( n + k m − 1 ) = n + k m − m m ( n + k m − 1 ) , \begin{aligned}
\frac{n(n-1)\frac{n-m}{m(n-1)}+2nkm\frac{1}{m}+km(k-1)}{(n+km)(n+km-1)}
&=\frac{n(n-m)+m(2nk+km(k-1))}{m(n+km)(n+km-1)}\\
&=\frac{n^2-nm+2nkm+km^2(k-1)}{m(n+km)(n+km-1)}\\
&=\frac{n^2-nm+nkm+nkm+k^2m^2-km^2}{m(n+km)(n+km-1)}\\
&=\frac{n^2+nkm-nm+nkm+k^2m^2-km^2}{m(n+km)(n+km-1)}\\
&=\frac{n(n+km-m)+km(n+km-m)}{m(n+km)(n+km-1)}\\
&=\frac{(n+km)(n+km-m)}{m(n+km)(n+km-1)}\\
&=\frac{n+km-m}{m(n+km-1)},
\end{aligned} ( n + k m ) ( n + k m − 1 ) n ( n − 1 ) m ( n − 1 ) n − m + 2 nk m m 1 + k m ( k − 1 ) = m ( n + k m ) ( n + k m − 1 ) n ( n − m ) + m ( 2 nk + k m ( k − 1 )) = m ( n + k m ) ( n + k m − 1 ) n 2 − nm + 2 nk m + k m 2 ( k − 1 ) = m ( n + k m ) ( n + k m − 1 ) n 2 − nm + nk m + nk m + k 2 m 2 − k m 2 = m ( n + k m ) ( n + k m − 1 ) n 2 + nk m − nm + nk m + k 2 m 2 − k m 2 = m ( n + k m ) ( n + k m − 1 ) n ( n + k m − m ) + k m ( n + k m − m ) = m ( n + k m ) ( n + k m − 1 ) ( n + k m ) ( n + k m − m ) = m ( n + k m − 1 ) n + k m − m ,
exactly the losing probability of the optimal quantum strategy for ( n + k m , m ) (n+km,m) ( n + k m , m ) , as desired.
An immediate corollary is that it is never necessary to actually play the quantum strategy for any n ≥ 2 m n \ge2m n ≥ 2 m : we could instead just play the smaller quantum strategy on the first m + ( n m o d m ) m + (n \bmod m) m + ( n mod m ) inputs and the classical strategy on the rest. We refer to this as the “mod m m m ” strategy.
Quantum Synchronous Value
We now prove that the quantum value our strategy achieves is optimal across all synchronous strategies (i.e., ones where Alice and Bob give the same output when given the same input).
Remark. Synchronous strategies must always win this game on equal inputs. Thus, to prove that a synchronous strategy is optimal across all synchronous strategies for this game on the input distributions we consider, it suffices to prove that said strategy is optimal when inputs are always unequal: i.e., p = 0 p = 0 p = 0 .
Theorem 4.3.1. When the players always receive unequal inputs, no synchronous quantum strategy has a value greater than that of the strategy from § 4.1 , which is
1 − n − m m ( n − 1 ) . 1 - \frac{n-m}{m(n-1)}. 1 − m ( n − 1 ) n − m .
Proof. This relies on two theorems found in [13 ] . The first, Theorem 3.6, gives us that the synchronous quantum value of an m m m -coloring game on a graph G ( V , E ) G(V,E) G ( V , E ) with the input distribution being uniform over all unequal inputs is at most
1 − m ∣ E ∣ f G , q ( 1 m ) . 1 - \frac{m}{|E|} f_{G,q}\left(\frac{1}{m}\right). 1 − ∣ E ∣ m f G , q ( m 1 ) .
where f G , q f_{G,q} f G , q is the quantum graph correlation function [13 ] . Theorem 3.8 of [13 ] gives us that f K n , q ( t ) = n t ( n t − 1 ) f_{K_n,q}(t) = nt(nt-1) f K n , q ( t ) = n t ( n t − 1 ) for all n ≥ 5 n \ge5 n ≥ 5 , as long as
n − n 2 − 4 n 2 n ≤ t ≤ n + n 2 − 4 n 2 n . \frac{n-\sqrt{n^2-4n}}{2n} \le t \le\frac{n+\sqrt{n^2-4n}}{2n}. 2 n n − n 2 − 4 n ≤ t ≤ 2 n n + n 2 − 4 n .
Plugging in our value of 1 m \frac{1}{m} m 1 , we find that, when the above constraints are met, the quantum synchronous value of the graph coloring game with m m m colors played on K n K_n K n with the input distribution being uniform over all unequal inputs is at most
1 − m n 2 − n ( n m ( n m − 1 ) ) 1-\frac{m}{n^2-n}\left(\frac{n}{m}\left(\frac{n}{m}-1\right)\right) 1 − n 2 − n m ( m n ( m n − 1 ) )
which simplifies to
1 − 1 n − 1 ( n m − 1 ) = 1 − n − m m ( n − 1 ) 1-\frac{1}{n-1}\left(\frac{n}{m}-1\right)=1-\frac{n-m}{m(n-1)} 1 − n − 1 1 ( m n − 1 ) = 1 − m ( n − 1 ) n − m
exactly the value of our quantum strategy. Thus, our synchronous quantum strategy is optimal whenever
n ≥ 5 , n − n 2 − 4 n 2 n ≤ 1 m ≤ n + n 2 − 4 n 2 n n \ge5,\ \frac{n-\sqrt{n^2-4n}}{2n} \le\frac{1}{m} \le\frac{n+\sqrt{n^2-4n}}{2n} n ≥ 5 , 2 n n − n 2 − 4 n ≤ m 1 ≤ 2 n n + n 2 − 4 n
But we can do better.
Considering only interesting cases (n > m ≥ 2 n > m \ge2 n > m ≥ 2 ), the n ≥ 5 n \ge5 n ≥ 5 requirement leaves us with three parameter pairs where our strategy may not be optimal, which we write in the form ( n , m ) (n,m) ( n , m ) : ( 3 , 2 ) , ( 4 , 2 ) , ( 4 , 3 ) (3,2),(4,2),(4,3) ( 3 , 2 ) , ( 4 , 2 ) , ( 4 , 3 ) . The second condition is more problematic. Since m ≥ 2 m \ge2 m ≥ 2 , we know that
1 m ≤ 1 2 < n + n 2 − 4 n 2 n \frac{1}{m} \le\frac{1}{2} < \frac{n+\sqrt{n^2-4n}}{2n} m 1 ≤ 2 1 < 2 n n + n 2 − 4 n
A simple algebraic proof gives that, for all m ≤ n − 2 m \le n-2 m ≤ n − 2 , we have
n − n 2 − 4 n 2 n < 1 m . \frac{n-\sqrt{n^2-4n}}{2n} < \frac{1}{m}. 2 n n − n 2 − 4 n < m 1 .
n − n 2 − 4 n 2 n ⋅ n + n 2 − 4 n n + n 2 − 4 n = n 2 − n 2 + 4 n 2 n ( n + n 2 − 4 n ) = 1 1 2 ( n + n 2 − 4 n ) \begin{aligned}
\frac{n-\sqrt{n^2-4n}}{2n}\cdot\frac{n+\sqrt{n^2-4n}}{n+\sqrt{n^2-4n}}
&=\frac{n^2-n^2+4n}{2n\left(n+\sqrt{n^2-4n}\right)}\\
&=\frac{1}{\frac{1}{2}\left(n+\sqrt{n^2-4n}\right)}
\end{aligned} 2 n n − n 2 − 4 n ⋅ n + n 2 − 4 n n + n 2 − 4 n = 2 n ( n + n 2 − 4 n ) n 2 − n 2 + 4 n = 2 1 ( n + n 2 − 4 n ) 1
And so it suffices to prove that
1 2 ( n + n 2 − 4 n ) > n − 2 \frac{1}{2}\left(n+\sqrt{n^2-4n}\right)>n-2 2 1 ( n + n 2 − 4 n ) > n − 2
or, more simply that
n 2 − 4 n > 2 n − 4 − n = n − 4 \sqrt{n^2-4n}>2n-4-n=n-4 n 2 − 4 n > 2 n − 4 − n = n − 4
From the other restriction we have that n > 4 n > 4 n > 4 , so 4 n > 16 4n > 16 4 n > 16 and thus
− 4 n > − 8 n + 16 -4n>-8n+16 − 4 n > − 8 n + 16
so
n 2 − 4 n > n 2 − 8 n + 16 = ( n − 4 ) 2 n^2-4n>n^2-8n+16=(n-4)^2 n 2 − 4 n > n 2 − 8 n + 16 = ( n − 4 ) 2
We can simply take the square root of both sides to find that
n 2 − 4 n > n − 4 \sqrt{n^2-4n}>n-4 n 2 − 4 n > n − 4
Thus, in addition to being unsure of optimality for parameters ( 3 , 2 ) (3,2) ( 3 , 2 ) , ( 4 , 2 ) (4,2) ( 4 , 2 ) , and ( 4 , 3 ) (4,3) ( 4 , 3 ) , we also are unsure of the optimality of our strategy for all pairs of parameters ( n , n − 1 ) (n,n-1) ( n , n − 1 ) . Fortunately, the result from § 4.2 (specifically the mod m m m strategy) may be used to prove optimality in these cases as well. Suppose for the sake of contradiction that there existed some synchronous quantum strategy with value greater than
1 − z − ( z − 1 ) ( z − 1 ) ( z − 1 ) 1-\frac{z-(z-1)}{(z-1)(z-1)} 1 − ( z − 1 ) ( z − 1 ) z − ( z − 1 )
for some parameter pair ( n = z , m = z − 1 ) (n=z,m=z-1) ( n = z , m = z − 1 ) . Note that, since the only interesting cases are when m ≥ 2 m \ge2 m ≥ 2 , we can assume z ≥ 3 z \ge3 z ≥ 3 . By the mod m m m strategy, we know that, when playing the game with parameter pair ( n ′ = 2 z − 1 , m ′ = z − 1 ) (n'=2z-1,m'=z-1) ( n ′ = 2 z − 1 , m ′ = z − 1 ) , the optimal success probability can be achieved by simply playing our quantum strategy on the first z z z inputs and the classical strategy on the other z − 1 z-1 z − 1 inputs. If we instead played this superior quantum strategy on the first z z z inputs and the classical strategy on the other z − 1 z-1 z − 1 inputs, then we would achieve a strictly higher success probability. This follows from the proof of Theorem 4.2.1 : We have no guarantees on what outputs the hypothetical quantum strategy for ( z , z − 1 ) (z,z-1) ( z , z − 1 ) will give, but since the number of inputs assigned to each output in the classical portion is 1, we will still have the exact same average failure rate as the scenario in Theorem 4.2.1 when one input is in the classically handled inputs ( z (z ( z to 2 z − 2 ) 2z-2) 2 z − 2 ) and one is in the quantum-handled inputs ( 0 (0 ( 0 to z − 1 ) z-1) z − 1 ) . The failure rate in the both-inputs-handled-classically case should also be unchanged from the scenario in Theorem 4.2.1 , so the only change is that, when both inputs are in the quantum-handled range, we have a better success probability. Thus, if the ( n = z , m = z − 1 ) (n=z,m=z-1) ( n = z , m = z − 1 ) case had a synchronous quantum strategy with value greater than
1 − n − m m ( n − 1 ) = 1 − z − ( z − 1 ) ( z − 1 ) ( z − 1 ) 1-\frac{n-m}{m(n-1)}=1-\frac{z-(z-1)}{(z-1)(z-1)} 1 − m ( n − 1 ) n − m = 1 − ( z − 1 ) ( z − 1 ) z − ( z − 1 )
then the ( n ′ = 2 z − 1 , m ′ = z − 1 ) (n'=2z-1,m'=z-1) ( n ′ = 2 z − 1 , m ′ = z − 1 ) case would have a value greater than
1 − n ′ − m ′ m ′ ( n ′ − 1 ) = 1 − 2 z − 1 − ( z − 1 ) ( z − 1 ) ( 2 z − 2 ) 1-\frac{n'-m'}{m'(n'-1)}=1-\frac{2z-1-(z-1)}{(z-1)(2z-2)} 1 − m ′ ( n ′ − 1 ) n ′ − m ′ = 1 − ( z − 1 ) ( 2 z − 2 ) 2 z − 1 − ( z − 1 )
which we know reaches the upper bound, and thus we have a contradiction. In particular, this covers ( 3 , 2 ) (3,2) ( 3 , 2 ) and ( 4 , 3 ) (4,3) ( 4 , 3 ) , since better strategies for ( 3 , 2 ) (3,2) ( 3 , 2 ) or ( 4 , 3 ) (4,3) ( 4 , 3 ) would imply better strategies for ( 5 , 2 ) (5,2) ( 5 , 2 ) and ( 7 , 3 ) (7,3) ( 7 , 3 ) respectively, which both violate our upper bound and thus create contradictions. For ( 4 , 2 ) (4,2) ( 4 , 2 ) , we can again invoke Theorem 4.2.1 to observe that, for ( 6 , 2 ) (6,2) ( 6 , 2 ) , playing the ( 4 , 2 ) (4,2) ( 4 , 2 ) quantum strategy on the first 4 inputs and playing the classical strategy on the remaining 2 inputs is optimal, so by the same argument as above a better synchronous quantum strategy for ( 4 , 2 ) (4,2) ( 4 , 2 ) implies a better synchronous quantum strategy for ( 6 , 2 ) (6,2) ( 6 , 2 ) , creating a contradiction.
Thus, our synchronous quantum value of
1 − n − m m ( n − 1 ) 1-\frac{n-m}{m(n-1)} 1 − m ( n − 1 ) n − m
is optimal for all n > m ≥ 2 n>m \ge2 n > m ≥ 2 .
Remark. Note that Theorem 4.3.1 implies the strategy laid out in § 4.1 is optimal across all quantum synchronous strategies.
Theorem 4.3.2. The quantum synchronous value of this game is p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right) p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) .
Proof. Since synchronous strategies can only lose this game on unequal inputs, this follows directly from Theorem 4.3.1 providing the upper bound and Theorem 4.1.3 meeting that bound.
Quantum Value
We now prove that the synchronous strategy detailed in § 4.1 is optimal when the probability p p p that the players receive equal inputs is sufficiently large: i.e., p ≥ 2 n − m ( m + 2 ) n − 2 m p \ge\frac{2n-m}{(m+2)n-2m} p ≥ ( m + 2 ) n − 2 m 2 n − m .
Recall the following definitions: c x y c_{xy} c x y is the probability that Alice’s output ( a ) (a) ( a ) is equal to Bob’s output ( b ) (b) ( b ) given that Alice received input x x x and Bob received input y y y . We also defined
ξ : = ∑ x = 0 n − 1 c x x \xi:= \sum_{x=0}^{n-1} c_{xx} ξ := x = 0 ∑ n − 1 c xx
and
μ : = ∑ x = 0 n − 1 ∑ y = 0 n − 1 c x y . \mu:= \sum_{x=0}^{n-1}\sum_{y=0}^{n-1} c_{xy}. μ := x = 0 ∑ n − 1 y = 0 ∑ n − 1 c x y .
Finally, recall that our input distribution π \pi π was defined as follows: letting p : = P [ x = y ] p := \mathbb{P}[x=y] p := P [ x = y ] , π ( x , x ) = p n \pi(x,x) = \frac{p}{n} π ( x , x ) = n p for each x ∈ [ n ] x \in[n] x ∈ [ n ] and π ( x , y ) = 1 − p n ( n − 1 ) \pi(x,y) = \frac{1-p}{n(n-1)} π ( x , y ) = n ( n − 1 ) 1 − p whenever x ≠ y x \ne y x = y . Note that we only care to study p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , since p = 0 p=0 p = 0 and p = 1 p=1 p = 1 both have trivial strategies that always win.
As shown in [16 ] , through Naimark’s dilation theorem and purification, considering only projective measurement strategies on shared pure states is sufficient to characterize the quantum value of a nonlocal game, assuming Alice and Bob are restricted to a finite-dimensional Hilbert space. As such, we need only consider strategies where, for given inputs x x x and y y y respectively, { A x a } a , { B y b } b \{A_x^a\}_a,\{B_y^b\}_b { A x a } a , { B y b } b are Alice’s and Bob’s projective measurements, such that Alice outputs color a a a when observing a a a , and Bob outputs color b b b when observing b b b . Let
∣ ψ ⟩ ∈ H = H A ⊗ H B |\psi\rangle\in\mathcal{H} = \mathcal{H}_A \otimes\mathcal{H}_B ∣ ψ ⟩ ∈ H = H A ⊗ H B
be the pure state shared by Alice and Bob, where H A \mathcal{H}_A H A is the Hilbert space for the portion of the state Alice owns, and H B \mathcal{H}_B H B is the Hilbert space for the portion of the state Bob owns.
We can see that the probability that outputs are equal for a given pair of inputs ( x , y ) (x,y) ( x , y ) is
c x y = ∑ k = 0 m − 1 Pr ( k , k ∣ x , y ) = ∑ k = 0 m − 1 ⟨ ψ ∣ A x k ⊗ B y k ∣ ψ ⟩ c_{xy} = \sum_{k=0}^{m-1} \Pr(k,k \mid x,y) = \sum_{k=0}^{m-1} \langle\psi|A_x^k \otimes B_y^k|\psi\rangle c x y = k = 0 ∑ m − 1 Pr ( k , k ∣ x , y ) = k = 0 ∑ m − 1 ⟨ ψ ∣ A x k ⊗ B y k ∣ ψ ⟩
and thus that
ξ = ∑ x = 0 n − 1 ∑ k = 0 m − 1 ⟨ ψ ∣ A x k ⊗ B x k ∣ ψ ⟩ \xi= \sum_{x=0}^{n-1}\sum_{k=0}^{m-1} \langle\psi|A_x^k \otimes B_x^k|\psi\rangle ξ = x = 0 ∑ n − 1 k = 0 ∑ m − 1 ⟨ ψ ∣ A x k ⊗ B x k ∣ ψ ⟩
and
μ = ∑ x = 0 n − 1 ∑ y = 0 n − 1 ∑ k = 0 m − 1 ⟨ ψ ∣ A x k ⊗ B y k ∣ ψ ⟩ . \mu= \sum_{x=0}^{n-1}\sum_{y=0}^{n-1}\sum_{k=0}^{m-1} \langle\psi|A_x^k \otimes B_y^k|\psi\rangle. μ = x = 0 ∑ n − 1 y = 0 ∑ n − 1 k = 0 ∑ m − 1 ⟨ ψ ∣ A x k ⊗ B y k ∣ ψ ⟩ .
We can also define three new operators:
N A k : = ∑ x = 0 n − 1 A x k N_A^k := \sum_{x=0}^{n-1} A_x^k N A k := x = 0 ∑ n − 1 A x k
N B k : = ∑ y = 0 n − 1 B y k N_B^k := \sum_{y=0}^{n-1} B_y^k N B k := y = 0 ∑ n − 1 B y k
Ξ k : = ∑ x = 0 n − 1 A x k ⊗ B x k \Xi_k := \sum_{x=0}^{n-1} A_x^k \otimes B_x^k Ξ k := x = 0 ∑ n − 1 A x k ⊗ B x k
Lemma 4.4.1. For each color k k k , the block operator
Γ k = [ N A k ⊗ I Ξ k Ξ k I ⊗ N B k ] \Gamma_k =
\begin{bmatrix}
N_A^k \otimes I & \Xi_k \\
\Xi_k & I \otimes N_B^k
\end{bmatrix} Γ k = [ N A k ⊗ I Ξ k Ξ k I ⊗ N B k ] is positive semidefinite.
Proof. We can prove this by constructing Γ k \Gamma_k Γ k as a sum of positive semidefinite matrices. Let
T x = [ A x k ⊗ I I ⊗ B x k ] . T_x = \begin{bmatrix} A_x^k \otimes I & I \otimes B_x^k \end{bmatrix}. T x = [ A x k ⊗ I I ⊗ B x k ] .
Note that an operator times its conjugate transpose is positive semidefinite, so T x † T x T_x^\dagger T_x T x † T x is positive semidefinite. We can write it out:
T x † T x = [ ( A x k ⊗ I ) † ( I ⊗ B x k ) † ] [ A x k ⊗ I I ⊗ B x k ] = [ ( A x k ⊗ I ) † ( A x k ⊗ I ) ( A x k ⊗ I ) † ( I ⊗ B x k ) ( I ⊗ B x k ) † ( A x k ⊗ I ) ( I ⊗ B x k ) † ( I ⊗ B x k ) ] . T_x^\dagger T_x =
\begin{bmatrix}
(A_x^k \otimes I)^\dagger\\
(I \otimes B_x^k)^\dagger
\end{bmatrix}
\begin{bmatrix}
A_x^k \otimes I & I \otimes B_x^k
\end{bmatrix}
=
\begin{bmatrix}
(A_x^k \otimes I)^\dagger(A_x^k \otimes I) & (A_x^k \otimes I)^\dagger(I \otimes B_x^k) \\
(I \otimes B_x^k)^\dagger(A_x^k \otimes I) & (I \otimes B_x^k)^\dagger(I \otimes B_x^k)
\end{bmatrix}. T x † T x = [ ( A x k ⊗ I ) † ( I ⊗ B x k ) † ] [ A x k ⊗ I I ⊗ B x k ] = [ ( A x k ⊗ I ) † ( A x k ⊗ I ) ( I ⊗ B x k ) † ( A x k ⊗ I ) ( A x k ⊗ I ) † ( I ⊗ B x k ) ( I ⊗ B x k ) † ( I ⊗ B x k ) ] .
Note that ( A x k ⊗ I ) (A_x^k \otimes I) ( A x k ⊗ I ) and ( I ⊗ B x k ) (I \otimes B_x^k) ( I ⊗ B x k ) are projectors, so they are Hermitian and equal to their own square, so we can rewrite this as
[ ( A x k ⊗ I ) † ( A x k ⊗ I ) ( A x k ⊗ I ) † ( I ⊗ B x k ) ( I ⊗ B x k ) † ( A x k ⊗ I ) ( I ⊗ B x k ) † ( I ⊗ B x k ) ] = [ ( A x k ) 2 ⊗ I A x k ⊗ B x k A x k ⊗ B x k I ⊗ ( B x k ) 2 ] = [ A x k ⊗ I A x k ⊗ B x k A x k ⊗ B x k I ⊗ B x k ] . \begin{bmatrix}
(A_x^k \otimes I)^\dagger(A_x^k \otimes I) & (A_x^k \otimes I)^\dagger(I \otimes B_x^k) \\
(I \otimes B_x^k)^\dagger(A_x^k \otimes I) & (I \otimes B_x^k)^\dagger(I \otimes B_x^k)
\end{bmatrix}
=
\begin{bmatrix}
(A_x^k)^2 \otimes I & A_x^k \otimes B_x^k \\
A_x^k \otimes B_x^k & I \otimes(B_x^k)^2
\end{bmatrix}
=
\begin{bmatrix}
A_x^k \otimes I & A_x^k \otimes B_x^k \\
A_x^k \otimes B_x^k & I \otimes B_x^k
\end{bmatrix}. [ ( A x k ⊗ I ) † ( A x k ⊗ I ) ( I ⊗ B x k ) † ( A x k ⊗ I ) ( A x k ⊗ I ) † ( I ⊗ B x k ) ( I ⊗ B x k ) † ( I ⊗ B x k ) ] = [ ( A x k ) 2 ⊗ I A x k ⊗ B x k A x k ⊗ B x k I ⊗ ( B x k ) 2 ] = [ A x k ⊗ I A x k ⊗ B x k A x k ⊗ B x k I ⊗ B x k ] .
Taking the sum of this expression for T x † T x T_x^\dagger T_x T x † T x over all inputs x x x gives
∑ x = 0 n − 1 [ A x k ⊗ I A x k ⊗ B x k A x k ⊗ B x k I ⊗ B x k ] = [ ∑ x = 0 n − 1 A x k ⊗ I ∑ x = 0 n − 1 A x k ⊗ B x k ∑ x = 0 n − 1 A x k ⊗ B x k ∑ x = 0 n − 1 I ⊗ B x k ] = [ N A k ⊗ I Ξ k Ξ k I ⊗ N B k ] = Γ k \sum_{x=0}^{n-1}
\begin{bmatrix}
A_x^k \otimes I & A_x^k \otimes B_x^k \\
A_x^k \otimes B_x^k & I \otimes B_x^k
\end{bmatrix}
=
\begin{bmatrix}
\sum_{x=0}^{n-1} A_x^k \otimes I & \sum_{x=0}^{n-1} A_x^k \otimes B_x^k \\
\sum_{x=0}^{n-1} A_x^k \otimes B_x^k & \sum_{x=0}^{n-1} I \otimes B_x^k
\end{bmatrix}
=
\begin{bmatrix}
N_A^k \otimes I & \Xi_k \\
\Xi_k & I \otimes N_B^k
\end{bmatrix}
= \Gamma_k x = 0 ∑ n − 1 [ A x k ⊗ I A x k ⊗ B x k A x k ⊗ B x k I ⊗ B x k ] = [ ∑ x = 0 n − 1 A x k ⊗ I ∑ x = 0 n − 1 A x k ⊗ B x k ∑ x = 0 n − 1 A x k ⊗ B x k ∑ x = 0 n − 1 I ⊗ B x k ] = [ N A k ⊗ I Ξ k Ξ k I ⊗ N B k ] = Γ k
Thus, since Γ k \Gamma_k Γ k is a sum of n n n positive semidefinite matrices, it is positive semidefinite. □
Recall that the Löwner operator relation Q ⪯ R Q \preceq R Q ⪯ R means that R − Q R-Q R − Q is positive semidefinite.
Lemma 4.4.2. For each color k k k , Ξ k ⪯ ( N A k ) 1 2 ⊗ ( N B k ) 1 2 \Xi_k \preceq(N_A^k)^{\frac{1}{2}} \otimes(N_B^k)^{\frac{1}{2}} Ξ k ⪯ ( N A k ) 2 1 ⊗ ( N B k ) 2 1 .
Proof. Note: To reduce confusion, we will make explicit which Hilbert space each identity matrix acts on. We fix ε > 0 \varepsilon> 0 ε > 0 and define the following operators:
Q : = ( N A k ⊗ I H B ) + ε I H A ⊗ H B = ( N A k + ε I H A ) ⊗ I H B Q := (N_A^k \otimes I_{\mathcal{H}_B}) + \varepsilon I_{\mathcal{H}_A \otimes\mathcal{H}_B}
= (N_A^k + \varepsilon I_{\mathcal{H}_A}) \otimes I_{\mathcal{H}_B} Q := ( N A k ⊗ I H B ) + ε I H A ⊗ H B = ( N A k + ε I H A ) ⊗ I H B
R : = ( I H A ⊗ N B k ) + ε I H A ⊗ H B = I H A ⊗ ( N B k + ε I H B ) R := (I_{\mathcal{H}_A} \otimes N_B^k) + \varepsilon I_{\mathcal{H}_A \otimes\mathcal{H}_B}
= I_{\mathcal{H}_A} \otimes(N_B^k + \varepsilon I_{\mathcal{H}_B}) R := ( I H A ⊗ N B k ) + ε I H A ⊗ H B = I H A ⊗ ( N B k + ε I H B )
Note that N A k N_A^k N A k and N B k N_B^k N B k are sums of projectors and thus are positive semidefinite and Hermitian, so N A k ⊗ I H B N_A^k \otimes I_{\mathcal{H}_B} N A k ⊗ I H B and I H A ⊗ N B k I_{\mathcal{H}_A} \otimes N_B^k I H A ⊗ N B k are Hermitian and positive semidefinite and thus have non-negative eigenvalues. Thus, Q Q Q and R R R are Hermitian and will have strictly positive eigenvalues, and are thus positive definite. Also note that Q Q Q and R R R commute.
We now invoke a result from [1 ] : for positive definite matrices L , M L,M L , M , the greatest Hermitian matrix Z Z Z such that
[ L Z Z M ] \begin{bmatrix} L & Z \\ Z & M \end{bmatrix} [ L Z Z M ]
is positive semidefinite is the geometric mean L # M L\#M L # M which, when L L L and M M M commute, can be written as ( L M ) 1 2 (LM)^{\frac{1}{2}} ( L M ) 2 1 or as L 1 2 M 1 2 L^{\frac{1}{2}}M^{\frac{1}{2}} L 2 1 M 2 1 (see [4 p. 106] ). By Lemma 4.4.1,
[ N A k ⊗ I H B Ξ k Ξ k I H A ⊗ N B k ] \begin{bmatrix}
N_A^k \otimes I_{\mathcal{H}_B} & \Xi_k \\
\Xi_k & I_{\mathcal{H}_A} \otimes N_B^k
\end{bmatrix} [ N A k ⊗ I H B Ξ k Ξ k I H A ⊗ N B k ]
is positive semidefinite, so
[ N A k ⊗ I H B Ξ k Ξ k I H A ⊗ N B k ] + ε [ I H A ⊗ H B 0 0 I H A ⊗ H B ] \begin{bmatrix}
N_A^k \otimes I_{\mathcal{H}_B} & \Xi_k \\
\Xi_k & I_{\mathcal{H}_A} \otimes N_B^k
\end{bmatrix}
+
\varepsilon
\begin{bmatrix}
I_{\mathcal{H}_A \otimes\mathcal{H}_B} & 0 \\
0 & I_{\mathcal{H}_A \otimes\mathcal{H}_B}
\end{bmatrix} [ N A k ⊗ I H B Ξ k Ξ k I H A ⊗ N B k ] + ε [ I H A ⊗ H B 0 0 I H A ⊗ H B ]
is also positive semidefinite. That matrix can be rewritten as
[ ( N A k + ε I H A ) ⊗ I H B Ξ k Ξ k I H A ⊗ ( N B k + ε I H B ) ] = [ Q Ξ k Ξ k R ] \begin{bmatrix}
(N_A^k+\varepsilon I_{\mathcal{H}_A}) \otimes I_{\mathcal{H}_B} & \Xi_k \\
\Xi_k & I_{\mathcal{H}_A} \otimes(N_B^k+\varepsilon I_{\mathcal{H}_B})
\end{bmatrix}
=
\begin{bmatrix}
Q & \Xi_k \\
\Xi_k & R
\end{bmatrix} [ ( N A k + ε I H A ) ⊗ I H B Ξ k Ξ k I H A ⊗ ( N B k + ε I H B ) ] = [ Q Ξ k Ξ k R ]
Thus, since Q Q Q and R R R commute and Ξ k \Xi_k Ξ k is Hermitian (as a sum of tensor products of projectors),
Ξ k ⪯ Q 1 2 R 1 2 = ( ( N A k + ε I H A ) ⊗ I H B ) 1 2 ( I H A ⊗ ( N B k + ε I H B ) ) 1 2 = ( N A k + ε I H A ) 1 2 ⊗ ( N B k + ε I H B ) 1 2 . \Xi_k \preceq Q^{\frac{1}{2}}R^{\frac{1}{2}} = \left((N_A^k+\varepsilon I_{\mathcal{H}_A}) \otimes I_{\mathcal{H}_B}\right)^{\frac{1}{2}}\left(I_{\mathcal{H}_A} \otimes(N_B^k+\varepsilon I_{\mathcal{H}_B})\right)^{\frac{1}{2}} = (N_A^k+\varepsilon I_{\mathcal{H}_A})^{\frac{1}{2}} \otimes(N_B^k+\varepsilon I_{\mathcal{H}_B})^{\frac{1}{2}}. Ξ k ⪯ Q 2 1 R 2 1 = ( ( N A k + ε I H A ) ⊗ I H B ) 2 1 ( I H A ⊗ ( N B k + ε I H B ) ) 2 1 = ( N A k + ε I H A ) 2 1 ⊗ ( N B k + ε I H B ) 2 1 .
Note that N A k + ε I H A N_A^k+\varepsilon I_{\mathcal{H}_A} N A k + ε I H A can be diagonalized using the same unitary as N A k N_A^k N A k , so we can write
N A k = U diag ( λ 1 , … , λ d ) U † N_A^k = U\operatorname{diag}(\lambda_1,\ldots,\lambda_d)U^\dagger N A k = U diag ( λ 1 , … , λ d ) U †
as well as
( N A k ) 1 2 = U diag ( λ 1 , … , λ d ) U † (N_A^k)^{\frac{1}{2}} = U\operatorname{diag}(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_d})U^\dagger ( N A k ) 2 1 = U diag ( λ 1 , … , λ d ) U †
and
N A k + ε I H A = U diag ( λ 1 + ε , … , λ d + ε ) U † N_A^k+\varepsilon I_{\mathcal{H}_A} = U\operatorname{diag}(\lambda_1+\varepsilon,\ldots,\lambda_d+\varepsilon)U^\dagger N A k + ε I H A = U diag ( λ 1 + ε , … , λ d + ε ) U †
and thus
( N A k + ε I H A ) 1 2 = U diag ( λ 1 + ε , … , λ d + ε ) U † , (N_A^k+\varepsilon I_{\mathcal{H}_A})^{\frac{1}{2}} = U\operatorname{diag}(\sqrt{\lambda_1+\varepsilon},\ldots,\sqrt{\lambda_d+\varepsilon})U^\dagger, ( N A k + ε I H A ) 2 1 = U diag ( λ 1 + ε , … , λ d + ε ) U † ,
so since the square root function on real non-negative scalars is continuous (and of course, the eigenvalues of a positive semidefinite matrix are real and non-negative), we have that
lim ε → 0 ( N A k + ε I H A ) 1 2 = ( N A k ) 1 2 . \lim_{\varepsilon\to0}(N_A^k+\varepsilon I_{\mathcal{H}_A})^{\frac{1}{2}}=(N_A^k)^{\frac{1}{2}}. ε → 0 lim ( N A k + ε I H A ) 2 1 = ( N A k ) 2 1 .
and by the same logic
lim ε → 0 ( N B k + ε I H B ) 1 2 = ( N B k ) 1 2 . \lim_{\varepsilon\to0}(N_B^k+\varepsilon I_{\mathcal{H}_B})^{\frac{1}{2}}=(N_B^k)^{\frac{1}{2}}. ε → 0 lim ( N B k + ε I H B ) 2 1 = ( N B k ) 2 1 .
Thus, since limits preserve the Löwner order and distribute over tensor products (when each tensor factor converges individually), we can send ε \varepsilon ε to 0 to conclude that
Ξ k ⪯ ( N A k + 0 I H A ) 1 2 ⊗ ( N B k + 0 I H B ) 1 2 = ( N A k ) 1 2 ⊗ ( N B k ) 1 2 . \Xi_k \preceq(N_A^k+0I_{\mathcal{H}_A})^{\frac{1}{2}}\otimes(N_B^k+0I_{\mathcal{H}_B})^{\frac{1}{2}}=(N_A^k)^{\frac{1}{2}}\otimes(N_B^k)^{\frac{1}{2}}. Ξ k ⪯ ( N A k + 0 I H A ) 2 1 ⊗ ( N B k + 0 I H B ) 2 1 = ( N A k ) 2 1 ⊗ ( N B k ) 2 1 .
Theorem 4.4.3. Any valid quantum strategy for this game has μ ≥ ε 2 m \mu\ge\frac{\varepsilon^2}{m} μ ≥ m ε 2 .
Proof. We can define a couple of new terms:
ξ k : = ⟨ ψ ∣ Ξ k ∣ ψ ⟩ = ⟨ ψ ∣ ( ∑ x = 0 n − 1 ( A x k ⊗ B x k ) ) ∣ ψ ⟩ = ∑ x = 0 n − 1 ⟨ ψ ∣ ( A x k ⊗ B x k ) ∣ ψ ⟩ . \xi_k := \langle\psi|\Xi_k|\psi\rangle= \langle\psi|\left(\sum_{x=0}^{n-1}(A_x^k\otimes B_x^k)\right)|\psi\rangle= \sum_{x=0}^{n-1}\langle\psi|(A_x^k\otimes B_x^k)|\psi\rangle. ξ k := ⟨ ψ ∣ Ξ k ∣ ψ ⟩ = ⟨ ψ ∣ ( x = 0 ∑ n − 1 ( A x k ⊗ B x k ) ) ∣ ψ ⟩ = x = 0 ∑ n − 1 ⟨ ψ ∣ ( A x k ⊗ B x k ) ∣ ψ ⟩ .
μ k : = ⟨ ψ ∣ ( N A k ⊗ N B k ) ∣ ψ ⟩ = ⟨ ψ ∣ ( ( ∑ x = 0 n − 1 A x k ) ⊗ ( ∑ y = 0 n − 1 B y k ) ) ∣ ψ ⟩ = ∑ x = 0 n − 1 ∑ y = 0 n − 1 ⟨ ψ ∣ ( A x k ⊗ B y k ) ∣ ψ ⟩ . \mu_k := \langle\psi|(N_A^k\otimes N_B^k)|\psi\rangle= \langle\psi|\left(\left(\sum_{x=0}^{n-1}A_x^k\right)\otimes\left(\sum_{y=0}^{n-1}B_y^k\right)\right)|\psi\rangle= \sum_{x=0}^{n-1}\sum_{y=0}^{n-1}\langle\psi|(A_x^k\otimes B_y^k)|\psi\rangle. μ k := ⟨ ψ ∣ ( N A k ⊗ N B k ) ∣ ψ ⟩ = ⟨ ψ ∣ ( ( x = 0 ∑ n − 1 A x k ) ⊗ ( y = 0 ∑ n − 1 B y k ) ) ∣ ψ ⟩ = x = 0 ∑ n − 1 y = 0 ∑ n − 1 ⟨ ψ ∣ ( A x k ⊗ B y k ) ∣ ψ ⟩ .
Note from the formulas for ξ \xi ξ and μ \mu μ that ξ = ∑ k = 0 m − 1 ξ k \xi=\sum_{k=0}^{m-1}\xi_k ξ = ∑ k = 0 m − 1 ξ k and μ = ∑ k = 0 m − 1 μ k \mu=\sum_{k=0}^{m-1}\mu_k μ = ∑ k = 0 m − 1 μ k . We can then define
R k : = ( N A k ) 1 2 ⊗ ( N B k ) 1 2 . R_k := (N_A^k)^{\frac{1}{2}}\otimes(N_B^k)^{\frac{1}{2}}. R k := ( N A k ) 2 1 ⊗ ( N B k ) 2 1 .
Note that R k R_k R k is a tensor product of Hermitian operators (positive semidefinite Hermitian operators have positive semidefinite square roots) and thus is itself Hermitian, and
R k 2 = ( N A k ) 1 2 ( N A k ) 1 2 ⊗ ( N B k ) 1 2 ( N B k ) 1 2 = N A k ⊗ N B k R_k^2=(N_A^k)^{\frac{1}{2}}(N_A^k)^{\frac{1}{2}}\otimes(N_B^k)^{\frac{1}{2}}(N_B^k)^{\frac{1}{2}}=N_A^k\otimes N_B^k R k 2 = ( N A k ) 2 1 ( N A k ) 2 1 ⊗ ( N B k ) 2 1 ( N B k ) 2 1 = N A k ⊗ N B k
and thus
μ k = ⟨ ψ ∣ R k 2 ∣ ψ ⟩ . \mu_k=\langle\psi|R_k^2|\psi\rangle. μ k = ⟨ ψ ∣ R k 2 ∣ ψ ⟩ .
By Lemma 4.4.2 , R k ⪰ Ξ k R_k\succeq\Xi_k R k ⪰ Ξ k , and thus we have that
ξ k = ⟨ ψ ∣ Ξ k ∣ ψ ⟩ ≤ ⟨ ψ ∣ R k ∣ ψ ⟩ . \xi_k=\langle\psi|\Xi_k|\psi\rangle\leq\langle\psi|R_k|\psi\rangle. ξ k = ⟨ ψ ∣ Ξ k ∣ ψ ⟩ ≤ ⟨ ψ ∣ R k ∣ ψ ⟩ .
We can observe that, since R k R_k R k is Hermitian and thus ⟨ ψ ∣ R k ψ ⟩ \langle\psi|R_k\psi\rangle ⟨ ψ ∣ R k ψ ⟩ is real,
⟨ ψ ∣ R k ψ ⟩ ≤ ∣ ⟨ ψ ∣ R k ψ ⟩ ∣ \langle\psi|R_k\psi\rangle\leq|\langle\psi|R_k\psi\rangle| ⟨ ψ ∣ R k ψ ⟩ ≤ ∣ ⟨ ψ ∣ R k ψ ⟩ ∣
and by the Cauchy-Schwarz inequality on vectors in H A ⊗ H B \mathcal{H}_A\otimes\mathcal{H}_B H A ⊗ H B ,
∣ ⟨ ψ ∣ R k ψ ⟩ ∣ ≤ ∥ ∣ ψ ⟩ ∥ ⋅ ∥ ∣ R k ψ ⟩ ∥ . |\langle\psi|R_k\psi\rangle|\leq\|\lvert\psi\rangle\|\cdot\|\lvert R_k\psi\rangle\|. ∣ ⟨ ψ ∣ R k ψ ⟩ ∣ ≤ ∥ ∣ ψ ⟩ ∥ ⋅ ∥ ∣ R k ψ ⟩ ∥.
The magnitude of ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ is 1, so
∥ ∣ ψ ⟩ ∥ ⋅ ∥ ∣ R k ψ ⟩ ∥ = ∥ ∣ R k ψ ⟩ ∥ = ∥ R k ∣ ψ ⟩ ∥ . \|\lvert\psi\rangle\|\cdot\|\lvert R_k\psi\rangle\|=\|\lvert R_k\psi\rangle\|=\|R_k\lvert\psi\rangle\|. ∥ ∣ ψ ⟩ ∥ ⋅ ∥ ∣ R k ψ ⟩ ∥ = ∥ ∣ R k ψ ⟩ ∥ = ∥ R k ∣ ψ ⟩ ∥.
Thus
ξ k ≤ ∥ R k ∣ ψ ⟩ ∥ . \xi_k\leq\|R_k\lvert\psi\rangle\|. ξ k ≤ ∥ R k ∣ ψ ⟩ ∥.
Since R k R_k R k is Hermitian,
∥ R k ∣ ψ ⟩ ∥ 2 = ⟨ ψ ∣ R k † R k ∣ ψ ⟩ = ⟨ ψ ∣ R k 2 ∣ ψ ⟩ = μ k \lVert R_k|\psi\rangle\rVert^2=\langle\psi|R_k^\dagger R_k|\psi\rangle=\langle\psi|R_k^2|\psi\rangle=\mu_k ∥ R k ∣ ψ ⟩ ∥ 2 = ⟨ ψ ∣ R k † R k ∣ ψ ⟩ = ⟨ ψ ∣ R k 2 ∣ ψ ⟩ = μ k
and thus (since ξ k \xi_k ξ k is a sum of probabilities and thus is nonnegative)
ξ k 2 ≤ μ k . \xi_k^2\leq\mu_k. ξ k 2 ≤ μ k .
Then by the Cauchy-Schwarz inequality on R m \mathbb{R}^m R m ,
ξ 2 = ( ∑ k = 0 m − 1 ξ k ) 2 ≤ ( ∑ k = 0 m − 1 1 2 ) ( ∑ k = 0 m − 1 ξ k 2 ) = m ∑ k = 0 m − 1 ξ k 2 ≤ m ∑ k = 0 m − 1 μ k = m μ \xi^2=\left(\sum_{k=0}^{m-1}\xi_k\right)^2\leq\left(\sum_{k=0}^{m-1}1^2\right)\left(\sum_{k=0}^{m-1}\xi_k^2\right)=m\sum_{k=0}^{m-1}\xi_k^2\leq m\sum_{k=0}^{m-1}\mu_k=m\mu ξ 2 = ( k = 0 ∑ m − 1 ξ k ) 2 ≤ ( k = 0 ∑ m − 1 1 2 ) ( k = 0 ∑ m − 1 ξ k 2 ) = m k = 0 ∑ m − 1 ξ k 2 ≤ m k = 0 ∑ m − 1 μ k = m μ
and thus ξ 2 m ≤ μ \frac{\xi^2}{m}\leq\mu m ξ 2 ≤ μ as desired.
Recall that we defined s : = p ( n − 1 ) 1 − p + 1 s:=\frac{p(n-1)}{1-p}+1 s := 1 − p p ( n − 1 ) + 1 , and that s s s is monotonic in p p p by Lemma 2.1.1 .
Lemma 4.4.4. At s = 2 n m s=\frac{2n}{m} s = m 2 n , the strategy defined in § 4.1 is optimal among quantum strategies.
Proof. Recall that we can use ν : = s ξ − μ \nu:=s\xi-\mu ν := s ξ − μ in lieu of the value ω \omega ω as an objective function. By Theorem 4.4.3 , any valid quantum strategy has μ ≥ ξ 2 m \mu\geq\frac{\xi^2}{m} μ ≥ m ξ 2 , and thus
ν : = s ξ − μ = 2 n m ξ − μ ≤ 2 n m ξ − ξ 2 m = ξ ( 2 n − ξ ) m . \nu:=s\xi-\mu=\frac{2n}{m}\xi-\mu\leq\frac{2n}{m}\xi-\frac{\xi^2}{m}=\frac{\xi(2n-\xi)}{m}. ν := s ξ − μ = m 2 n ξ − μ ≤ m 2 n ξ − m ξ 2 = m ξ ( 2 n − ξ ) . This expression is quadratic in ξ \xi ξ with negative leading coefficient and hence is maximized when ξ \xi ξ equals the midpoint of its roots: i.e., at ξ = 0 + 2 n 2 = n \xi=\frac{0+2n}{2}=n ξ = 2 0 + 2 n = n .
The strategy defined in § 4.1 attains both ξ = n \xi=n ξ = n by Theorem 4.1.1 and μ = n 2 m = ξ 2 m \mu=\frac{n^2}{m}=\frac{\xi^2}{m} μ = m n 2 = m ξ 2 by Theorem 4.1.2 , so no other quantum strategy can have a larger value of ν \nu ν than the one achieved by the strategy defined in § 4.1 , as desired.
Theorem 4.4.5. For all p ≥ 2 n − m ( m + 2 ) n − 2 m p\geq\frac{2n-m}{(m+2)n-2m} p ≥ ( m + 2 ) n − 2 m 2 n − m , the quantum strategy defined in § 4.1 is optimal among quantum strategies.
Proof. By Lemma 4.4.4 , this strategy is optimal at the value of p p p corresponding to s = 2 n m s=\frac{2n}{m} s = m 2 n :
p = s − 1 n + s − 2 = 2 n m − 1 n + 2 n m − 2 = 2 n − m n m + 2 n − 2 m . p=\frac{s-1}{n+s-2}=\frac{\frac{2n}{m}-1}{n+\frac{2n}{m}-2}=\frac{2n-m}{nm+2n-2m}. p = n + s − 2 s − 1 = n + m 2 n − 2 m 2 n − 1 = nm + 2 n − 2 m 2 n − m . By Theorem 2.1.2 , it is then optimal for all p ≥ 2 n − m ( m + 2 ) n − 2 m p\geq\frac{2n-m}{(m+2)n-2m} p ≥ ( m + 2 ) n − 2 m 2 n − m , as desired.
Theorem 4.4.6. For all p ≥ 2 n − m ( m + 2 ) n − 2 m p\geq\frac{2n-m}{(m+2)n-2m} p ≥ ( m + 2 ) n − 2 m 2 n − m , our game has quantum value
ω = p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) . \omega=p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right). ω = p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) .
Proof. By Theorem 4.4.5 , the strategy defined in § 4.1 is optimal among quantum strategies. Then its value, which by Theorem 4.1.3 is p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right) p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) , is the game’s value.
Remark. This parallels the classical threshold for synchronous optimality: when m ≥ 2 m \ge2 m ≥ 2 ,
2 n − m ( m + 2 ) n − 2 m ≤ 2 m + 2 ≤ 1 2 . \frac{2n-m}{(m+2)n-2m} \le\frac{2}{m+2} \le\frac{1}{2}. ( m + 2 ) n − 2 m 2 n − m ≤ m + 2 2 ≤ 2 1 .
Remark. Earlier in our work, we found a separate proof that n ξ − μ ≤ n 2 ( 1 − 1 m ) n\xi-\mu\le n^2\left(1-\frac{1}{m}\right) n ξ − μ ≤ n 2 ( 1 − m 1 ) . This leads to a proof of the same value of this game which only holds when p ≥ 1 2 p \ge\frac{1}{2} p ≥ 2 1 . This is entirely covered by the above work, but since it was a substantially different proof technique, we have preserved that chain of work in Appendix B.
Other Quantum Strategies
Having shown that a synchronous strategy is optimal whenever p ≥ 2 n − m ( m + 2 ) n − 2 m p \ge\frac{2n-m}{(m+2)n-2m} p ≥ ( m + 2 ) n − 2 m 2 n − m , we now try to find strategies that work better for smaller p p p . One obvious idea is for Alice to always output 0 and Bob 1, so that they win exactly when they receive different inputs: i.e., ξ = μ = 0 \xi=\mu=0 ξ = μ = 0 .
Making use of the remaining m − 2 m-2 m − 2 colors lets them do a bit better. If Alice’s input x x x satisfies x < m − 2 x<m-2 x < m − 2 , she can output x x x , and otherwise always output m − 2 m-2 m − 2 ; likewise, if Bob’s input y y y satisfies y < m − 2 y<m-2 y < m − 2 , Bob can output color y y y , and otherwise always output m − 1 m-1 m − 1 . Then ξ = m − 2 \xi=m-2 ξ = m − 2 , and μ = ξ \mu=\xi μ = ξ still, since Alice and Bob only output the same color if x = y < m − 2 x=y<m-2 x = y < m − 2 .
In fact, if m ≥ 3 m \ge3 m ≥ 3 they can play our optimal synchronous strategy (with m − 2 m-2 m − 2 colors) on anywhere between m − 2 m-2 m − 2 and n n n of their inputs; as before, Alice can dump her remaining inputs into the second-to-last color and Bob can dump his into the last color.
Then ξ \xi ξ equals the number of synchronous inputs exactly, and μ = ξ 2 m − 2 \mu=\frac{\xi^2}{m-2} μ = m − 2 ξ 2 , so
ν = s ξ − μ = s ξ − ξ 2 m − 2 . \nu=s\xi-\mu=s\xi-\frac{\xi^2}{m-2}. ν = s ξ − μ = s ξ − m − 2 ξ 2 .
This is quadratic in ξ \xi ξ with negative leading coefficient, so the value of ξ \xi ξ that maximizes ν \nu ν is simply the nearest element of [ m − 2 , n ] ∩ Z [m-2,n]\cap\mathbb{Z} [ m − 2 , n ] ∩ Z to s ( m − 2 ) 2 \frac{s(m-2)}{2} 2 s ( m − 2 ) , which maximizes ν \nu ν over R \mathbb{R} R .
In particular, if s ( m − 2 ) 2 < m − 2 \frac{s(m-2)}{2}<m-2 2 s ( m − 2 ) < m − 2 (i.e., s < 2 s<2 s < 2 ), the optimal ξ \xi ξ is m − 2 m-2 m − 2 . Even if some analogue of these dumping strategies that allowed fractional ξ \xi ξ were feasible (which we have not ruled out), ξ < m − 2 \xi<m-2 ξ < m − 2 would imply that μ = ξ 2 m − 2 = ξ ξ m − 2 < ξ \mu=\frac{\xi^2}{m-2}=\xi\frac{\xi}{m-2}<\xi μ = m − 2 ξ 2 = ξ m − 2 ξ < ξ , which is impossible.
Likewise, if s ( m − 2 ) 2 > n \frac{s(m-2)}{2}>n 2 s ( m − 2 ) > n (i.e., s > 2 n m − 2 s>\frac{2n}{m-2} s > m − 2 2 n ), the optimal ξ \xi ξ is n n n (even fractionally), and since this strategy is fully synchronous, it cannot outperform the strategy from § 4.1 by Theorem 4.3.1 .
The largest value of ν \nu ν attained by any dumping strategy is then at most
s 2 ( m − 2 ) 2 − ( s ( m − 2 ) 2 ) 2 m − 2 = s 2 ( m − 2 ) 2 − s 2 ( m − 2 ) 2 4 ( m − 2 ) = s 2 ( m − 2 ) 2 − s 2 ( m − 2 ) 4 = s 2 ( m − 2 ) 4 . \frac{s^2(m-2)}{2}-\frac{\left(\frac{s(m-2)}{2}\right)^2}{m-2}
=\frac{s^2(m-2)}{2}-\frac{s^2(m-2)^2}{4(m-2)}
=\frac{s^2(m-2)}{2}-\frac{s^2(m-2)}{4}
=\frac{s^2(m-2)}{4}. 2 s 2 ( m − 2 ) − m − 2 ( 2 s ( m − 2 ) ) 2 = 2 s 2 ( m − 2 ) − 4 ( m − 2 ) s 2 ( m − 2 ) 2 = 2 s 2 ( m − 2 ) − 4 s 2 ( m − 2 ) = 4 s 2 ( m − 2 ) .
it could beat our synchronous strategy when s 2 ( m − 2 ) 4 > s n − n 2 m \frac{s^2(m-2)}{4} > sn-\frac{n^2}{m} 4 s 2 ( m − 2 ) > s n − m n 2 , or s 2 m ( m − 2 ) > 4 s m n − 4 n 2 s^2m(m-2)>4smn-4n^2 s 2 m ( m − 2 ) > 4 s mn − 4 n 2 , which occurs exactly when the quadratic m ( m − 2 ) s 2 − 4 m n s + 4 n 2 m(m-2)s^2-4mns+4n^2 m ( m − 2 ) s 2 − 4 mn s + 4 n 2 is positive. Its roots are
4 m n ± ( 4 m n ) 2 − 4 ⋅ m ( m − 2 ) ⋅ 4 n 2 2 m ( m − 2 ) = 4 m n ± 4 n m 2 − m ( m − 2 ) 2 m ( m − 2 ) = 2 n ( m ± 2 m ) m ( m − 2 ) . \frac{4mn\pm\sqrt{(4mn)^2-4\cdot m(m-2)\cdot4n^2}}{2m(m-2)}
=\frac{4mn\pm4n\sqrt{m^2-m(m-2)}}{2m(m-2)}
=\frac{2n(m\pm\sqrt{2m})}{m(m-2)}. 2 m ( m − 2 ) 4 mn ± ( 4 mn ) 2 − 4 ⋅ m ( m − 2 ) ⋅ 4 n 2 = 2 m ( m − 2 ) 4 mn ± 4 n m 2 − m ( m − 2 ) = m ( m − 2 ) 2 n ( m ± 2 m ) .
and its leading coefficient is positive, so it is positive when s < 2 n ( m − 2 m ) m ( m − 2 ) s<\frac{2n(m-\sqrt{2m})}{m(m-2)} s < m ( m − 2 ) 2 n ( m − 2 m ) or s > 2 n ( m + 2 m ) m ( m − 2 ) s>\frac{2n(m+\sqrt{2m})}{m(m-2)} s > m ( m − 2 ) 2 n ( m + 2 m ) .
We can ignore the latter case, since 2 m > 0 \sqrt{2m}>0 2 m > 0 , so s > 2 n ( m + 2 m ) m ( m − 2 ) > 2 n m m ( m − 2 ) = 2 n m − 2 s>\frac{2n(m+\sqrt{2m})}{m(m-2)}>\frac{2nm}{m(m-2)}=\frac{2n}{m-2} s > m ( m − 2 ) 2 n ( m + 2 m ) > m ( m − 2 ) 2 nm = m − 2 2 n .
The largest s s s at which a dumping strategy could beat our synchronous strategy is then
2 n ( m − 2 m ) m ( m − 2 ) . \frac{2n(m-\sqrt{2m})}{m(m-2)}. m ( m − 2 ) 2 n ( m − 2 m ) .
as long as this quantity is greater than 2, which occurs when 2 n ( m − 2 m ) > 2 m ( m − 2 ) 2n(m-\sqrt{2m})>2m(m-2) 2 n ( m − 2 m ) > 2 m ( m − 2 ) , or 2 n m − 2 m ( m − 2 ) > 2 n 2 m 2nm-2m(m-2)>2n\sqrt{2m} 2 nm − 2 m ( m − 2 ) > 2 n 2 m , which (since 2 m > 0 2\sqrt{m}>0 2 m > 0 ) is equivalent to ( n + 2 − m ) m > 2 n (n+2-m)\sqrt{m}>\sqrt{2n} ( n + 2 − m ) m > 2 n .
Both sides are always positive, so this inequality is equivalent to ( n + 2 − m ) 2 m > 2 n 2 (n+2-m)^2m>2n^2 ( n + 2 − m ) 2 m > 2 n 2 , or
0 < ( n + 2 − m ) 2 m − 2 n 2 = ( n 2 + 4 + m 2 + 4 n − 2 m n − 4 m ) m − 2 n 2 = m n 2 + 4 m + m 3 + 4 m n − 2 m 2 n − 4 m 2 − 2 n 2 = m n 2 − 2 n 2 + m 3 − 2 m 2 − 2 m 2 n + 4 m n − 2 m 2 + 4 m = ( m − 2 ) ( n 2 + m 2 − 2 m n − 2 m ) = ( m − 2 ) ( ( n − m ) 2 − 2 m ) . \begin{aligned}
0<(n+2-m)^2m-2n^2 \\
&=(n^2+4+m^2+4n-2mn-4m)m-2n^2 \\
&=mn^2+4m+m^3+4mn-2m^2n-4m^2-2n^2 \\
&=mn^2-2n^2+m^3-2m^2-2m^2n+4mn-2m^2+4m \\
&=(m-2)(n^2+m^2-2mn-2m) \\
&=(m-2)((n-m)^2-2m).
\end{aligned} 0 < ( n + 2 − m ) 2 m − 2 n 2 = ( n 2 + 4 + m 2 + 4 n − 2 mn − 4 m ) m − 2 n 2 = m n 2 + 4 m + m 3 + 4 mn − 2 m 2 n − 4 m 2 − 2 n 2 = m n 2 − 2 n 2 + m 3 − 2 m 2 − 2 m 2 n + 4 mn − 2 m 2 + 4 m = ( m − 2 ) ( n 2 + m 2 − 2 mn − 2 m ) = ( m − 2 ) (( n − m ) 2 − 2 m ) .
Since m ≥ 3 m\ge3 m ≥ 3 , m − 2 > 0 m-2>0 m − 2 > 0 , so this inequality simplifies to 0 < ( n − m ) 2 − 2 m 0<(n-m)^2-2m 0 < ( n − m ) 2 − 2 m , or 2 m < ( n − m ) 2 2m<(n-m)^2 2 m < ( n − m ) 2 .
Otherwise, dumping strategies can only outperform our synchronous strategy when s < 2 s<2 s < 2 , at which point the best dumping strategy has ξ = m − 2 \xi=m-2 ξ = m − 2 and thus has larger ν \nu ν when
s n − n 2 m < s ( m − 2 ) − ( m − 2 ) 2 m − 2 = s ( m − 2 ) − ( m − 2 ) , sn-\frac{n^2}{m}<s(m-2)-\frac{(m-2)^2}{m-2}=s(m-2)-(m-2), s n − m n 2 < s ( m − 2 ) − m − 2 ( m − 2 ) 2 = s ( m − 2 ) − ( m − 2 ) ,
or s ( n + 2 − m ) < n 2 m − m + 2 s(n+2-m)<\frac{n^2}{m}-m+2 s ( n + 2 − m ) < m n 2 − m + 2 , which since n + 2 − m > 0 n+2-m>0 n + 2 − m > 0 is equivalent to s < n 2 − m 2 + 2 m m ( n + 2 − m ) s<\frac{n^2-m^2+2m}{m(n+2-m)} s < m ( n + 2 − m ) n 2 − m 2 + 2 m .
Remark. Note that we have not proven that these dumping strategies are optimal across all quantum strategies for any p > 0 p>0 p > 0 , only that they outperform synchronous strategies near the specified values of s s s (or p p p ). However, we also do not know of any strategy that outperforms both our synchronous strategy and all dumping strategies for any values of n n n , m m m , or p p p .
Quantum Advantage over Classical Strategies
We can now apply the previous results to explicitly find the advantage provided by use of entanglement for this game.
Recall that the quantum advantage is the difference between the values of the optimal quantum and classical strategies, and the quantum synchronous advantage is the difference between the values of the optimal quantum and classical synchronous strategies. Also recall that we defined r = n m o d m r=n\bmod m r = n mod m and q = ⌊ n m ⌋ q=\left\lfloor\frac{n}{m}\right\rfloor q = ⌊ m n ⌋ , so that n = q m + r n=qm+r n = q m + r and r ∈ [ 0 , m ) r\in[0,m) r ∈ [ 0 , m ) .
Theorem 4.6.1. The quantum synchronous advantage in this game is
( 1 − p ) ( r ( m − r ) m n ( n − 1 ) ) . (1-p)\left(\frac{r(m-r)}{mn(n-1)}\right). ( 1 − p ) ( mn ( n − 1 ) r ( m − r ) ) .
Proof. From Theorems 3.2.2 and 4.3.2 , we have that the classical and quantum synchronous values of this game are
p + ( 1 − p ) ( 1 − ( q − 1 ) n + ( q + 1 ) r n ( n − 1 ) ) p+(1-p)\left(1-\frac{(q-1)n+(q+1)r}{n(n-1)}\right) p + ( 1 − p ) ( 1 − n ( n − 1 ) ( q − 1 ) n + ( q + 1 ) r )
and
p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right) p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m )
respectively. Thus, the quantum synchronous advantage is
p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) − ( p + ( 1 − p ) ( 1 − ( q − 1 ) n + ( q + 1 ) r n ( n − 1 ) ) ) = ( 1 − p ) ( ( q − 1 ) n + ( q + 1 ) r n ( n − 1 ) − n − m m ( n − 1 ) ) = ( 1 − p ) ( m q n − m n + m q r + m r − n 2 + n m m n ( n − 1 ) ) = ( 1 − p ) ( m q n + m q r + m r − n 2 m n ( n − 1 ) ) = ( 1 − p ) ( m q n + ( m q + r ) r − r 2 + m r − n 2 m n ( n − 1 ) ) = ( 1 − p ) ( m q n + n r − r 2 + m r − n 2 m n ( n − 1 ) ) = ( 1 − p ) ( ( m q + r ) n − r 2 + m r − n 2 m n ( n − 1 ) ) = ( 1 − p ) ( n 2 − r 2 + m r − n 2 m n ( n − 1 ) ) = ( 1 − p ) ( r ( m − r ) m n ( n − 1 ) ) \begin{aligned}
& p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right)-\left(p+(1-p)\left(1-\frac{(q-1)n+(q+1)r}{n(n-1)}\right)\right) \\
={}& (1-p)\left(\frac{(q-1)n+(q+1)r}{n(n-1)}-\frac{n-m}{m(n-1)}\right) \\
={}& (1-p)\left(\frac{mqn-mn+mqr+mr-n^2+nm}{mn(n-1)}\right) \\
={}& (1-p)\left(\frac{mqn+mqr+mr-n^2}{mn(n-1)}\right) \\
={}& (1-p)\left(\frac{mqn+(mq+r)r-r^2+mr-n^2}{mn(n-1)}\right) \\
={}& (1-p)\left(\frac{mqn+nr-r^2+mr-n^2}{mn(n-1)}\right) \\
={}& (1-p)\left(\frac{(mq+r)n-r^2+mr-n^2}{mn(n-1)}\right) \\
={}& (1-p)\left(\frac{n^2-r^2+mr-n^2}{mn(n-1)}\right) \\
={}& (1-p)\left(\frac{r(m-r)}{mn(n-1)}\right)
\end{aligned} = = = = = = = = p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) − ( p + ( 1 − p ) ( 1 − n ( n − 1 ) ( q − 1 ) n + ( q + 1 ) r ) ) ( 1 − p ) ( n ( n − 1 ) ( q − 1 ) n + ( q + 1 ) r − m ( n − 1 ) n − m ) ( 1 − p ) ( mn ( n − 1 ) m q n − mn + m q r + m r − n 2 + nm ) ( 1 − p ) ( mn ( n − 1 ) m q n + m q r + m r − n 2 ) ( 1 − p ) ( mn ( n − 1 ) m q n + ( m q + r ) r − r 2 + m r − n 2 ) ( 1 − p ) ( mn ( n − 1 ) m q n + n r − r 2 + m r − n 2 ) ( 1 − p ) ( mn ( n − 1 ) ( m q + r ) n − r 2 + m r − n 2 ) ( 1 − p ) ( mn ( n − 1 ) n 2 − r 2 + m r − n 2 ) ( 1 − p ) ( mn ( n − 1 ) r ( m − r ) )
:::
Theorem 4.6.2. When p ≥ 2 m + 2 p\geq\frac{2}{m+2} p ≥ m + 2 2 , the quantum advantage in this game is
( 1 − p ) ( r ( m − r ) m n ( n − 1 ) ) . (1-p)\left(\frac{r(m-r)}{mn(n-1)}\right). ( 1 − p ) ( mn ( n − 1 ) r ( m − r ) ) .
Proof. When p ≥ 2 m + 2 p \ge\frac{2}{m+2} p ≥ m + 2 2 , from Theorems 3.3.3 and 4.4.6 , we have that the classical and quantum synchronous values of this game are the same as the classical and quantum values, so by Theorem 4.6.1 the quantum advantage is
( 1 − p ) ( r ( m − r ) m n ( n − 1 ) ) . (1-p)\left(\frac{r(m-r)}{mn(n-1)}\right). ( 1 − p ) ( mn ( n − 1 ) r ( m − r ) ) .
Remark. Note that this advantage is 0 if and only if r = 0 r=0 r = 0 or, in other words, when m ∣ n m \mid n m ∣ n .
Remark. r ( m − r ) ≤ m 2 m 2 = m 2 4 r(m-r) \le\frac{m}{2}\frac{m}{2}=\frac{m^2}{4} r ( m − r ) ≤ 2 m 2 m = 4 m 2 , so the quantum advantage when p ≥ 2 m + 2 p \ge\frac{2}{m+2} p ≥ m + 2 2 satisfies
( 1 − p ) ( r ( m − r ) m n ( n − 1 ) ) ≤ ( 1 − p ) ( m 2 4 m n ( n − 1 ) ) = ( 1 − p ) ( m 4 n ( n − 1 ) ) = O ( m n 2 ) . (1-p)\left(\frac{r(m-r)}{mn(n-1)}\right) \le(1-p)\left(\frac{m^2}{4mn(n-1)}\right)=(1-p)\left(\frac{m}{4n(n-1)}\right)=O\left(\frac{m}{n^2}\right). ( 1 − p ) ( mn ( n − 1 ) r ( m − r ) ) ≤ ( 1 − p ) ( 4 mn ( n − 1 ) m 2 ) = ( 1 − p ) ( 4 n ( n − 1 ) m ) = O ( n 2 m ) .
Conclusion
The game we considered can be best thought of as the graph-coloring game on K n K_n K n with m m m colors, where 2 ≤ m < n 2 \le m < n 2 ≤ m < n . We found an optimal synchronous classical strategy and proved its optimality across all classical strategies when p p p , the probability that inputs are equal, is at least 2 m + 2 \frac{2}{m+2} m + 2 2 . We then constructed an optimal synchronous quantum strategy and proved its optimality across all quantum strategies when p ≥ 2 n − m ( m + 2 ) n − 2 m p \ge\frac{2n-m}{(m+2)n-2m} p ≥ ( m + 2 ) n − 2 m 2 n − m . We thus found the classical and quantum synchronous values of this game, and the general classical and quantum values for the aforementioned thresholds on p p p , as well as the quantum advantage over classical strategies (by difference in value) when p ≥ 2 m + 2 p \ge\frac{2}{m+2} p ≥ m + 2 2 , which equals 0 if and only if m m m divides n n n .
Open Problems
We have not yet found which quantum strategies are optimal for p < 2 n − m ( m + 2 ) n − 2 m p < \frac{2n-m}{(m+2)n-2m} p < ( m + 2 ) n − 2 m 2 n − m , nor have we found a closed form for the classical optimum when p < 2 m + 2 p < \frac{2}{m+2} p < m + 2 2 . We know that both classical and quantum synchronous strategies are suboptimal in at least some of these cases but have found neither a general optimal strategy for these cases nor the value of p p p below which synchronous strategies become suboptimal.
Another interesting question is if the optimal quantum success probability is achievable using less entanglement than our strategy (which uses log 2 ( m ) \log_2(m) log 2 ( m ) ebits), or if log 2 ( m ) \log_2(m) log 2 ( m ) is optimal.
Finally, numerical simulations suggest that it may be possible to achieve the optimal quantum success probability with the same amount of entanglement using only real orthogonal transformations (as opposed to complex unitaries).
Acknowledgements
We thank Dr. Scott Aaronson (UT Austin) for suggesting we investigate this problem and providing continued support in revising this paper.
We also thank Dr. Venkat Arun (UT Austin) for discussing this problem with us and correcting an error in our initial construction.
AI Use Statement
ChatGPT and Claude were consulted at various points during this project to assist with ideation and literature review. In addition, Lemmas 4.4.1 , 4.4.2 , and B.0.1 , as well as Theorems 4.4.3 , and B.0.3 were originally shown by a mixture of ChatGPT Astra 6 and Claude Opus 5.5 in response to our prompting. The final versions of all proofs in this paper are human-written and the authors take full responsibility for all work in this paper.
Deriving our Strategy
We consider a particular class of strategies where Alice and Bob share the maximally entangled m m m -dimensional Bell state ∣ ψ ⟩ : = 1 m ∑ k = 0 m − 1 ∣ k ⟩ ∣ k ⟩ |\psi\rangle:= \frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}|k\rangle|k\rangle ∣ ψ ⟩ := m 1 ∑ k = 0 m − 1 ∣ k ⟩ ∣ k ⟩ , apply the unitaries A ( x ) A(x) A ( x ) and B ( y ) B(y) B ( y ) when they receive inputs x x x and y y y , respectively, then output the result of measuring their part in the computational basis.
The state they jointly measure is then given by
∣ ψ ⟩ x y : = ( A ( x ) ⊗ B ( y ) ) ∣ ψ ⟩ = 1 m ∑ k = 0 m − 1 ( A ( x ) ∣ k ⟩ ) ⊗ ( B ( y ) ∣ k ⟩ ) = 1 m ∑ k = 0 m − 1 ( ( ∑ a = 0 m − 1 A ( x ) a k ∣ a ⟩ ) ⊗ ( ∑ b = 0 m − 1 B ( y ) b k ∣ b ⟩ ) ) = 1 m ∑ k = 0 m − 1 ∑ a = 0 m − 1 ∑ b = 0 m − 1 A ( x ) a k B ( y ) b k ∣ a ⟩ ∣ b ⟩ = 1 m ∑ a = 0 m − 1 ∑ b = 0 m − 1 ∑ k = 0 m − 1 A ( x ) a k B ( y ) b k ∣ a b ⟩ = 1 m ∑ a = 0 m − 1 ∑ b = 0 m − 1 ⟨ A ( x ) a ∗ ∣ B ( y ) b ⟩ ∣ a b ⟩ = ∑ a = 0 m − 1 ∑ b = 0 m − 1 1 m ⟨ A ( x ) a ∗ ∣ B ( y ) b ⟩ ∣ a b ⟩ . \begin{aligned}
|\psi\rangle_{xy} &:= (A(x)\otimes B(y))|\psi\rangle\\
&= \frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}(A(x)|k\rangle)\otimes(B(y)|k\rangle) \\
&= \frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\left(\left(\sum_{a=0}^{m-1}A(x)_{ak}|a\rangle\right)\otimes\left(\sum_{b=0}^{m-1}B(y)_{bk}|b\rangle\right)\right) \\
&= \frac{1}{\sqrt{m}}\sum_{k=0}^{m-1}\sum_{a=0}^{m-1}\sum_{b=0}^{m-1}A(x)_{ak}B(y)_{bk}|a\rangle|b\rangle\\
&= \frac{1}{\sqrt{m}}\sum_{a=0}^{m-1}\sum_{b=0}^{m-1}\sum_{k=0}^{m-1}A(x)_{ak}B(y)_{bk}|ab\rangle\\
&= \frac{1}{\sqrt{m}}\sum_{a=0}^{m-1}\sum_{b=0}^{m-1}\langle A(x)^{*}_{a}\mid B(y)_{b}\rangle|ab\rangle\\
&= \sum_{a=0}^{m-1}\sum_{b=0}^{m-1}\frac{1}{\sqrt{m}}\langle A(x)^{*}_{a}\mid B(y)_{b}\rangle|ab\rangle.
\end{aligned} ∣ ψ ⟩ x y := ( A ( x ) ⊗ B ( y )) ∣ ψ ⟩ = m 1 k = 0 ∑ m − 1 ( A ( x ) ∣ k ⟩) ⊗ ( B ( y ) ∣ k ⟩) = m 1 k = 0 ∑ m − 1 ( ( a = 0 ∑ m − 1 A ( x ) ak ∣ a ⟩ ) ⊗ ( b = 0 ∑ m − 1 B ( y ) bk ∣ b ⟩ ) ) = m 1 k = 0 ∑ m − 1 a = 0 ∑ m − 1 b = 0 ∑ m − 1 A ( x ) ak B ( y ) bk ∣ a ⟩ ∣ b ⟩ = m 1 a = 0 ∑ m − 1 b = 0 ∑ m − 1 k = 0 ∑ m − 1 A ( x ) ak B ( y ) bk ∣ ab ⟩ = m 1 a = 0 ∑ m − 1 b = 0 ∑ m − 1 ⟨ A ( x ) a ∗ ∣ B ( y ) b ⟩ ∣ ab ⟩ = a = 0 ∑ m − 1 b = 0 ∑ m − 1 m 1 ⟨ A ( x ) a ∗ ∣ B ( y ) b ⟩ ∣ ab ⟩ .
The probability that Alice and Bob give equal outputs is the sum of the squared amplitudes corresponding to basis states of the form ∣ k k ⟩ |kk\rangle ∣ k k ⟩ , so
ξ = ∑ x = 0 n − 1 ∑ k = 0 m − 1 ∣ 1 m ⟨ A ( x ) k ∗ ∣ B ( x ) k ⟩ ∣ 2 = 1 m ∑ x = 0 n − 1 ∑ k = 0 m − 1 ∣ ⟨ A ( x ) k ∗ ∣ B ( x ) k ⟩ ∣ 2 . \xi=\sum_{x=0}^{n-1}\sum_{k=0}^{m-1}\left|\frac{1}{\sqrt{m}}\langle A(x)^{*}_{k}\mid B(x)_{k}\rangle\right|^{2}=\frac{1}{m}\sum_{x=0}^{n-1}\sum_{k=0}^{m-1}\left|\langle A(x)^{*}_{k}\mid B(x)_{k}\rangle\right|^{2}. ξ = x = 0 ∑ n − 1 k = 0 ∑ m − 1 m 1 ⟨ A ( x ) k ∗ ∣ B ( x ) k ⟩ 2 = m 1 x = 0 ∑ n − 1 k = 0 ∑ m − 1 ∣ ⟨ A ( x ) k ∗ ∣ B ( x ) k ⟩ ∣ 2 .
and
μ = ∑ x = 0 n − 1 ∑ y = 0 n − 1 ∑ k = 0 m − 1 ∣ 1 m ⟨ A ( x ) k ∗ ∣ B ( y ) k ⟩ ∣ 2 = 1 m ∑ x = 0 n − 1 ∑ y = 0 n − 1 ∑ k = 0 m − 1 ∣ ⟨ A ( x ) k ∗ ∣ B ( y ) k ⟩ ∣ 2 . \mu=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}\sum_{k=0}^{m-1}\left|\frac{1}{\sqrt{m}}\langle A(x)^{*}_{k}\mid B(y)_{k}\rangle\right|^{2}=\frac{1}{m}\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}\sum_{k=0}^{m-1}\left|\langle A(x)^{*}_{k}\mid B(y)_{k}\rangle\right|^{2}. μ = x = 0 ∑ n − 1 y = 0 ∑ n − 1 k = 0 ∑ m − 1 m 1 ⟨ A ( x ) k ∗ ∣ B ( y ) k ⟩ 2 = m 1 x = 0 ∑ n − 1 y = 0 ∑ n − 1 k = 0 ∑ m − 1 ∣ ⟨ A ( x ) k ∗ ∣ B ( y ) k ⟩ ∣ 2 .
Synchronous Quantum Strategies
If B ( y ) = A ( x ) ∗ B(y)=A(x)^{*} B ( y ) = A ( x ) ∗ , the amplitude of ∣ a b ⟩ |ab\rangle ∣ ab ⟩ is 1 m ⟨ B ( y ) a ∣ B ( y ) b ⟩ \frac{1}{\sqrt{m}}\langle B(y)_{a}\mid B(y)_{b}\rangle m 1 ⟨ B ( y ) a ∣ B ( y ) b ⟩ , which equals 1 m \frac{1}{\sqrt{m}} m 1 if a = b a=b a = b and 0 0 0 otherwise, since B ( y ) B(y) B ( y ) is unitary. Hence, Alice and Bob will always measure ∣ k k ⟩ |kk\rangle ∣ k k ⟩ for some k ∈ [ m ] k\in[m] k ∈ [ m ] and so give the same output. Therefore, any strategy with B ( x ) = A ( x ) ∗ B(x)=A(x)^{*} B ( x ) = A ( x ) ∗ for all x ∈ [ n ] x\in[n] x ∈ [ n ] is synchronous.
We then seek to minimize μ \mu μ , or equivalently its constant multiple
m μ = ∑ x = 0 n − 1 ∑ y = 0 n − 1 ∑ k = 0 m − 1 ∣ ⟨ B ( x ) k ∣ B ( y ) k ⟩ ∣ 2 . m\mu=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}\sum_{k=0}^{m-1}\left|\langle B(x)_{k}\mid B(y)_{k}\rangle\right|^{2}. m μ = x = 0 ∑ n − 1 y = 0 ∑ n − 1 k = 0 ∑ m − 1 ∣ ⟨ B ( x ) k ∣ B ( y ) k ⟩ ∣ 2 .
Vector Packing Problem
Since B ( x ) k B(x)_k B ( x ) k is a unit vector for each x ∈ [ n ] x \in[n] x ∈ [ n ] and k ∈ [ m ] k \in[m] k ∈ [ m ] , we must have
∑ x = 0 n − 1 ∑ y = 0 n − 1 ∣ ⟨ B ( x ) k ∣ B ( y ) k ⟩ ∣ 2 > n \sum_{x=0}^{n-1}\sum_{y=0}^{n-1} \left|\langle B(x)_k \mid B(y)_k\rangle\right|^2 > n x = 0 ∑ n − 1 y = 0 ∑ n − 1 ∣ ⟨ B ( x ) k ∣ B ( y ) k ⟩ ∣ 2 > n
for all k ∈ [ m ] k \in[m] k ∈ [ m ] : otherwise, { B ( x ) k ∣ x ∈ [ n ] } \{B(x)_k \mid x \in[n]\} { B ( x ) k ∣ x ∈ [ n ]} would be a set of n n n orthogonal vectors in an m m m -dimensional space with m < n m < n m < n .
As such, we attempt to minimize ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}|\langle v_i \mid v_j\rangle|^2 ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 across all sets of n n n unit vectors V ∈ ( C m ) n ≅ C m × n V \in(\mathbb{C}^m)^n \cong\mathbb{C}^{m \times n} V ∈ ( C m ) n ≅ C m × n . This presents a “vector packing” problem, since our objective function discourages correlation between vectors.
By the definition of the matrix product, ⟨ v i ∣ v j ⟩ = ( V † V ) i j \langle v_i \mid v_j\rangle= (V^\dagger V)_{ij} ⟨ v i ∣ v j ⟩ = ( V † V ) ij for all i i i and j j j . Tracing along the main diagonal (i.e., in the computational basis) gives
tr ( V † V ) = ∑ i = 0 n − 1 ( V † V ) i i = ∑ i = 0 n − 1 ⟨ v i ∣ v i ⟩ = ∑ i = 0 n − 1 ∥ v i ∥ 2 = ∑ i = 0 n − 1 1 = n . \operatorname{tr}(V^\dagger V)=\sum_{i=0}^{n-1}(V^\dagger V)_{ii}=\sum_{i=0}^{n-1}\langle v_i\mid v_i\rangle=\sum_{i=0}^{n-1}\|v_i\|^2=\sum_{i=0}^{n-1}1=n. tr ( V † V ) = i = 0 ∑ n − 1 ( V † V ) ii = i = 0 ∑ n − 1 ⟨ v i ∣ v i ⟩ = i = 0 ∑ n − 1 ∥ v i ∥ 2 = i = 0 ∑ n − 1 1 = n .
By singular value decomposition, V = U Σ W V=U\Sigma W V = U Σ W for some unitary U ∈ C m × m U \in\mathbb{C}^{m \times m} U ∈ C m × m , unitary W ∈ C n × n W \in\mathbb{C}^{n \times n} W ∈ C n × n , and nonnegative real diagonal Σ ∈ C m × n \Sigma\in\mathbb{C}^{m \times n} Σ ∈ C m × n , so
V † V = ( U Σ W ) † ( U Σ W ) = W † Σ † U † U Σ W = W † Σ T Σ W . V^\dagger V=(U\Sigma W)^\dagger(U\Sigma W)=W^\dagger\Sigma^\dagger U^\dagger U\Sigma W=W^\dagger\Sigma^T\Sigma W. V † V = ( U Σ W ) † ( U Σ W ) = W † Σ † U † U Σ W = W † Σ T Σ W .
Hence, since traces are invariant under conjugation by unitaries like W W W ,
n = tr ( V † V ) = tr ( W † Σ T Σ W ) = tr ( Σ T Σ ) = ∑ i = 0 m − 1 ( Σ i i ) 2 . n=\operatorname{tr}(V^\dagger V)=\operatorname{tr}(W^\dagger\Sigma^T\Sigma W)=\operatorname{tr}(\Sigma^T\Sigma)=\sum_{i=0}^{m-1}(\Sigma_{ii})^2. n = tr ( V † V ) = tr ( W † Σ T Σ W ) = tr ( Σ T Σ ) = i = 0 ∑ m − 1 ( Σ ii ) 2 .
For all i i i and j j j ,
∣ ⟨ v i ∣ v j ⟩ ∣ 2 = ⟨ v i ∣ v j ⟩ ⟨ v i ∣ v j ⟩ ∗ = ⟨ v i ∣ v j ⟩ ⟨ v j ∣ v i ⟩ = ( V † V ) i j ( V † V ) j i , |\langle v_i\mid v_j\rangle|^2=\langle v_i\mid v_j\rangle\langle v_i\mid v_j\rangle^*=\langle v_i\mid v_j\rangle\langle v_j\mid v_i\rangle=(V^\dagger V)_{ij}(V^\dagger V)_{ji}, ∣ ⟨ v i ∣ v j ⟩ ∣ 2 = ⟨ v i ∣ v j ⟩ ⟨ v i ∣ v j ⟩ ∗ = ⟨ v i ∣ v j ⟩ ⟨ v j ∣ v i ⟩ = ( V † V ) ij ( V † V ) j i ,
so
∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 = ∑ i = 0 n − 1 ∑ j = 0 n − 1 ( V † V ) i j ( V † V ) j i = ∑ i = 0 n − 1 ( ( V † V ) 2 ) i i = tr ( ( V † V ) 2 ) . \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}|\langle v_i\mid v_j\rangle|^2=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}(V^\dagger V)_{ij}(V^\dagger V)_{ji}=\sum_{i=0}^{n-1}((V^\dagger V)^2)_{ii}=\operatorname{tr}((V^\dagger V)^2). i = 0 ∑ n − 1 j = 0 ∑ n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 = i = 0 ∑ n − 1 j = 0 ∑ n − 1 ( V † V ) ij ( V † V ) j i = i = 0 ∑ n − 1 (( V † V ) 2 ) ii = tr (( V † V ) 2 ) .
Since W W W is unitary, W W † = I WW^\dagger=I W W † = I , so
( V † V ) 2 = ( W † Σ T Σ W ) 2 = W † Σ T Σ W W † Σ T Σ W = W † ( Σ T Σ ) 2 W . (V^\dagger V)^2=(W^\dagger\Sigma^T\Sigma W)^2=W^\dagger\Sigma^T\Sigma WW^\dagger\Sigma^T\Sigma W=W^\dagger(\Sigma^T\Sigma)^2W. ( V † V ) 2 = ( W † Σ T Σ W ) 2 = W † Σ T Σ W W † Σ T Σ W = W † ( Σ T Σ ) 2 W .
Thus, again using that the trace is invariant under conjugation by W W W ,
tr ( ( V † V ) 2 ) = tr ( W † ( Σ T Σ ) 2 W ) = tr ( ( Σ T Σ ) 2 ) = ∑ i = 0 m − 1 ( ( Σ T Σ ) 2 ) i i . \operatorname{tr}((V^\dagger V)^2)=\operatorname{tr}(W^\dagger(\Sigma^T\Sigma)^2W)=\operatorname{tr}((\Sigma^T\Sigma)^2)=\sum_{i=0}^{m-1}((\Sigma^T\Sigma)^2)_{ii}. tr (( V † V ) 2 ) = tr ( W † ( Σ T Σ ) 2 W ) = tr (( Σ T Σ ) 2 ) = i = 0 ∑ m − 1 (( Σ T Σ ) 2 ) ii .
Σ \Sigma Σ and hence Σ T Σ \Sigma^{\mathsf{T}}\Sigma Σ T Σ and ( Σ T Σ ) 2 (\Sigma^{\mathsf{T}}\Sigma)^2 ( Σ T Σ ) 2 are diagonal, so for all i i i ,
( ( Σ T Σ ) 2 ) i i = ( ( Σ T Σ ) i i ) 2 = ( ( Σ i i 2 ) ) 2 . \left((\Sigma^{\mathsf{T}}\Sigma)^2\right)_{ii}=\left((\Sigma^{\mathsf{T}}\Sigma)_{ii}\right)^2=\left((\Sigma_{ii}^2)\right)^2. ( ( Σ T Σ ) 2 ) ii = ( ( Σ T Σ ) ii ) 2 = ( ( Σ ii 2 ) ) 2 .
Letting λ i : = Σ i i 2 \lambda_i := \Sigma_{ii}^2 λ i := Σ ii 2 for each i ∈ [ m ] i \in[m] i ∈ [ m ] , we then wish to minimize ∑ i = 0 m − 1 λ i 2 \sum_{i=0}^{m-1}\lambda_i^2 ∑ i = 0 m − 1 λ i 2 subject to the constraint ∑ i = 0 m − 1 λ i = n \sum_{i=0}^{m-1}\lambda_i=n ∑ i = 0 m − 1 λ i = n (and λ i ≥ 0 \lambda_i \ge0 λ i ≥ 0 for all i ∈ [ m ] i \in[m] i ∈ [ m ] ).
By the Cauchy-Schwarz inequality on the standard inner product on R m \mathbb{R}^m R m ,
m ( ∑ i = 0 m − 1 λ i 2 ) = ( ∑ i = 0 m − 1 1 2 ) ( ∑ i = 0 m − 1 λ i 2 ) ≥ ( ∑ i = 0 m − 1 1 ⋅ λ i ) 2 = ( ∑ i = 0 m − 1 λ i ) 2 = n 2 . m\left(\sum_{i=0}^{m-1}\lambda_i^2\right)=\left(\sum_{i=0}^{m-1}1^2\right)\left(\sum_{i=0}^{m-1}\lambda_i^2\right)\ge\left(\sum_{i=0}^{m-1}1\cdot\lambda_i\right)^2=\left(\sum_{i=0}^{m-1}\lambda_i\right)^2=n^2. m ( i = 0 ∑ m − 1 λ i 2 ) = ( i = 0 ∑ m − 1 1 2 ) ( i = 0 ∑ m − 1 λ i 2 ) ≥ ( i = 0 ∑ m − 1 1 ⋅ λ i ) 2 = ( i = 0 ∑ m − 1 λ i ) 2 = n 2 .
Hence, ∑ i = 0 m − 1 λ i 2 ≥ n 2 m \sum_{i=0}^{m-1}\lambda_i^2 \ge\frac{n^2}{m} ∑ i = 0 m − 1 λ i 2 ≥ m n 2 , and the inequality is saturated if and only if the vector with each entry i i i equal to λ i \lambda_i λ i is parallel to the vector with all entries equal to 1 1 1 , which requires that all λ i \lambda_i λ i be equal to the same λ ∈ R \lambda\in\mathbb{R} λ ∈ R . Then using our constraint, n = ∑ i = 0 m − 1 λ i = ∑ i = 0 m − 1 λ = m λ n=\sum_{i=0}^{m-1}\lambda_i=\sum_{i=0}^{m-1}\lambda=m\lambda n = ∑ i = 0 m − 1 λ i = ∑ i = 0 m − 1 λ = mλ , so λ = n m \lambda=\frac{n}{m} λ = m n . Thus, Σ i i = λ i = λ = n m \Sigma_{ii}=\sqrt{\lambda_i}=\sqrt{\lambda}=\sqrt{\frac{n}{m}} Σ ii = λ i = λ = m n for all i ∈ [ m ] i \in[m] i ∈ [ m ] .
However, we must choose W W W to make every diagonal entry of V † V V^\dagger V V † V equal 1 1 1 , not merely their sum equal n n n : i.e., 1 = ( V † V ) i i = ( W † Σ T Σ W ) i i 1=(V^\dagger V)_{ii}=(W^\dagger\Sigma^{\mathsf{T}}\Sigma W)_{ii} 1 = ( V † V ) ii = ( W † Σ T Σ W ) ii for all i i i .
Since Σ T Σ \Sigma^{\mathsf{T}}\Sigma Σ T Σ is diagonal with ( Σ T Σ ) j j = Σ j j 2 = λ j = n m (\Sigma^{\mathsf{T}}\Sigma)_{jj}=\Sigma_{jj}^2=\lambda_j=\frac{n}{m} ( Σ T Σ ) j j = Σ j j 2 = λ j = m n for j < m j<m j < m and ( Σ T Σ ) j j = 0 (\Sigma^{\mathsf{T}}\Sigma)_{jj}=0 ( Σ T Σ ) j j = 0 for j ≥ m j\ge m j ≥ m ,
( W † Σ T Σ W ) i i = ∑ j = 0 m − 1 ( W † ) i j ( Σ T Σ ) j j W j i = ∑ j = 0 m − 1 W j i ∗ ( n m ) W j i = n m ∑ j = 0 m − 1 W j i ∗ W j i . (W^\dagger\Sigma^{\mathsf{T}}\Sigma W)_{ii}=\sum_{j=0}^{m-1}(W^\dagger)_{ij}(\Sigma^{\mathsf{T}}\Sigma)_{jj}W_{ji}=\sum_{j=0}^{m-1}W_{ji}^*\left(\frac{n}{m}\right)W_{ji}=\frac{n}{m}\sum_{j=0}^{m-1}W_{ji}^*W_{ji}. ( W † Σ T Σ W ) ii = j = 0 ∑ m − 1 ( W † ) ij ( Σ T Σ ) j j W j i = j = 0 ∑ m − 1 W j i ∗ ( m n ) W j i = m n j = 0 ∑ m − 1 W j i ∗ W j i .
This sum is just the squared length of the vector given by the top m m m entries of column i i i of W W W . As such, our desired unitaries W W W are exactly those whose uppermost m × n m\times n m × n submatrices have column vectors of squared length m n \frac{m}{n} n m each, which since the rows of a unitary must all have squared norm 1 1 1 is the only possible length they could have if they all have equal length.
The matrix U U U in the singular value decomposition of V V V is unconstrained here, which makes sense because applying unitary operators to the columns of V V V preserves their inner products and hence the value of the objective function. One obvious choice of W W W that satisfies these constraints is the discrete Fourier transform matrix F n ∈ C n × n F_n \in\mathbb{C}^{n\times n} F n ∈ C n × n , where ( F n ) x y : = ω n x y n (F_n)_{xy}:=\frac{\omega_n^{xy}}{\sqrt{n}} ( F n ) x y := n ω n x y with ω n : = e 2 π i / n \omega_n:=e^{2\pi i/n} ω n := e 2 π i / n : all its entries and thus all its truncated columns have equal magnitude.
Trying the Fourier vectors
Indeed, if v i : = n m F i v_i := \sqrt{\frac{n}{m}}F_i v i := m n F i is the normalized i th i^{\text{th}} i th column of F n F_n F n truncated to the top m m m entries,
∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 = ∑ i = 0 n − 1 ∑ j = 0 n − 1 ⟨ v i ∣ v j ⟩ ∗ ⟨ v i ∣ v j ⟩ = ∑ i = 0 n − 1 ∑ j = 0 n − 1 ( 1 m ∑ k = 0 m − 1 ( ω n k i ) ∗ ω n k j ) ( 1 m ∑ l = 0 m − 1 ( ω n l i ) ∗ ω n l j ) = 1 m 2 ∑ i = 0 n − 1 ∑ j = 0 n − 1 ( ∑ k = 0 m − 1 ω n k i − k j ) ( ∑ l = 0 m − 1 ω n − l i + l j ) = 1 m 2 ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ω n k i − k j ω n − l i + l j = 1 m 2 ∑ i = 0 n − 1 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ∑ j = 0 n − 1 ω n ( j − i ) ( l − k ) . \begin{aligned}
\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} \left|\langle v_i \mid v_j\rangle\right|^2
&= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} \langle v_i \mid v_j\rangle^* \langle v_i \mid v_j\rangle\\
&= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} \left(\frac{1}{m}\sum_{k=0}^{m-1}(\omega_n^{ki})^*\omega_n^{kj}\right)\left(\frac{1}{m}\sum_{l=0}^{m-1}(\omega_n^{li})^*\omega_n^{lj}\right) \\
&= \frac{1}{m^2}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\left(\sum_{k=0}^{m-1}\omega_n^{ki-kj}\right)\left(\sum_{l=0}^{m-1}\omega_n^{-li+lj}\right) \\
&= \frac{1}{m^2}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\omega_n^{ki-kj}\omega_n^{-li+lj} \\
&= \frac{1}{m^2}\sum_{i=0}^{n-1}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\sum_{j=0}^{n-1}\omega_n^{(j-i)(l-k)}.
\end{aligned} i = 0 ∑ n − 1 j = 0 ∑ n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 = i = 0 ∑ n − 1 j = 0 ∑ n − 1 ⟨ v i ∣ v j ⟩ ∗ ⟨ v i ∣ v j ⟩ = i = 0 ∑ n − 1 j = 0 ∑ n − 1 ( m 1 k = 0 ∑ m − 1 ( ω n k i ) ∗ ω n k j ) ( m 1 l = 0 ∑ m − 1 ( ω n l i ) ∗ ω n l j ) = m 2 1 i = 0 ∑ n − 1 j = 0 ∑ n − 1 ( k = 0 ∑ m − 1 ω n k i − k j ) ( l = 0 ∑ m − 1 ω n − l i + l j ) = m 2 1 i = 0 ∑ n − 1 j = 0 ∑ n − 1 k = 0 ∑ m − 1 l = 0 ∑ m − 1 ω n k i − k j ω n − l i + l j = m 2 1 i = 0 ∑ n − 1 k = 0 ∑ m − 1 l = 0 ∑ m − 1 j = 0 ∑ n − 1 ω n ( j − i ) ( l − k ) .
If l = k l=k l = k , we have ∑ j = 0 n − 1 ω n ( j − i ) ( l − k ) = ∑ j = 0 n − 1 ω n 0 = ∑ j = 0 n − 1 1 = n \sum_{j=0}^{n-1}\omega_n^{(j-i)(l-k)}=\sum_{j=0}^{n-1}\omega_n^0=\sum_{j=0}^{n-1}1=n ∑ j = 0 n − 1 ω n ( j − i ) ( l − k ) = ∑ j = 0 n − 1 ω n 0 = ∑ j = 0 n − 1 1 = n .
Otherwise, ω n l − k ≠ 1 \omega_n^{l-k}\ne1 ω n l − k = 1 , so the terms in the sum interfere and
∑ j = 0 n − 1 ω n ( j − i ) ( l − k ) = ∑ j = 0 n − 1 ω n j ( l − k ) ω n − i ( l − k ) = ω n − i ( l − k ) ∑ j = 0 n − 1 ( ω n l − k ) j = ω n − i ( l − k ) ( 1 − ( ω n l − k ) n 1 − ω n l − k ) = ω n − i ( l − k ) 1 − ω n l − k ( 1 − ( ω n n ) l − k ) = ω n − i ( l − k ) 1 − ω n l − k ( 1 − 1 l − k ) = 0. \begin{aligned}
\sum_{j=0}^{n-1}\omega_n^{(j-i)(l-k)}
&= \sum_{j=0}^{n-1}\omega_n^{j(l-k)}\omega_n^{-i(l-k)} \\
&= \omega_n^{-i(l-k)}\sum_{j=0}^{n-1}\left(\omega_n^{l-k}\right)^j \\
&= \omega_n^{-i(l-k)}\left(\frac{1-\left(\omega_n^{l-k}\right)^n}{1-\omega_n^{l-k}}\right) \\
&= \frac{\omega_n^{-i(l-k)}}{1-\omega_n^{l-k}}\left(1-\left(\omega_n^n\right)^{l-k}\right) \\
&= \frac{\omega_n^{-i(l-k)}}{1-\omega_n^{l-k}}\left(1-1^{l-k}\right)=0.
\end{aligned} j = 0 ∑ n − 1 ω n ( j − i ) ( l − k ) = j = 0 ∑ n − 1 ω n j ( l − k ) ω n − i ( l − k ) = ω n − i ( l − k ) j = 0 ∑ n − 1 ( ω n l − k ) j = ω n − i ( l − k ) ( 1 − ω n l − k 1 − ( ω n l − k ) n ) = 1 − ω n l − k ω n − i ( l − k ) ( 1 − ( ω n n ) l − k ) = 1 − ω n l − k ω n − i ( l − k ) ( 1 − 1 l − k ) = 0.
Hence, ∑ j = 0 n − 1 ∑ l = 0 m − 1 ω n ( j − i ) ( l − k ) = n \sum_{j=0}^{n-1}\sum_{l=0}^{m-1}\omega_n^{(j-i)(l-k)}=n ∑ j = 0 n − 1 ∑ l = 0 m − 1 ω n ( j − i ) ( l − k ) = n for all i ∈ [ n ] i\in[n] i ∈ [ n ] and k ∈ [ m ] k\in[m] k ∈ [ m ] , so
∑ i = 0 n − 1 ∑ k = 0 m − 1 ∑ l = 0 m − 1 ∑ j = 0 n − 1 ω n ( j − i ) ( l − k ) = ∑ i = 0 n − 1 ∑ k = 0 m − 1 n = m n 2 \sum_{i=0}^{n-1}\sum_{k=0}^{m-1}\sum_{l=0}^{m-1}\sum_{j=0}^{n-1}\omega_n^{(j-i)(l-k)}
=\sum_{i=0}^{n-1}\sum_{k=0}^{m-1}n=mn^2 i = 0 ∑ n − 1 k = 0 ∑ m − 1 l = 0 ∑ m − 1 j = 0 ∑ n − 1 ω n ( j − i ) ( l − k ) = i = 0 ∑ n − 1 k = 0 ∑ m − 1 n = m n 2
and therefore ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 = m n 2 m 2 = n 2 m \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\left|\langle v_i\mid v_j\rangle\right|^2=\frac{mn^2}{m^2}=\frac{n^2}{m} ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ v i ∣ v j ⟩ ∣ 2 = m 2 m n 2 = m n 2 , as desired.
Extending to Unitary Bases
To extend these vectors to a set of bases that minimize the objective, we let each v i v_i v i be the first row of the basis B ( i ) B(i) B ( i ) . Since unitaries are closed under the operation of multiplying columns by phases, we hope that our bases will be identical apart from the Fourier phases applied to each column: then
⟨ B ( x ) k ∣ B ( y ) k ⟩ = ∑ l = 0 m − 1 B ( x ) k l ∗ B ( y ) k l = ∑ l = 0 m − 1 ( B ( 0 ) k l ω n l x ) ∗ B ( 0 ) k l ω n l y = ∑ l = 0 m − 1 ∣ B ( 0 ) k l ∣ 2 ω n l ( y − x ) \langle B(x)_k \mid B(y)_k \rangle= \sum_{l=0}^{m-1} B(x)_{kl}^{*}B(y)_{kl} = \sum_{l=0}^{m-1} \left(B(0)_{kl}\omega_n^{lx}\right)^{*}B(0)_{kl}\omega_n^{ly} = \sum_{l=0}^{m-1} \lvert B(0)_{kl}\rvert^2\omega_n^{l(y-x)} ⟨ B ( x ) k ∣ B ( y ) k ⟩ = l = 0 ∑ m − 1 B ( x ) k l ∗ B ( y ) k l = l = 0 ∑ m − 1 ( B ( 0 ) k l ω n l x ) ∗ B ( 0 ) k l ω n l y = l = 0 ∑ m − 1 ∣ B ( 0 ) k l ∣ 2 ω n l ( y − x )
for any row index k k k and any inputs x x x and y y y : the inner products depend only on the magnitudes of the entries of the chosen “template basis” B ( 0 ) B(0) B ( 0 ) .
Hence, if each entry B ( 0 ) k l B(0)_{kl} B ( 0 ) k l satisfies ∣ B ( 0 ) k l ∣ = ∣ B ( 0 ) 0 l ∣ = 1 m \lvert B(0)_{kl}\rvert= \lvert B(0)_{0l}\rvert= \frac{1}{\sqrt{m}} ∣ B ( 0 ) k l ∣ = ∣ B ( 0 ) 0 l ∣ = m 1 ,
∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ B ( i ) k ∣ B ( j ) k ⟩ ∣ 2 = ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ B ( i ) 0 ∣ B ( j ) 0 ⟩ ∣ 2 = n 2 m \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\lvert\langle B(i)_k \mid B(j)_k\rangle\rvert^2 = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\lvert\langle B(i)_0 \mid B(j)_0\rangle\rvert^2 = \frac{n^2}{m} i = 0 ∑ n − 1 j = 0 ∑ n − 1 ∣⟨ B ( i ) k ∣ B ( j ) k ⟩ ∣ 2 = i = 0 ∑ n − 1 j = 0 ∑ n − 1 ∣⟨ B ( i ) 0 ∣ B ( j ) 0 ⟩ ∣ 2 = m n 2
for each row index k k k , so our objective ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∑ k = 0 m − 1 ∣ ⟨ B ( i ) k ∣ B ( j ) k ⟩ ∣ 2 \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{k=0}^{m-1}\lvert\langle B(i)_k \mid B(j)_k\rangle\rvert^2 ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∑ k = 0 m − 1 ∣⟨ B ( i ) k ∣ B ( j ) k ⟩ ∣ 2 will equal
∑ k = 0 m − 1 ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∣ ⟨ B ( i ) k ∣ B ( j ) k ⟩ ∣ 2 = ∑ k = 0 m − 1 n 2 m = m ⋅ n 2 m = n 2 . \sum_{k=0}^{m-1}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\lvert\langle B(i)_k \mid B(j)_k\rangle\rvert^2 = \sum_{k=0}^{m-1}\frac{n^2}{m} = m\cdot\frac{n^2}{m}=n^2. k = 0 ∑ m − 1 i = 0 ∑ n − 1 j = 0 ∑ n − 1 ∣⟨ B ( i ) k ∣ B ( j ) k ⟩ ∣ 2 = k = 0 ∑ m − 1 m n 2 = m ⋅ m n 2 = n 2 .
We thus seek any m × m m\times m m × m unitary whose every entry has magnitude 1 m \frac{1}{\sqrt{m}} m 1 . A convenient such choice for B ( 0 ) B(0) B ( 0 ) is the Fourier matrix F m ∈ C m × m F_m\in\mathbb{C}^{m\times m} F m ∈ C m × m .
Proof of Synchronous Optimality for p ≥ 1 2 p \ge\frac{1}{2} p ≥ 2 1
Lemma B.0.1. Any valid quantum strategy has n ξ − μ ≤ n 2 ( 1 − 1 m ) n\xi-\mu\le n^2\left(1-\frac{1}{m}\right) n ξ − μ ≤ n 2 ( 1 − m 1 ) .
Proof. Let ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ be the state shared by Alice and Bob, and let { A x a } a \{A_x^a\}_a { A x a } a , { B y b } b \{B_y^b\}_b { B y b } b be Alice’s and Bob’s projective measurements, respectively. We then define the following symbols:
u x a = ( A x a ⊗ I ) ∣ ψ ⟩ u_{xa}=(A_x^a\otimes I)\lvert\psi\rangle u x a = ( A x a ⊗ I ) ∣ ψ ⟩
v y b = ( I ⊗ B y b ) ∣ ψ ⟩ v_{yb}=(I\otimes B_y^b)\lvert\psi\rangle v y b = ( I ⊗ B y b ) ∣ ψ ⟩
u ‾ a = 1 n ∑ x u x a \overline{u}_a=\frac{1}{n}\sum_x u_{xa} u a = n 1 x ∑ u x a
v ‾ b = 1 n ∑ y v y b \overline{v}_b=\frac{1}{n}\sum_y v_{yb} v b = n 1 y ∑ v y b
Looking at the above symbols, we can see that the probability that outputs are equal for a given pair of inputs ( x , y ) (x,y) ( x , y ) is
c x y = ∑ a Pr ( a , a ∣ x , y ) = ∑ a ⟨ ψ ∣ A x a ⊗ B y a ∣ ψ ⟩ c_{xy} = \sum_a \Pr(a,a \mid x,y) = \sum_a \langle\psi| A_x^a \otimes B_y^a | \psi\rangle c x y = a ∑ Pr ( a , a ∣ x , y ) = a ∑ ⟨ ψ ∣ A x a ⊗ B y a ∣ ψ ⟩
A x a ⊗ B y a = ( A x a ⊗ I ) ( I ⊗ B y a ) A_x^a \otimes B_y^a = (A_x^a \otimes I)(I \otimes B_y^a) A x a ⊗ B y a = ( A x a ⊗ I ) ( I ⊗ B y a ) so
∑ a ⟨ ψ ∣ A x a ⊗ B y a ∣ ψ ⟩ = ∑ a ⟨ ψ ∣ ( A x a ⊗ I ) ( I ⊗ B y a ) ∣ ψ ⟩ \sum_a \langle\psi| A_x^a \otimes B_y^a | \psi\rangle= \sum_a \langle\psi| (A_x^a \otimes I)(I \otimes B_y^a) | \psi\rangle a ∑ ⟨ ψ ∣ A x a ⊗ B y a ∣ ψ ⟩ = a ∑ ⟨ ψ ∣ ( A x a ⊗ I ) ( I ⊗ B y a ) ∣ ψ ⟩
By the adjoint property, this is equivalent to
∑ a ⟨ ( ( A x a ) † ⊗ I † ) ψ ∣ ( I ⊗ B y a ) ψ ⟩ \sum_a \langle((A_x^a)^\dagger\otimes I^\dagger)\psi| (I \otimes B_y^a)\psi\rangle a ∑ ⟨(( A x a ) † ⊗ I † ) ψ ∣ ( I ⊗ B y a ) ψ ⟩
and since A x a A_x^a A x a is a projector and thus Hermitian, ( A x a ) † = ( A x a ) (A_x^a)^\dagger= (A_x^a) ( A x a ) † = ( A x a ) , so we have
∑ a ⟨ ( ( A x a ) † ⊗ I † ) ψ ∣ ( I ⊗ B y a ) ψ ⟩ = ∑ a ⟨ ( A x a ⊗ I ) ψ ∣ ( I ⊗ B y a ) ψ ⟩ = ∑ a ⟨ u x a ∣ v y a ⟩ \sum_a \langle((A_x^a)^\dagger\otimes I^\dagger)\psi| (I \otimes B_y^a)\psi\rangle= \sum_a \langle(A_x^a \otimes I)\psi| (I \otimes B_y^a)\psi\rangle= \sum_a \langle u_{xa} \mid v_{ya} \rangle a ∑ ⟨(( A x a ) † ⊗ I † ) ψ ∣ ( I ⊗ B y a ) ψ ⟩ = a ∑ ⟨( A x a ⊗ I ) ψ ∣ ( I ⊗ B y a ) ψ ⟩ = a ∑ ⟨ u x a ∣ v y a ⟩
and thus
c x y = ∑ a ⟨ u x a ∣ v y a ⟩ c_{xy} = \sum_a \langle u_{xa} \mid v_{ya} \rangle c x y = a ∑ ⟨ u x a ∣ v y a ⟩
It follows that
ξ = ∑ x , a ⟨ u x a ∣ v x a ⟩ \xi= \sum_{x,a} \langle u_{xa} \mid v_{xa} \rangle ξ = x , a ∑ ⟨ u x a ∣ v x a ⟩
and
μ = ∑ x , y , a ⟨ u x a ∣ v y a ⟩ \mu= \sum_{x,y,a} \langle u_{xa} \mid v_{ya} \rangle μ = x , y , a ∑ ⟨ u x a ∣ v y a ⟩
Note that ∑ y v y a = n v ˉ a \sum_y v_{ya} = n\bar{v}_a ∑ y v y a = n v ˉ a , and thus ∑ y ⟨ u x a ∣ v y a ⟩ = n ⟨ u x a ∣ v ˉ a ⟩ \sum_y \langle u_{xa} \mid v_{ya} \rangle= n \langle u_{xa} \mid\bar{v}_a \rangle ∑ y ⟨ u x a ∣ v y a ⟩ = n ⟨ u x a ∣ v ˉ a ⟩ . Thus,
μ = ∑ x , y , a ⟨ u x a ∣ v y a ⟩ = n ∑ x , a ⟨ u x a ∣ v ˉ a ⟩ \mu= \sum_{x,y,a} \langle u_{xa} \mid v_{ya} \rangle= n \sum_{x,a} \langle u_{xa} \mid\bar{v}_a \rangle μ = x , y , a ∑ ⟨ u x a ∣ v y a ⟩ = n x , a ∑ ⟨ u x a ∣ v ˉ a ⟩
We can now find an expression for n ξ − μ n\xi-\mu n ξ − μ :
n ξ − μ = n ∑ x , a ⟨ u x a ∣ v x a ⟩ − n ∑ x , a ⟨ u x a ∣ v ˉ a ⟩ = n ∑ x , a ⟨ u x a ∣ v x a − v ˉ a ⟩ n\xi-\mu= n \sum_{x,a} \langle u_{xa} \mid v_{xa} \rangle- n \sum_{x,a} \langle u_{xa} \mid\bar{v}_a \rangle= n \sum_{x,a} \langle u_{xa} \mid v_{xa} - \bar{v}_a \rangle n ξ − μ = n x , a ∑ ⟨ u x a ∣ v x a ⟩ − n x , a ∑ ⟨ u x a ∣ v ˉ a ⟩ = n x , a ∑ ⟨ u x a ∣ v x a − v ˉ a ⟩
Note that, for all a a a , ∑ x ⟨ u ˉ a ∣ v x a − v ˉ a ⟩ = ⟨ u ˉ a ∣ n v ˉ a − n v ˉ a ⟩ = ⟨ u ˉ a ∣ 0 ⟩ = 0 \sum_x \langle\bar{u}_a \mid v_{xa} - \bar{v}_a \rangle= \langle\bar{u}_a \mid n\bar{v}_a - n\bar{v}_a \rangle= \langle\bar{u}_a \mid0 \rangle= 0 ∑ x ⟨ u ˉ a ∣ v x a − v ˉ a ⟩ = ⟨ u ˉ a ∣ n v ˉ a − n v ˉ a ⟩ = ⟨ u ˉ a ∣ 0 ⟩ = 0 , which means that we can use it as a zero quantity and freely subtract it, so
n ξ − μ = n ∑ x , a ⟨ u x a ∣ v x a − v ˉ a ⟩ = n ∑ x , a ⟨ u x a ∣ v x a − v ˉ a ⟩ − n ∑ x , a ⟨ u ˉ a ∣ v x a − v ˉ a ⟩ n\xi-\mu= n \sum_{x,a} \langle u_{xa} \mid v_{xa} - \bar{v}_a \rangle= n \sum_{x,a} \langle u_{xa} \mid v_{xa} - \bar{v}_a \rangle- n \sum_{x,a} \langle\bar{u}_a \mid v_{xa} - \bar{v}_a \rangle n ξ − μ = n x , a ∑ ⟨ u x a ∣ v x a − v ˉ a ⟩ = n x , a ∑ ⟨ u x a ∣ v x a − v ˉ a ⟩ − n x , a ∑ ⟨ u ˉ a ∣ v x a − v ˉ a ⟩
Thus
n ξ − μ = n ∑ x , a ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ n\xi-\mu= n \sum_{x,a} \langle u_{xa} - \bar{u}_a \mid v_{xa} - \bar{v}_a \rangle n ξ − μ = n x , a ∑ ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩
Note that ξ , μ \xi,\mu ξ , μ are both sums of probabilities, and thus must be entirely real. As such, Re ( n ∑ x , a ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ) = n ∑ x , a ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ \operatorname{Re}\left(n\sum_{x,a}\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\right)=n\sum_{x,a}\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle Re ( n ∑ x , a ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ) = n ∑ x , a ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ , so
n ξ − μ = n ∑ x , a Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ n\xi-\mu=n\sum_{x,a}\operatorname{Re}\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle n ξ − μ = n x , a ∑ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩
We will return to that expression in a little while. In the meantime, recall that A x a A_x^a A x a is a projector, and thus ∥ u x a ∥ 2 = ⟨ ψ ∣ ( A x a ) 2 ⊗ I ∣ ψ ⟩ = ⟨ ψ ∣ ( A x a ) ⊗ I ∣ ψ ⟩ \lVert u_{xa}\rVert^2=\langle\psi\mid(A_x^a)^2\otimes I\mid\psi\rangle=\langle\psi\mid(A_x^a)\otimes I\mid\psi\rangle ∥ u x a ∥ 2 = ⟨ ψ ∣ ( A x a ) 2 ⊗ I ∣ ψ ⟩ = ⟨ ψ ∣ ( A x a ) ⊗ I ∣ ψ ⟩ . This tells us that, by completeness of projective measurement,
∑ a ∥ u x a ∥ 2 = 1 \sum_a\lVert u_{xa}\rVert^2=1 a ∑ ∥ u x a ∥ 2 = 1
and thus
∑ x , a ∥ u x a ∥ 2 = n \sum_{x,a}\lVert u_{xa}\rVert^2=n x , a ∑ ∥ u x a ∥ 2 = n
We will use that soon. But first, we will establish a lower bound on ∑ a ∥ u ˉ a ∥ 2 \sum_a\lVert\bar{u}_a\rVert^2 ∑ a ∥ u ˉ a ∥ 2 . By the generalized triangle inequality,
∥ ∑ a u ˉ a ∥ ≤ ∑ a ∥ u ˉ a ∥ \left\lVert\sum_a\bar{u}_a\right\rVert\leq\sum_a\lVert\bar{u}_a\rVert a ∑ u ˉ a ≤ a ∑ ∥ u ˉ a ∥
Since both sides are nonnegative real numbers, this tells us that
∥ ∑ a u ˉ a ∥ 2 ≤ ( ∑ a ∥ u ˉ a ∥ ) 2 \left\lVert\sum_a\bar{u}_a\right\rVert^2\leq\left(\sum_a\lVert\bar{u}_a\rVert\right)^2 a ∑ u ˉ a 2 ≤ ( a ∑ ∥ u ˉ a ∥ ) 2
By the Cauchy-Schwarz inequality, since there are m m m values of a a a ,
m ∑ a ∥ u ˉ a ∥ 2 ≥ ( ∑ a ∥ u ˉ a ∥ ) 2 ≥ ∥ ∑ a u ˉ a ∥ 2 m\sum_a\lVert\bar{u}_a\rVert^2\geq\left(\sum_a\lVert\bar{u}_a\rVert\right)^2\geq\left\lVert\sum_a\bar{u}_a\right\rVert^2 m a ∑ ∥ u ˉ a ∥ 2 ≥ ( a ∑ ∥ u ˉ a ∥ ) 2 ≥ a ∑ u ˉ a 2
and thus
∑ a ∥ u ˉ a ∥ 2 ≥ ∥ ∑ a u ˉ a ∥ 2 m \sum_a\lVert\bar{u}_a\rVert^2\geq\frac{\left\lVert\sum_a\bar{u}_a\right\rVert^2}{m} a ∑ ∥ u ˉ a ∥ 2 ≥ m ∥ ∑ a u ˉ a ∥ 2
We have
∥ ∑ a u ˉ a ∥ = ∥ ∑ x , a u x a n ∥ = ∥ 1 n ∑ x ( ∑ a u x a ) ∥ = ∥ 1 n ∑ x ∣ ψ ⟩ ∥ = ∥ ∣ ψ ⟩ ∥ = 1 , \left\lVert\sum_a\bar{u}_a\right\rVert=\left\lVert\sum_{x,a}\frac{u_{xa}}{n}\right\rVert=\left\lVert\frac{1}{n}\sum_x\left(\sum_a u_{xa}\right)\right\rVert=\left\lVert\frac{1}{n}\sum_x\lvert\psi\rangle\right\rVert=\lVert\lvert\psi\rangle\rVert=1, a ∑ u ˉ a = x , a ∑ n u x a = n 1 x ∑ ( a ∑ u x a ) = n 1 x ∑ ∣ ψ ⟩ = ∥∣ ψ ⟩∥ = 1 ,
so
∑ a ∥ u ˉ a ∥ 2 ≥ 1 2 m = 1 m \sum_a\lVert\bar{u}_a\rVert^2\geq\frac{1^2}{m}=\frac{1}{m} a ∑ ∥ u ˉ a ∥ 2 ≥ m 1 2 = m 1
Again, that will be used soon. Next, we define
D u = ∑ x , a ∥ u x a − u ˉ a ∥ 2 D_u=\sum_{x,a}\lVert u_{xa}-\bar{u}_a\rVert^2 D u = x , a ∑ ∥ u x a − u ˉ a ∥ 2
We can expand the term inside the sum to get us
D u = ∑ x , a ( ∥ u x a ∥ 2 − 2 Re ⟨ u x a ∣ u ˉ a ⟩ + ∥ u ˉ a ∥ 2 ) D_u=\sum_{x,a}\left(\lVert u_{xa}\rVert^2-2\operatorname{Re}\langle u_{xa}\mid\bar{u}_a\rangle+\lVert\bar{u}_a\rVert^2\right) D u = x , a ∑ ( ∥ u x a ∥ 2 − 2 Re ⟨ u x a ∣ u ˉ a ⟩ + ∥ u ˉ a ∥ 2 )
Distributing the sum over x x x gives us
D u = ∑ a ( ∑ x ∥ u x a ∥ 2 − 2 ∑ x Re ⟨ u x a ∣ u ˉ a ⟩ + ∑ x ∥ u ˉ a ∥ 2 ) = ∑ a ( ∑ x ∥ u x a ∥ 2 − 2 ∑ x Re ⟨ u x a ∣ u ˉ a ⟩ + n ∥ u ˉ a ∥ 2 ) = ∑ a ( ∑ x ∥ u x a ∥ 2 − 2 Re ∑ x ⟨ u x a ∣ u ˉ a ⟩ + n ∥ u ˉ a ∥ 2 ) = ∑ a ( ∑ x ∥ u x a ∥ 2 − 2 Re ( n ⟨ u ˉ a ∣ u ˉ a ⟩ ) + n ∥ u ˉ a ∥ 2 ) = ∑ a ( ∑ x ∥ u x a ∥ 2 − 2 n ∥ u ˉ a ∥ 2 + n ∥ u ˉ a ∥ 2 ) = ∑ a ( ∑ x ∥ u x a ∥ 2 − n ∥ u ˉ a ∥ 2 ) \begin{aligned}
D_u&=\sum_a\left(\sum_x\lVert u_{xa}\rVert^2-2\sum_x\operatorname{Re}\langle u_{xa}\mid\bar{u}_a\rangle+\sum_x\lVert\bar{u}_a\rVert^2\right)\\
&=\sum_a\left(\sum_x\lVert u_{xa}\rVert^2-2\sum_x\operatorname{Re}\langle u_{xa}\mid\bar{u}_a\rangle+n\lVert\bar{u}_a\rVert^2\right)\\
&=\sum_a\left(\sum_x\lVert u_{xa}\rVert^2-2\operatorname{Re}\sum_x\langle u_{xa}\mid\bar{u}_a\rangle+n\lVert\bar{u}_a\rVert^2\right)\\
&=\sum_a\left(\sum_x\lVert u_{xa}\rVert^2-2\operatorname{Re}\left(n\langle\bar{u}_a\mid\bar{u}_a\rangle\right)+n\lVert\bar{u}_a\rVert^2\right)\\
&=\sum_a\left(\sum_x\lVert u_{xa}\rVert^2-2n\lVert\bar{u}_a\rVert^2+n\lVert\bar{u}_a\rVert^2\right)\\
&=\sum_a\left(\sum_x\lVert u_{xa}\rVert^2-n\lVert\bar{u}_a\rVert^2\right)
\end{aligned} D u = a ∑ ( x ∑ ∥ u x a ∥ 2 − 2 x ∑ Re ⟨ u x a ∣ u ˉ a ⟩ + x ∑ ∥ u ˉ a ∥ 2 ) = a ∑ ( x ∑ ∥ u x a ∥ 2 − 2 x ∑ Re ⟨ u x a ∣ u ˉ a ⟩ + n ∥ u ˉ a ∥ 2 ) = a ∑ ( x ∑ ∥ u x a ∥ 2 − 2 Re x ∑ ⟨ u x a ∣ u ˉ a ⟩ + n ∥ u ˉ a ∥ 2 ) = a ∑ ( x ∑ ∥ u x a ∥ 2 − 2 Re ( n ⟨ u ˉ a ∣ u ˉ a ⟩ ) + n ∥ u ˉ a ∥ 2 ) = a ∑ ( x ∑ ∥ u x a ∥ 2 − 2 n ∥ u ˉ a ∥ 2 + n ∥ u ˉ a ∥ 2 ) = a ∑ ( x ∑ ∥ u x a ∥ 2 − n ∥ u ˉ a ∥ 2 )
And we can distribute the sum over a a a to find
D u = ∑ x , a ∥ u x a ∥ 2 − n ∑ a ∥ u ˉ a ∥ 2 D_u=\sum_{x,a}\lVert u_{xa}\rVert^2-n\sum_a\lVert\bar{u}_a\rVert^2 D u = x , a ∑ ∥ u x a ∥ 2 − n a ∑ ∥ u ˉ a ∥ 2
We established above that ∑ x , a ∥ u x a ∥ 2 = n \sum_{x,a}\lVert u_{xa}\rVert^2=n ∑ x , a ∥ u x a ∥ 2 = n so
D u = n − n ∑ a ∥ u ˉ a ∥ 2 D_u=n-n\sum_a\lVert\bar{u}_a\rVert^2 D u = n − n a ∑ ∥ u ˉ a ∥ 2
and we also established above that ∑ a ∥ u ˉ a ∥ 2 ≥ 1 m \sum_a\lVert\bar{u}_a\rVert^2\ge\frac{1}{m} ∑ a ∥ u ˉ a ∥ 2 ≥ m 1 , which tells us that
D u = n − n ∑ a ∥ u ˉ a ∥ 2 ≤ n − n m = n ( 1 − 1 m ) D_u=n-n\sum_a\lVert\bar{u}_a\rVert^2\le n-\frac{n}{m}=n\left(1-\frac{1}{m}\right) D u = n − n a ∑ ∥ u ˉ a ∥ 2 ≤ n − m n = n ( 1 − m 1 )
Importantly, note that none of our steps here used any property specific to Alice, so the same inequality holds true for Bob’s state and projectors:
D v = ∑ y , b ∥ v y b − v ˉ b ∥ 2 ≤ n ( 1 − 1 m ) D_v=\sum_{y,b}\lVert v_{yb}-\bar{v}_b\rVert^2\le n\left(1-\frac{1}{m}\right) D v = y , b ∑ ∥ v y b − v ˉ b ∥ 2 ≤ n ( 1 − m 1 )
At last, we can come back to our expression for n ξ − μ n\xi-\mu n ξ − μ :
n ξ − μ = n ∑ x , a Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ n\xi-\mu=n\sum_{x,a}\operatorname{Re}\langle u_{xa}-\bar{u}_a\mid v_{xa}-\bar{v}_a\rangle n ξ − μ = n x , a ∑ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩
As a simple property of absolute values,
n ∑ x , a Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ≤ n ∣ ∑ x , a Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ n\sum_{x,a}\operatorname{Re}\langle u_{xa}-\bar{u}_a\mid v_{xa}-\bar{v}_a\rangle\le n\left|\sum_{x,a}\operatorname{Re}\langle u_{xa}-\bar{u}_a\mid v_{xa}-\bar{v}_a\rangle\right| n x , a ∑ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ≤ n x , a ∑ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩
By the triangle inequality,
∣ ∑ x , a Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ ≤ ∑ x , a ∣ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ \left|\sum_{x,a} \operatorname{Re}\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\right| \le\sum_{x,a}\left|\operatorname{Re}\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\right| x , a ∑ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ≤ x , a ∑ ∣ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣
The magnitude of a complex value is guaranteed to be at least the magnitude of its real part, so
∑ x , a ∣ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ ≤ ∑ x , a ∣ ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ \sum_{x,a}\left|\operatorname{Re}\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\right| \le\sum_{x,a}\left|\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\right| x , a ∑ ∣ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ ≤ x , a ∑ ∣ ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣
For each pair ( x , a ) (x,a) ( x , a ) we can apply Cauchy-Schwarz to see that
∣ ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ ≤ ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥ \left|\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\right| \le\left\|u_{xa}-\bar{u}_a\right\| \cdot\left\|v_{xa}-\bar{v}_a\right\| ∣ ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ ≤ ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥
so
∑ x , a ∣ ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ ≤ ∑ x , a ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥ \sum_{x,a}\left|\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\right| \le\sum_{x,a}\left\|u_{xa}-\bar{u}_a\right\| \cdot\left\|v_{xa}-\bar{v}_a\right\| x , a ∑ ∣ ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ∣ ≤ x , a ∑ ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥
Once more using Cauchy-Schwarz we can observe that
( ∑ x , a ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥ ) 2 ≤ ∑ x , a ( ∥ u x a − u ˉ a ∥ ) 2 ∑ x , a ( ∥ v x a − v ˉ a ∥ ) 2 = D u D v \left(\sum_{x,a}\left\|u_{xa}-\bar{u}_a\right\| \cdot\left\|v_{xa}-\bar{v}_a\right\|\right)^2 \le\sum_{x,a}\left(\left\|u_{xa}-\bar{u}_a\right\|\right)^2 \sum_{x,a}\left(\left\|v_{xa}-\bar{v}_a\right\|\right)^2 = D_uD_v ( x , a ∑ ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥ ) 2 ≤ x , a ∑ ( ∥ u x a − u ˉ a ∥ ) 2 x , a ∑ ( ∥ v x a − v ˉ a ∥ ) 2 = D u D v
and thus
∑ x , a ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥ ≤ D u D v \sum_{x,a}\left\|u_{xa}-\bar{u}_a\right\| \cdot\left\|v_{xa}-\bar{v}_a\right\| \le\sqrt{D_u}\sqrt{D_v} x , a ∑ ∥ u x a − u ˉ a ∥ ⋅ ∥ v x a − v ˉ a ∥ ≤ D u D v
This allows us to conclude that
n ξ − μ = n ∑ x , a Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ≤ n D u D v n\xi-\mu= n\sum_{x,a}\operatorname{Re}\langle u_{xa}-\bar{u}_a \mid v_{xa}-\bar{v}_a\rangle\le n\sqrt{D_u}\sqrt{D_v} n ξ − μ = n x , a ∑ Re ⟨ u x a − u ˉ a ∣ v x a − v ˉ a ⟩ ≤ n D u D v
and since we know that D u ≤ n ( 1 − 1 m ) D_u \le n\left(1-\frac{1}{m}\right) D u ≤ n ( 1 − m 1 ) and D v ≤ n ( 1 − 1 m ) D_v \le n\left(1-\frac{1}{m}\right) D v ≤ n ( 1 − m 1 ) , this tells us that
n ξ − μ ≤ n 2 ( 1 − 1 m ) n\xi-\mu\le n^2\left(1-\frac{1}{m}\right) n ξ − μ ≤ n 2 ( 1 − m 1 )
Theorem B.0.2. At p = 1 2 p=\frac{1}{2} p = 2 1 , any quantum strategy has ω ≤ 1 2 + 1 2 ( 1 − n − m m ( n − 1 ) ) \omega\le\frac{1}{2}+\frac{1}{2}\left(1-\frac{n-m}{m(n-1)}\right) ω ≤ 2 1 + 2 1 ( 1 − m ( n − 1 ) n − m ) .
Proof. Recall that the value for a given strategy can be written as
ω = 1 − p + 1 − p n ( n − 1 ) ν \omega= 1-p+\frac{1-p}{n(n-1)}\nu ω = 1 − p + n ( n − 1 ) 1 − p ν where
ν : = ( p ( n − 1 ) 1 − p + 1 ) ξ − μ \nu:= \left(\frac{p(n-1)}{1-p}+1\right)\xi-\mu ν := ( 1 − p p ( n − 1 ) + 1 ) ξ − μ Since p = 1 2 p=\frac{1}{2} p = 2 1 , we have
p ( n − 1 ) 1 − p + 1 = 1 2 ( n − 1 ) 1 2 + 1 = n \frac{p(n-1)}{1-p}+1 = \frac{\frac{1}{2}(n-1)}{\frac{1}{2}}+1=n 1 − p p ( n − 1 ) + 1 = 2 1 2 1 ( n − 1 ) + 1 = n
so ν = n ξ − μ \nu=n\xi-\mu ν = n ξ − μ and thus by Lemma B.0.1 ν ≤ n 2 ( 1 − 1 m ) \nu\le n^{2}\left(1-\frac{1}{m}\right) ν ≤ n 2 ( 1 − m 1 ) . Thus
ω = 1 − p + 1 − p n ( n − 1 ) ν ≤ 1 − p + 1 − p n ( n − 1 ) ( n 2 ) ( 1 − 1 m ) \omega=1-p+\frac{1-p}{n(n-1)}\nu\le1-p+\frac{1-p}{n(n-1)}\left(n^{2}\right)\left(1-\frac{1}{m}\right) ω = 1 − p + n ( n − 1 ) 1 − p ν ≤ 1 − p + n ( n − 1 ) 1 − p ( n 2 ) ( 1 − m 1 )
Substituting in p = 1 2 p=\frac{1}{2} p = 2 1 , we have
ω ≤ 1 − 1 2 + 1 2 n ( n − 1 ) ( n 2 ) ( 1 − 1 m ) = 1 2 + 1 2 ( n − n m n − 1 ) \omega\le1-\frac{1}{2}+\frac{\frac{1}{2}}{n(n-1)}\left(n^{2}\right)\left(1-\frac{1}{m}\right)=\frac{1}{2}+\frac{1}{2}\left(\frac{n-\frac{n}{m}}{n-1}\right) ω ≤ 1 − 2 1 + n ( n − 1 ) 2 1 ( n 2 ) ( 1 − m 1 ) = 2 1 + 2 1 ( n − 1 n − m n )
We have
n − n m n − 1 = m n − n m ( n − 1 ) = m n − m + m − n m ( n − 1 ) = 1 − n − m m ( n − 1 ) . \frac{n-\frac{n}{m}}{n-1}=\frac{mn-n}{m(n-1)}=\frac{mn-m+m-n}{m(n-1)}=1-\frac{n-m}{m(n-1)}. n − 1 n − m n = m ( n − 1 ) mn − n = m ( n − 1 ) mn − m + m − n = 1 − m ( n − 1 ) n − m .
Substituting into the above inequality for ω \omega ω gives our desired bound.
Theorem B.0.3. Our quantum synchronous strategy is optimal at p = 1 2 p=\frac{1}{2} p = 2 1 (i.e., when equal inputs are exactly as likely as unequal inputs).
Proof. By Theorem 4.1.3 , our quantum synchronous strategy’s value is
p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right) p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) Substituting in p = 1 2 p=\frac{1}{2} p = 2 1 this gives us
1 2 + 1 2 ( 1 − n − m m ( n − 1 ) ) \frac{1}{2}+\frac{1}{2}\left(1-\frac{n-m}{m(n-1)}\right) 2 1 + 2 1 ( 1 − m ( n − 1 ) n − m ) By Theorem B.0.2 , for p = 1 2 p=\frac{1}{2} p = 2 1 , we have
ω ≤ 1 2 + 1 2 ( 1 − n − m m ( n − 1 ) ) \omega\le\frac{1}{2}+\frac{1}{2}\left(1-\frac{n-m}{m(n-1)}\right) ω ≤ 2 1 + 2 1 ( 1 − m ( n − 1 ) n − m ) for all quantum strategies, and thus our synchronous strategy achieves the upper bound on win probability for p = 1 2 p=\frac{1}{2} p = 2 1 .
Theorem B.0.4. Our quantum synchronous strategy is optimal for all p ∈ [ 1 2 , 1 ] p\in\left[\frac{1}{2},1\right] p ∈ [ 2 1 , 1 ] .
Proof. This follows directly from Theorems 2.1.2 and B.0.3 : our strategy is optimal over all quantum strategies for p = 1 2 p=\frac{1}{2} p = 2 1 by Theorem B.0.3 , and thus by Theorem 2.1.2 our strategy is optimal for all p ∈ [ 1 2 , 1 ] p\in\left[\frac{1}{2},1\right] p ∈ [ 2 1 , 1 ] .
Theorem B.0.5. The optimal quantum value for this game, for p ∈ [ 1 2 , 1 ] p\in\left[\frac{1}{2},1\right] p ∈ [ 2 1 , 1 ] , is p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right) p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) .
Proof. This follows directly from Theorem B.0.4 : since our strategy is optimal over all quantum strategies for p ∈ [ 1 2 , 1 ] p\in\left[\frac{1}{2},1\right] p ∈ [ 2 1 , 1 ] , and since we have by Theorem 4.1.3 the success probability of our strategy is
p + ( 1 − p ) ( 1 − n − m m ( n − 1 ) ) p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right) p + ( 1 − p ) ( 1 − m ( n − 1 ) n − m ) that must be the optimal quantum value over all quantum strategies for p ∈ [ 1 2 , 1 ] p\in\left[\frac{1}{2},1\right] p ∈ [ 2 1 , 1 ] .