## @wrenchwater4

### Profile

Registered: 3 months ago

Quantum Game Players Can Have Advantage Without Discord

The last two decades have witnessed a rapid development of quantum information processing, a new paradigm which studies the power and limit of “quantum advantages” in various information processing tasks. Problems such as when quantum advantage exists, and if existing, how much it could be, are at a central position of these studies. In a broad class of scenarios, there are, implicitly or explicitly, at least two parties involved, who share a state, and the correlation in this shared state is the key factor to the efficiency under concern. In these scenarios, the shared entanglement or discord is usually what accounts for quantum advantage. In this paper, we examine a fundamental problem of this nature from the perspective of game theory, a branch of applied mathematics studying selfish behaviors of two or more players. We exhibit a natural zero-sum game, in which the chance for any player to win the game depends only on the ending correlation. We show that in a certain classical equilibrium, a situation in which no player can further increase her payoff by any local classical operation, whoever first uses a quantum computer has a big advantage over its classical opponent. The equilibrium is fair to both players and, as a shared correlation, it does not contain any discord, yet a quantum advantage still exists. This indicates that at least in game theory, the previous notion of discord as a measure of non-classical correlation needs to be reexamined, when there are two players with different objectives.

Quantum computers have exhibited tremendous power in algorithmic, cryptographic, information theoretic, and many other information processing tasks, compared with their classical counterparts. Meanwhile, for a large number of problems, quantum computers are not able to offer much advantage over classical ones. When and why quantum computers are more powerful are always at a central position in studies on quantum computation and quantum information processing. A particularly interesting class of scenarios is when there are, implicitly or explicitly, at least two parties involved who share a state, the correlation in this state is the key factor. What accounts for the quantum advantage is often entanglement, one of the most distinctive characters of quantum information. Indeed, it has been showed that a quantum algorithm with only slight entanglement can be simulated efficiently by a classical computer [Vid03]. In certain potential applications of quantum algorithms, it is also shown that entangled measurement is necessary for the existence of efficient quantum algorithms [HMR+^+start_FLOATSUPERSCRIPT + end_FLOATSUPERSCRIPT10].

Recently people started to realize that entanglement is not always a necessary resource needed for generating quantum correlations. It has been found that discord, another unique character of quantum states, also plays an important role in quantum information processing [OZ01]. Discord is a relaxed version of entanglement-states with positive entanglement must also have positive discord, but there are states with positive discord but zero entanglement. People has discovered cases where quantum speed-up exists without entanglement involved, and discord is considered to be responsible for the quantum advantage [DSC08]. Till today, discord is widely considered as necessary for the existence of quantum advantages.

In this paper, we reexamine this notion from the perspective of game theory [OR94]. Game theory studies the situation in which there are two or more players with possibly different goals. There are two broad classes of games, one is strategic-form (or normal-form) games, in which all players make their choice simultaneously; a typical example is Rock-Paper-Scissors. The other class is extensive-form games, in which players make their moves in turn; a typical example is chess.

The research on quantum games began about one decade ago, starting with two pioneering papers.111Note that there is also a class of “nonlocal games”, such as CHSH or GHZ games [BCMdW10], where all the players have the same objective. But general game theory focuses more on situation that the players have different objective functions, and the players are selfish, each aiming to optimize her own objective function only. The first one [EWL99] aimed to quantize a specific strategic-form game called Prisoners’ Dilemma [EWL99], and it unleashed a long sequence of follow-up works in the same model. Despite the rapid growth of literature, controversy also largely exists [BH01, vEP02, CT06], which questioned the meaning of the claimed quantum solution, the ad hoc assumptions in the model, and the inconsistency with standard settings of classical strategic games. Recently a new model was proposed for quantizing general strategic-form games [Zha12]. Compared with [EWL99], the new model corresponds to the classical games more precisely, and has rich mathematical structures and game-theoretic questions; also see later theoretical developments [KZ12, WZ13, JSWZ13, PKL+^+start_FLOATSUPERSCRIPT + end_FLOATSUPERSCRIPT15].

Back to the early stage of the development of quantum game theory, the other pioneering paper was [Mey99], which demonstrated the power of using quantum strategies in an extensive-form game. More specifically, Meyer considered the quantum version of the classical Penny Matching game. The basic setting is as follows. There are two players, and each has two possible actions on one bit: Flip it or not. Starting with the bit being 0, Player 1 first takes an action, and then Player 2 takes an action, and finally Player 1 takes another action, and the game is finished. If the bit is finally 0, then Player 1 wins; otherwise Player 2 wins. It is not hard to see that if Player 2 flips the bit with half probability, then no matter what Player 1 does, each player wins the game with half probability. Now consider the following change of setting: The bit becomes a qubit; the first player uses a quantum computer in the sense that she can perform any quantum admissible operation on the bit; the second player uses a classical computer in the sense that she can perform either Identity or the flip operation [0110]matrix0110\beginbmatrix0&1\\ 1&0\endbmatrix[ start_ARG start_ROW start_CELL 0 end_CELL start_CELL 1 end_CELL end_ROW start_ROW start_CELL 1 end_CELL start_CELL 0 end_CELL end_ROW end_ARG ]. In this new setting, Player 1 can win the game with certainty! Her winning strategy is simple: she first applies a Hadamard gate to change the state to |+⟩=(|0⟩+|1⟩)/2ketket0ket12|+\rangle=(|0\rangle+|1\rangle)/\sqrt2| + ⟩ = ( | 0 ⟩ + | 1 ⟩ ) / square-root start_ARG 2 end_ARG, and then no matter whether Player 2 applies the flip operation or not, the state remains the same |+⟩ket|+\rangle| + ⟩, thus in the third step Player 1 can simply apply a Hadamard gate again to rotate the state back to |0⟩ket0|0\rangle| 0 ⟩. This shows that a player using a quantum computer can have big advantage over one using a classical computer.

Despite a very interesting phenomena it exhibits, the quantum advantage is not the most convincing due to a fairness issue. After all, the quantum player takes two actions and the classical player takes just one. And the order of “Player 1 →→\rightarrow→ Player 2 →→\rightarrow→ Player 1” is also crucial for the quantum advantage. One remedy is to consider normal-form games, in which the players give their strategies simultaneously, thus there is no longer the issue of the action order. Taking the model in [Zha12], two players play a complete-information normal-form game, with a starting state ρ𝜌\rhoitalic_ρ in systems (A1,A2)subscript𝐴1subscript𝐴2(A_1,A_2)( italic_A start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_A start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ), and Aisubscript𝐴𝑖A_iitalic_A start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT being given to Player i𝑖iitalic_i. A classical player can only measure her part of the state in the computational basis, followed by whatever classical operation C𝐶Citalic_C (on the computational basis). In previous works [EWL99, Mey99, ZWC+^+start_FLOATSUPERSCRIPT + end_FLOATSUPERSCRIPT12] the classical player is usually assumed to be able to apply any classical operation on computational basis (such as X𝑋Xitalic_X-gate), followed by a measurement in the computational basis. A classical operations there is implicitly assumed to be unitary, so the operation in the matrix form is a permutation matrix. Here we allow classical player to measure first and then perform any classical operation, which gives her more power since the second-step classical operation does need to be unitary. Indeed, in Meyer’s Penny Matching game, in the second step Player 2 could measure the state first and then randomly set it to be |0⟩ket0|0\rangle| 0 ⟩ or |1⟩ket1|1\rangle| 1 ⟩ each with half probability. Then in the third step, Player 1’s Hadamard gate will change the state to |+⟩ket|+\rangle| + ⟩ or |-⟩ket|-\rangle| - ⟩, in either case, Player 1 could win with only half probability.

Even if we now enlarge the space of possible operations of the classical player, we will show examples where the quantum player has advantage of winning the game. Furthermore, the examples have the following nice properties respecting the fairness of the game:

1.

If both players are classical, then both get expected payoff 0, and ρ𝜌\rhoitalic_ρ is a correlated equilibrium in the sense that any classical operation C𝐶Citalic_C by one player cannot increase her expected payoff.

2.

Suppose that one player remains classical and the other player uses a quantum computer. To illustrate the power of using quantum strategies, we cut the classical player some slack as follows. The classical player can (1) pick one subsystem, A1subscript𝐴1A_1italic_A start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT or A2subscript𝐴2A_2italic_A start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT, of ρ𝜌\rhoitalic_ρ, leaving the other subsystem to the quantum player, and (2) “take side” by picking one of the two payoff matrices, leaving the other to the quantum player.

Examples were found that even with the advantage of taking side and taking part of the shared state, the classical player still has a disadvantage compared to the quantum player. Consider the canonical 2×2222\times 22 × 2 zero-sum game with the payoff matrices being

U1=(1-1-11) and U2=(-111-1).formulae-sequencesubscript𝑈1matrix1111 and subscript𝑈2matrix1111U_1=\beginpmatrix1&-1\\ -1&1\endpmatrix\quad\text and \quad U_2=\beginpmatrix-1&1\\ 1&-1\endpmatrix.italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = ( start_ARG start_ROW start_CELL 1 end_CELL start_CELL - 1 end_CELL end_ROW start_ROW start_CELL - 1 end_CELL start_CELL 1 end_CELL end_ROW end_ARG ) and italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = ( start_ARG start_ROW start_CELL - 1 end_CELL start_CELL 1 end_CELL end_ROW start_ROW start_CELL 1 end_CELL start_CELL - 1 end_CELL end_ROW end_ARG ) . (1)

Quantum game with entanglement

Each player i𝑖iitalic_i owns a 2-dimensional Hilbert space, and they share the quantum state

|ψ⟩=12(|+0⟩+|-1⟩)=12(|0+⟩+|1-⟩),ket𝜓12ket0ket112ketlimit-from0ketlimit-from1|\psi\rangle=\frac1\sqrt2(|+0\rangle+|-1\rangle)=\frac1\sqrt2(|0+% \rangle+|1-\rangle),| italic_ψ ⟩ = divide start_ARG 1 end_ARG start_ARG square-root start_ARG 2 end_ARG end_ARG ( | + 0 ⟩ + | - 1 ⟩ ) = divide start_ARG 1 end_ARG start_ARG square-root start_ARG 2 end_ARG end_ARG ( | 0 + ⟩ + | 1 - ⟩ ) , (2)

where |+⟩=12(|0⟩+|1⟩)ket12ket0ket1|+\rangle=\frac1\sqrt2(|0\rangle+|1\rangle)| + ⟩ = divide start_ARG 1 end_ARG start_ARG square-root start_ARG 2 end_ARG end_ARG ( | 0 ⟩ + | 1 ⟩ ), and |-⟩=12(|0⟩-|1⟩)ket12ket0ket1|-\rangle=\frac1\sqrt2(|0\rangle-|1\rangle)| - ⟩ = divide start_ARG 1 end_ARG start_ARG square-root start_ARG 2 end_ARG end_ARG ( | 0 ⟩ - | 1 ⟩ ). It is not difficult to verify that if both players measure their parts in the computational basis, then each gets payoff 1 and -11-1- 1 with equal probability, resulting an average payoff of zero for both players. This is a correlated equilibrium for classical operations.

Now suppose that Player 1 employs a quantum computer. Since the state is symmetric, it does not matter which part Player 2, the classical player, chooses. Let us assume that Player 2 chooses part 2, and the payoff matrix U2subscript𝑈2U_2italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT. Then Player 1 can apply the Hadamard transformation on her qubit, followed by the measurement in computational basis. The state immediately before the measurement is |ψ′⟩=(|00⟩+|11⟩)/2ketsuperscript𝜓′ket00ket112|\psi^\prime\rangle=(|00\rangle+|11\rangle)/\sqrt2| italic_ψ start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ⟩ = ( | 00 ⟩ + | 11 ⟩ ) / square-root start_ARG 2 end_ARG. Therefore the measurement in the computational basis gives Player 1 and Player 2 payoff 1 and -11-1- 1, respectively, with certainty. In other words, Player 1 wins with certainty, whereas she could only win with half probability when using a classical computer.

In this example where the quantum player has an advantage, the state shared by players is highly entangled, which motivates the following natural question: Is entanglement necessary for quantum advantage in the game? It turns out that the answer is no. Consider the example below.

Quantum game with discord

The payoff matrices are the same as before, but the quantum state shared by players is the following.

ρ=14(|+⟩⟨+|⊗|0⟩⟨0|+|0⟩⟨0|⊗|+⟩⟨+|+|-⟩⟨-|⊗|1⟩⟨1|+|1⟩⟨1|⊗|-⟩⟨-|).fragmentsρ14fragments(|⟩fragments⟨|tensor-product|0⟩fragments⟨0||0⟩fragments⟨0|tensor-product|⟩fragments⟨||⟩fragments⟨|tensor-product|1⟩fragments⟨1||1⟩fragments⟨1|tensor-product|⟩fragments⟨|).\rho=\frac14(|+\rangle\langle+|\otimes|0\rangle\langle 0|+|0\rangle\langle 0% |\otimes|+\rangle\langle+|+|-\rangle\langle-|\otimes|1\rangle\langle 1|+|1% \rangle\langle 1|\otimes|-\rangle\langle-|).italic_ρ = divide start_ARG 1 end_ARG start_ARG 4 end_ARG ( | + ⟩ ⟨ + | ⊗ | 0 ⟩ ⟨ 0 | + | 0 ⟩ ⟨ 0 | ⊗ | + ⟩ ⟨ + | + | - ⟩ ⟨ - | ⊗ | 1 ⟩ ⟨ 1 | + | 1 ⟩ ⟨ 1 | ⊗ | - ⟩ ⟨ - | ) . (3)

This state is separable and thus does not have any entanglement. It can be checked that if the players measure this state in computational basis, the probability of getting each of the four possible outcomes is 1/4. Thus the overall payoff of each player is zero, and it can be verified that it is a classical correlated equilibrium.

In the quantum setting, again without loss of generality assume that the classical computer picks the second part of ρ𝜌\rhoitalic_ρ and the second payoff matrix. The quantum player can again perform a Hadamard operation on her system, resulting in a new state

ρ′=14(|0⟩⟨0|⊗|0⟩⟨0|+|+⟩⟨+|⊗|+⟩⟨+|+|1⟩⟨1|⊗|1⟩⟨1|+|-⟩⟨-|⊗|-⟩⟨-|).fragmentssuperscript𝜌′14fragments(|0⟩fragments⟨0|tensor-product|0⟩fragments⟨0||⟩fragments⟨|tensor-product|⟩fragments⟨||1⟩fragments⟨1|tensor-product|1⟩fragments⟨1||⟩fragments⟨|tensor-product|⟩fragments⟨|).\rho^\prime=\frac14(|0\rangle\langle 0|\otimes|0\rangle\langle 0|+|+% \rangle\langle+|\otimes|+\rangle\langle+|+|1\rangle\langle 1|\otimes|1\rangle% \langle 1|+|-\rangle\langle-|\otimes|-\rangle\langle-|).italic_ρ start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT = divide start_ARG 1 end_ARG start_ARG 4 end_ARG ( | 0 ⟩ ⟨ 0 | ⊗ | 0 ⟩ ⟨ 0 | + | + ⟩ ⟨ + | ⊗ | + ⟩ ⟨ + | + | 1 ⟩ ⟨ 1 | ⊗ | 1 ⟩ ⟨ 1 | + | - ⟩ ⟨ - | ⊗ | - ⟩ ⟨ - | ) . (4)

Measuring the new state, the quantum player gets state |00⟩ket00|00\rangle| 00 ⟩, |01⟩ket01|01\rangle| 01 ⟩, |10⟩ket10|10\rangle| 10 ⟩, |11⟩ket11|11\rangle| 11 ⟩ with probability 3/8383/83 / 8, 1/8181/81 / 8, 1/8181/81 / 8, 3/8383/83 / 8 respectively. As a result, her winning probability increases from 1/2 to 3/4; in other words, she gets an expected payoff of 1/2.

Note that the quantum state in Eq.(4) is separable, and there is no any entanglement, but the quantum player still gets a quantum advantage. Thus, entanglement is not necessary for quantum advantage to exist in this game. Note that, however, the state in Eq.(4) has a positive discord. As we have mentioned, it was known that in some scenarios, it is discord, rather than entanglement, that produces non-classical correlations. So the above example confirms this traditional notion in the new game-theoretic setting.

These two examples were also experimentally verified recently [ZWC+^+start_FLOATSUPERSCRIPT + end_FLOATSUPERSCRIPT12]. The present paper makes further studies on the foregoing notion by asking the following fundamental question.

Is discord necessary for quantum advantage to exist in games where players share a symmetric state?

It is tempting to conjecture that the answer is Yes. In the rest of the paper, we will show that, first, discord is indeed necessary for any quantum advantage to exist in a 2-player games where each player has n=2𝑛2n=2italic_n = 2 strategies. We will then show that when n≥3𝑛3n\geq 3italic_n ≥ 3, however, there are games where the quantum player has a positive advantage even when the shared symmetric state has zero discord.

2 Preliminaries

Suppose that in a classical game there are k𝑘kitalic_k players, labeled by 1,2,…,k12…𝑘\1,2,\ldots,k\ 1 , 2 , … , italic_k . Each player i𝑖iitalic_i has a set Sisubscript𝑆𝑖S_iitalic_S start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT of strategies. To play the game, each player i𝑖iitalic_i selects a strategy sisubscript𝑠𝑖s_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT from Sisubscript𝑆𝑖S_iitalic_S start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT. We use s=(s1,…,sk)𝑠subscript𝑠1…subscript𝑠𝑘s=(s_1,\ldots,s_k)italic_s = ( italic_s start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_s start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ) to denote the joint strategy selected by the players and S=S1×…×Sk𝑆subscript𝑆1…subscript𝑆𝑘S=S_1\times\ldots\times S_kitalic_S = italic_S start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT × … × italic_S start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT to denote the set of all possible joint strategies. Each player i𝑖iitalic_i has a utility function ui:S→ℝ:subscript𝑢𝑖→𝑆ℝu_i:S\rightarrow\mbox$\mathbbR$italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT : italic_S → blackboard_R, specifying the payoff or utility ui(s)subscript𝑢𝑖𝑠u_i(s)italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s ) of Player i𝑖iitalic_i on the joint strategy s𝑠sitalic_s. For simplicity of notation, we use subscript -i𝑖-i- italic_i to denote the set [k]-idelimited-[]𝑘𝑖[k]-\i\[ italic_k ] - italic_i , so s-isubscript𝑠𝑖s_-iitalic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT is (s1,…,si-1,si+1,…,sk)subscript𝑠1…subscript𝑠𝑖1subscript𝑠𝑖1…subscript𝑠𝑘(s_1,\ldots,s_i-1,s_i+1,\ldots,s_k)( italic_s start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_s start_POSTSUBSCRIPT italic_i - 1 end_POSTSUBSCRIPT , italic_s start_POSTSUBSCRIPT italic_i + 1 end_POSTSUBSCRIPT , … , italic_s start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ), and similarly for S-isubscript𝑆𝑖S_-iitalic_S start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT, p-isubscript𝑝𝑖p_-iitalic_p start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT, etc. In this paper, we will mainly consider 2-player games.

Nash equilibrium is a fundamental solution concept in game theory. Roughly, it says that in a joint strategy, no player can gain more by changing her strategy, provided that all other players keep their current strategies unchanged. The precise definition is as follows.

A pure Nash equilibrium is a joint strategy s=(s1,…,sk)∈S𝑠subscript𝑠1normal-…subscript𝑠𝑘𝑆s=(s_1,\ldots,s_k)\in Sitalic_s = ( italic_s start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_s start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ) ∈ italic_S satisfying that

ui(si,s-i)≥ui(si′,s-i)subscript𝑢𝑖subscript𝑠𝑖subscript𝑠𝑖subscript𝑢𝑖superscriptsubscript𝑠𝑖′subscript𝑠𝑖\displaystyle u_i(s_i,s_-i)\geq u_i(s_i^\prime,s_-i)italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) ≥ italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) (5)

for all i∈[k]𝑖delimited-[]𝑘i\in[k]italic_i ∈ [ italic_k ] and all si′∈Sisubscriptsuperscript𝑠normal-′𝑖subscript𝑆𝑖s^\prime_i\in S_iitalic_s start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∈ italic_S start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT.

Pure Nash equilibria can be generalized by allowing each player to independently select her strategy according to some probability distribution, leading to the following concept of mixed Nash equilibrium.

Definition 2

A (mixed) Nash equilibrium (NE) is a product probability distribution p=p1×…×pk𝑝subscript𝑝1normal-…subscript𝑝𝑘p=p_1\times\ldots\times p_kitalic_p = italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT × … × italic_p start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT, where each pisubscript𝑝𝑖p_iitalic_p start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT is a probability distributions over Sisubscript𝑆𝑖S_iitalic_S start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT, satisfying that

∑s-ip-i(s-i)ui(si,s-i)≥∑s-ip-i(s-i)ui(si′,s-i),subscriptsubscript𝑠𝑖subscript𝑝𝑖subscript𝑠𝑖subscript𝑢𝑖subscript𝑠𝑖subscript𝑠𝑖subscriptsubscript𝑠𝑖subscript𝑝𝑖subscript𝑠𝑖subscript𝑢𝑖superscriptsubscript𝑠𝑖′subscript𝑠𝑖\displaystyle\sum_s_-ip_-i(s_-i)u_i(s_i,s_-i)\geq\sum_s_-ip_% -i(s_-i)u_i(s_i^\prime,s_-i),∑ start_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT italic_p start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) ≥ ∑ start_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT italic_p start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) , (6)

for all i∈[k]𝑖delimited-[]𝑘i\in[k]italic_i ∈ [ italic_k ], and all si,si′∈Sisubscript𝑠𝑖subscriptsuperscript𝑠normal-′𝑖subscript𝑆𝑖s_i,s^\prime_i\in S_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∈ italic_S start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT with pi(si)>0subscript𝑝𝑖subscript𝑠𝑖0p_i(s_i)>0italic_p start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) >0.

A fundamental fact proved by Nash [Nas51] is that every game with a finite number of players and a finite set of strategies for each player has at least one mixed Nash equilibrium.

There are various further extensions of mixed Nash equilibria. Aumann [Aum74] introduced a relaxation called correlated equilibrium. This notion assumes an external party, called Referee, to draw a joint strategy s=(s1,…,sk)𝑠subscript𝑠1…subscript𝑠𝑘s=(s_1,...,s_k)italic_s = ( italic_s start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_s start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ) from some probability distribution p𝑝pitalic_p over S𝑆Sitalic_S, possibly correlated in an arbitrary way, and to suggest sisubscript𝑠𝑖s_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT to Player i𝑖iitalic_i. Note that Player i𝑖iitalic_i only sees sisubscript𝑠𝑖s_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT, thus the rest strategy s-isubscript𝑠𝑖s_-iitalic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT is a random variable over S-isubscript𝑆𝑖S_-iitalic_S start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT distributed according to the conditional distribution p|sievaluated-at𝑝subscript𝑠𝑖p|_s_iitalic_p | start_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT, the distribution p𝑝pitalic_p conditioned on the i𝑖iitalic_i-th part being sisubscript𝑠𝑖s_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT. Gaming news Now p𝑝pitalic_p is a correlated equilibrium if any Player i𝑖iitalic_i, upon receiving a suggested strategy sisubscript𝑠𝑖s_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT, has no incentive to change her strategy to a different si′∈Sisuperscriptsubscript𝑠𝑖′subscript𝑆𝑖s_i^\prime\in S_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ∈ italic_S start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT, assuming that all other players stick to their received suggestion s-isubscript𝑠𝑖s_-iitalic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT.

Definition 3

A correlated equilibrium (CE) is a probability distribution p𝑝pitalic_p over S𝑆Sitalic_S satisfying that

∑s-ip(si,s-i)ui(si,s-i)≥∑s-ip(si,s-i)ui(si′,s-i),subscriptsubscript𝑠𝑖𝑝subscript𝑠𝑖subscript𝑠𝑖subscript𝑢𝑖subscript𝑠𝑖subscript𝑠𝑖subscriptsubscript𝑠𝑖𝑝subscript𝑠𝑖subscript𝑠𝑖subscript𝑢𝑖superscriptsubscript𝑠𝑖′subscript𝑠𝑖\displaystyle\sum_s_-ip(s_i,s_-i)u_i(s_i,s_-i)\geq\sum_s_-ip% (s_i,s_-i)u_i(s_i^\prime,s_-i),∑ start_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT italic_p ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) ≥ ∑ start_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT italic_p ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) , (7)

for all i∈[k]𝑖delimited-[]𝑘i\in[k]italic_i ∈ [ italic_k ], and all si,si′∈Sisubscript𝑠𝑖subscriptsuperscript𝑠normal-′𝑖subscript𝑆𝑖s_i,s^\prime_i\in S_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∈ italic_S start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT.

The above statement can also be restated as

𝔼s-i←μ|si[ui(si,s-i)]≥𝔼s-i←μ|si[ui(si′,s-i)].subscript𝔼←subscript𝑠𝑖conditional𝜇subscript𝑠𝑖delimited-[]subscript𝑢𝑖subscript𝑠𝑖subscript𝑠𝑖subscript𝔼←subscript𝑠𝑖conditional𝜇subscript𝑠𝑖delimited-[]subscript𝑢𝑖superscriptsubscript𝑠𝑖′subscript𝑠𝑖\mathbbE_s_-i\leftarrow\mu[u_i(s_i,s_-i)]\geq\mathbbE_% s_i[u_i(s_i^\prime,s_-i)].blackboard_E start_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ← italic_μ | italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT [ italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) ] ≥ blackboard_E start_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ← italic_μ | italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT [ italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT , italic_s start_POSTSUBSCRIPT - italic_i end_POSTSUBSCRIPT ) ] . (8)

where μ|siconditional𝜇subscript𝑠𝑖\mu|s_iitalic_μ | italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT is the distribution μ𝜇\muitalic_μ conditioned on the i𝑖iitalic_i-th component being sisubscript𝑠𝑖s_iitalic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT. Notice that a classical correlated equilibrium p𝑝pitalic_p is a classical Nash equilibrium if p𝑝pitalic_p is a product distribution.

Correlated equilibria captures natural games such as the Traffic Light and the Battle of the Sexes ([VNRET97], Chapter 1). The set of CE also has good mathematical properties such as being convex (with Nash equilibria being some of the vertices of the polytope). Algorithmically, it is computationally benign for finding the best CE, measured by any linear function of payoffs, simply by solving a linear program (of polynomial size for games of constant players). A natural learning dynamics also leads to an approximate CE ([VNRET97], Chapter 4) which we will define next, and all CE in a graphical game with n𝑛nitalic_n players and with log(n)𝑛\log(n)roman_log ( italic_n ) degree can be found in polynomial time ([VNRET97], Chapter 7).

3 Quantum game without discord

In this section, we will address the question proposed at the end of the first section. Suppose that a game has two players and both of them have n𝑛nitalic_n strategies. In other words, each player holds an n𝑛nitalic_n-dimensional quantum system. Recall that we also require the shared quantum state ρ∈H⊗H𝜌tensor-product𝐻𝐻\rho\in H\otimes Hitalic_ρ ∈ italic_H ⊗ italic_H be symmetric, so that swapping the two systems does not change the state. It is not hard to derive from the general criteria of zero-discord state [DVB10] that these quantum states ρ𝜌\rhoitalic_ρ have the form of

ρ=∑i,j=0n-1p(i,j)|ψi⟩⟨ψi|⊗|ψj⟩⟨ψj|,𝜌superscriptsubscript𝑖𝑗0𝑛1tensor-product𝑝𝑖𝑗ketsubscript𝜓𝑖brasubscript𝜓𝑖ketsubscript𝜓𝑗brasubscript𝜓𝑗\rho=\sum_i,j=0^n-1p(i,j)|\psi_i\rangle\langle\psi_i|\otimes|\psi_j% \rangle\langle\psi_j|,italic_ρ = ∑ start_POSTSUBSCRIPT italic_i , italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n - 1 end_POSTSUPERSCRIPT italic_p ( italic_i , italic_j ) | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | ⊗ | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | , (9)

where ψi⟩ketsubscript𝜓𝑖\ is a set of orthogonal basis of the n𝑛nitalic_n-dimensional Hilbert space H𝐻Hitalic_H, and P=[p(i,j)]ij∈ℝ+n×n𝑃subscriptdelimited-[]𝑝𝑖𝑗𝑖𝑗superscriptsubscriptℝ𝑛𝑛P=[p(i,j)]_ij\in\mbox$\mathbbR$_+^n\times nitalic_P = [ italic_p ( italic_i , italic_j ) ] start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ∈ blackboard_R start_POSTSUBSCRIPT + end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n × italic_n end_POSTSUPERSCRIPT is a symmetric matrix with nonnegative entries satisfying that ∑ijp(i,j)=1subscript𝑖𝑗𝑝𝑖𝑗1\sum_ijp(i,j)=1∑ start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT italic_p ( italic_i , italic_j ) = 1. (In general, we use the upper case letter P𝑃Pitalic_P to denote the matrix and the lower case letter p𝑝pitalic_p to denote the corresponding two-variate distribution p(i,j)𝑝𝑖𝑗p(i,j)italic_p ( italic_i , italic_j ).) We sometimes also write the state as

ρ=∑ip1(i)|ψi⟩⟨ψi|⊗σi𝜌subscript𝑖tensor-productsubscript𝑝1𝑖ketsubscript𝜓𝑖brasubscript𝜓𝑖subscript𝜎𝑖\rho=\sum_ip_1(i)|\psi_i\rangle\langle\psi_i|\otimes\sigma_iitalic_ρ = ∑ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | ⊗ italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT (10)

where p1(i)=∑jp(i,j)subscript𝑝1𝑖subscript𝑗𝑝𝑖𝑗p_1(i)=\sum_jp(i,j)italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) = ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_p ( italic_i , italic_j ) is the marginal distribution on the first system, and σi=∑jp(i,j)p1(i)|ψj⟩⟨ψj|subscript𝜎𝑖subscript𝑗𝑝𝑖𝑗subscript𝑝1𝑖ketsubscript𝜓𝑗brasubscript𝜓𝑗\sigma_i=\sum_j\fracp(i,j)p_1(i)|\psi_j\rangle\langle\psi_j|italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT divide start_ARG italic_p ( italic_i , italic_j ) end_ARG start_ARG italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) end_ARG | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | (if p1(i)=0subscript𝑝1𝑖0p_1(i)=0italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) = 0 then let σi=|0⟩⟨0|subscript𝜎𝑖ket0bra0\sigma_i=|0\rangle\langle 0|italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = | 0 ⟩ ⟨ 0 |). Gaming news

Consider the following game as a natural extension of the Penny Matching game in Section 1. The payoff matrices are

U1=nI-J and U2=-U1,formulae-sequencesubscript𝑈1𝑛𝐼𝐽𝑎𝑛𝑑subscript𝑈2subscript𝑈1U_1=nI-J\quad and\quad U_2=-U_1,italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = italic_n italic_I - italic_J italic_a italic_n italic_d italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = - italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , (11)

where J𝐽Jitalic_J is the all-one matrix. Intuitively, whoever takes the first matrix bets that the two n𝑛nitalic_n-sided dice give the same side, and the other player bets that the two dice give different sides. We first show that there is a unique correlated equilibrium in the game.

Lemma 1

The game given by Eq.(11) has only one classical correlated equilibrium Q=J/n2𝑄𝐽superscript𝑛2Q=J/n^2italic_Q = italic_J / italic_n start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT.

Proof: According to the definition of correlated equilibrium, if a distribution q𝑞qitalic_q on [n]×[n]delimited-[]𝑛delimited-[]𝑛[n]\times[n][ italic_n ] × [ italic_n ] is a classical correlated equilibrium, then the following relationships hold:

∑jq(i,j)U1(i,j)≥∑jq(i,j)U1(i′,j),∀i,i′∈0,1,…,n-1,formulae-sequencesubscript𝑗𝑞𝑖𝑗subscript𝑈1𝑖𝑗subscript𝑗𝑞𝑖𝑗subscript𝑈1superscript𝑖′𝑗for-all𝑖superscript𝑖′01…𝑛1\sum_jq(i,j)U_1(i,j)\geq\sum_jq(i,j)U_1(i^\prime,j),\qquad\forall i,% i^\prime\in\0,1,...,n-1\,∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_q ( italic_i , italic_j ) italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i , italic_j ) ≥ ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_q ( italic_i , italic_j ) italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT , italic_j ) , ∀ italic_i , italic_i start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ∈ 0 , 1 , … , italic_n - 1 , (12)

and

∑iq(i,j)U2(i,j)≥∑iq(i,j)U2(i,j′),∀j,j′∈0,1,…,n-1.formulae-sequencesubscript𝑖𝑞𝑖𝑗subscript𝑈2𝑖𝑗subscript𝑖𝑞𝑖𝑗subscript𝑈2𝑖superscript𝑗′for-all𝑗superscript𝑗′01…𝑛1\sum_iq(i,j)U_2(i,j)\geq\sum_iq(i,j)U_2(i,j^\prime),\qquad\forall j,% j^\prime\in\0,1,...,n-1\.∑ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ( italic_i , italic_j ) italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ( italic_i , italic_j ) ≥ ∑ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ( italic_i , italic_j ) italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ( italic_i , italic_j start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ) , ∀ italic_j , italic_j start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ∈ 0 , 1 , … , italic_n - 1 . (13)

Plugging the definition of U1subscript𝑈1U_1italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT and U2subscript𝑈2U_2italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT into the above inequalities, one can verify that Q=J/n2𝑄𝐽superscript𝑛2Q=J/n^2italic_Q = italic_J / italic_n start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT is the only solution.

Recall that ρ=∑ip1(i)|ψi⟩⟨ψi|⊗σi𝜌subscript𝑖tensor-productsubscript𝑝1𝑖ketsubscript𝜓𝑖brasubscript𝜓𝑖subscript𝜎𝑖\rho=\sum_ip_1(i)|\psi_i\rangle\langle\psi_i|\otimes\sigma_iitalic_ρ = ∑ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | ⊗ italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT. Since ρ𝜌\rhoitalic_ρ is symmetric, it does not matter which part the classical player, Player 2, chooses to hold. For the convenience of discussions, let us assume that the classical player takes the second part. We use 𝚜𝚞𝚙𝚙(p)𝚜𝚞𝚙𝚙𝑝\mbox\ttsupp(p)supp ( italic_p ) to denote the support of a distribution p𝑝pitalic_p, i.e. the set of elements with non-zero probability. The next lemma gives a sufficient and necessary condition for the existence of quantum advantage.

Lemma 2

Suppose that measuring the state ρ𝜌\rhoitalic_ρ gives a classical correlated equilibrium for the game given in Eq.(11). Then Player 1 (who is quantum) does not have any advantage if and only if

⟨i|σj|i⟩=1/n,∀i∈0,1,…,n-1 and j∈𝚜𝚞𝚙𝚙(p1).formulae-sequencequantum-operator-product𝑖subscript𝜎𝑗𝑖1𝑛for-all𝑖01…𝑛1 and 𝑗𝚜𝚞𝚙𝚙subscript𝑝1\langle i|\sigma_j|i\rangle=1/n,\ \ \ \forall i\in\0,1,...,n-1\\text and % j\in\text\mbox\ttsupp(p_1).⟨ italic_i | italic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | italic_i ⟩ = 1 / italic_n , ∀ italic_i ∈ 0 , 1 , … , italic_n - 1 and italic_j ∈ supp ( italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) . (14)

Proof: “Only if”: Assume that Player 1 first measures her part in the orthonormal basis ketsubscript𝜓𝑖\ . Note that this does not affect the state. If outcome j𝑗jitalic_j occurs, then Player 1 knows that the state of Player 2 is σjsubscript𝜎𝑗\sigma_jitalic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT. We consider which utility matrix in Eq.(11) Player 1 has. In the first case, Player 1 takes the utility matrix U1subscript𝑈1U_1italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT. It is not hard to see that her optimal strategy is to replace her part |ψj⟩ketsubscript𝜓𝑗|\psi_j\rangle| italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ by |i⟩ket𝑖|i\rangle| italic_i ⟩, where i𝑖iitalic_i is a maximizer of maxi⟨i|σj|i⟩subscript𝑖conditional𝑖subscript𝜎𝑗𝑖\max_i\langle i|\sigma_j|i\rangleroman_max start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟨ italic_i | italic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | italic_i ⟩. Thus Player 1 has a strict positive advantage if and only if there is some i𝑖iitalic_i and j𝑗jitalic_j, where j∈𝚜𝚞𝚙𝚙(p1)𝑗𝚜𝚞𝚙𝚙subscript𝑝1j\in\mbox\ttsupp(p_1)italic_j ∈ supp ( italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ), with ⟨i|σj|i⟩>1/nquantum-operator-product𝑖subscript𝜎𝑗𝑖1𝑛\langle i|\sigma_j|i\rangle>1/n⟨ italic_i | italic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | italic_i ⟩ >1 / italic_n, which is equivalent to saying that there is some i𝑖iitalic_i and j∈𝚜𝚞𝚙𝚙(p1)𝑗𝚜𝚞𝚙𝚙subscript𝑝1j\in\mbox\ttsupp(p_1)italic_j ∈ supp ( italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) with ⟨i|σj|i⟩≠1/nquantum-operator-product𝑖subscript𝜎𝑗𝑖1𝑛\langle i|\sigma_j|i\rangle

eq 1/n⟨ italic_i | italic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | italic_i ⟩ ≠ 1 / italic_n.

Similarly, if Player 1 takes the utility matrix U2subscript𝑈2U_2italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT, then her optimal strategy is to replace |ψj⟩ketsubscript𝜓𝑗|\psi_j\rangle| italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ with |i⟩ket𝑖|i\rangle| italic_i ⟩, where i𝑖iitalic_i is a minimizer of mini⟨i|σj|i⟩subscript𝑖conditional𝑖subscript𝜎𝑗𝑖\min_i\langle i|\sigma_j|i\rangleroman_min start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟨ italic_i | italic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | italic_i ⟩. Thus Player 1 has a strict positive advantage if and only if there is some i𝑖iitalic_i and j𝑗jitalic_j with ⟨i|σj|i⟩<1/nquantum-operator-product𝑖subscript𝜎𝑗𝑖1𝑛\langle i|\sigma_j|i\rangle<1/n⟨ italic_i | italic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | italic_i ⟩ <1 / italic_n, which is again equivalent to saying that there is some i𝑖iitalic_i and j𝑗jitalic_j with ⟨i|σj|i⟩≠1/nquantum-operator-product𝑖subscript𝜎𝑗𝑖1𝑛\langle i|\sigma_j|i\rangle

eq 1/n⟨ italic_i | italic_σ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | italic_i ⟩ ≠ 1 / italic_n.

“If”: Player 2 measures her part in the computational basis, yielding the state

1n∑i,jp1(j)|ψj⟩⟨ψj|⊗|i⟩⟨i|.1𝑛subscript𝑖𝑗tensor-productsubscript𝑝1𝑗ketsubscript𝜓𝑗brasubscript𝜓𝑗ket𝑖bra𝑖\frac1n\sum_i,jp_1(j)|\psi_j\rangle\langle\psi_j|\otimes|i\rangle% \langle i|.divide start_ARG 1 end_ARG start_ARG italic_n end_ARG ∑ start_POSTSUBSCRIPT italic_i , italic_j end_POSTSUBSCRIPT italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_j ) | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | ⊗ | italic_i ⟩ ⟨ italic_i | .

Now whatever quantum operation Player 1 applies, the probability of observing the same bits (i.e. the state after the measurement is |ii⟩ket𝑖𝑖|ii\rangle| italic_i italic_i ⟩ for some i𝑖iitalic_i) is 1/n1𝑛1/n1 / italic_n, with the expected payoff of 0 for both players.

Though the above lemma gives a sufficient and necessary condition, it is still not always clear whether quantum advantage could exist for any symmetric state ρ𝜌\rhoitalic_ρ with zero discord. Next we will further the study by considering a related matrix M∈ℝ+n×n𝑀superscriptsubscriptℝ𝑛𝑛M\in\mbox$\mathbbR$_+^n\times nitalic_M ∈ blackboard_R start_POSTSUBSCRIPT + end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n × italic_n end_POSTSUPERSCRIPT, whose (i,j)𝑖𝑗(i,j)( italic_i , italic_j )-th entry is defined to be

M(i,j)=|⟨i|ψj⟩|2.𝑀𝑖𝑗superscriptinner-product𝑖subscript𝜓𝑗2M(i,j)=|\langle i|\psi_j\rangle|^2.italic_M ( italic_i , italic_j ) = | ⟨ italic_i | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT . (15)

It turns out that the rank of M𝑀Mitalic_M is an important criteria to our question. In the rest of this section, we will consider two cases, depending on whether M𝑀Mitalic_M is full rank or not.

3.1 Case 1: M𝑀Mitalic_M is full-rank

We will first show that if M𝑀Mitalic_M is full-rank, then the quantum player cannot have any advantage. Gaming news

Theorem 3

Suppose that the two players of the game Eq.(11) share a symmetric state ρ𝜌\rhoitalic_ρ, measuring which gives a classical correlated equilibrium. Then Player 1 (who is quantum) does not have any advantage if M𝑀Mitalic_M in Eq.(15) is full-rank.

Proof: By Lemma 1, for any 0≤k,j≤n-1formulae-sequence0𝑘𝑗𝑛10\leq k,j\leq n-10 ≤ italic_k , italic_j ≤ italic_n - 1 we have

∑i=0n-1p1(i)|⟨k|ψi⟩|2⋅⟨j|σi|j⟩=1n2superscriptsubscript𝑖0𝑛1⋅subscript𝑝1𝑖superscriptinner-product𝑘subscript𝜓𝑖2quantum-operator-product𝑗subscript𝜎𝑖𝑗1superscript𝑛2\sum_i=0^n-1p_1(i)|\langle k|\psi_i\rangle|^2\cdot\langle j|\sigma_% i|j\rangle=\frac1n^2∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n - 1 end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) | ⟨ italic_k | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ⋅ ⟨ italic_j | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_j ⟩ = divide start_ARG 1 end_ARG start_ARG italic_n start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG

Summing over j𝑗jitalic_j, we obtain another equality

∑i=0n-1p1(i)|⟨k|ψi⟩|2=1n.superscriptsubscript𝑖0𝑛1subscript𝑝1𝑖superscriptinner-product𝑘subscript𝜓𝑖21𝑛\sum_i=0^n-1p_1(i)|\langle k|\psi_i\rangle|^2=\frac1n.∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n - 1 end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) | ⟨ italic_k | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT = divide start_ARG 1 end_ARG start_ARG italic_n end_ARG .

Combining these two equalities, we have

∑i=0n-1|⟨k|ψi⟩|2⋅p1(i)(⟨j|σi|j⟩-1n)=0.superscriptsubscript𝑖0𝑛1⋅superscriptinner-product𝑘subscript𝜓𝑖2subscript𝑝1𝑖quantum-operator-product𝑗subscript𝜎𝑖𝑗1𝑛0\sum_i=0^n-1|\langle k|\psi_i\rangle|^2\cdot p_1(i)\left(\langle j|% \sigma_i|j\rangle-\frac1n\right)=0.∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n - 1 end_POSTSUPERSCRIPT | ⟨ italic_k | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ⋅ italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) ( ⟨ italic_j | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_j ⟩ - divide start_ARG 1 end_ARG start_ARG italic_n end_ARG ) = 0 .

Define a matrix A=[a(i,j)]ij∈ℝn×n𝐴subscriptdelimited-[]𝑎𝑖𝑗𝑖𝑗superscriptℝ𝑛𝑛A=[a(i,j)]_ij\in\mbox$\mathbbR$^n\times nitalic_A = [ italic_a ( italic_i , italic_j ) ] start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ∈ blackboard_R start_POSTSUPERSCRIPT italic_n × italic_n end_POSTSUPERSCRIPT by a(i,j)=p1(i)(⟨j|σi|j⟩-1n)𝑎𝑖𝑗subscript𝑝1𝑖quantum-operator-product𝑗subscript𝜎𝑖𝑗1𝑛a(i,j)=p_1(i)\left(\langle j|\sigma_i|j\rangle-\frac1n\right)italic_a ( italic_i , italic_j ) = italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) ( ⟨ italic_j | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_j ⟩ - divide start_ARG 1 end_ARG start_ARG italic_n end_ARG ). Then the above equality is just ∑iM(k,i)a(i,j)=0subscript𝑖𝑀𝑘𝑖𝑎𝑖𝑗0\sum_iM(k,i)a(i,j)=0∑ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_M ( italic_k , italic_i ) italic_a ( italic_i , italic_j ) = 0 for all k,j𝑘𝑗k,jitalic_k , italic_j. In other words, we have

M⋅A=0.⋅𝑀𝐴0M\cdot A=0.italic_M ⋅ italic_A = 0 . (16)

Since the matrix M𝑀Mitalic_M is assumed to be full-rank, we have A=M-10=0𝐴superscript𝑀100A=M^-10=0italic_A = italic_M start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT 0 = 0. The conclusion thus follows by Lemma 2.

Two corollaries are in order. First, note that M𝑀Mitalic_M is full-rank for a generic orthogonal basis ketsubscript𝜓𝑖\ , it is generically true that no discord implies no quantum advantage.

Corollary 4

If a set of orthonormal basis ketsubscript𝜓𝑖\\psi_i\rangle\ is picked uniformly at random, then with probability 1, the quantum player does not have any advantage.

The second corollary considers the case of n=2𝑛2n=2italic_n = 2, which is settled by the above theorem completely. Indeed, when n=2𝑛2n=2italic_n = 2, the rank of M𝑀Mitalic_M is either 1 or 2. The rank-2 case is handled by the above theorem. If the rank is 1, it is not hard to see that the only possible M𝑀Mitalic_M is M=[1/21/21/21/2]𝑀matrix12121212M=\beginbmatrix1/2&1/2\\ 1/2&1/2\endbmatrixitalic_M = [ start_ARG start_ROW start_CELL 1 / 2 end_CELL start_CELL 1 / 2 end_CELL end_ROW start_ROW start_CELL 1 / 2 end_CELL start_CELL 1 / 2 end_CELL end_ROW end_ARG ]. In this case, for any i𝑖iitalic_i and any k𝑘kitalic_k it holds that

⟨k|σi|k⟩=⟨k|(∑jp(j|i)|ψj⟩⟨ψj|)|k⟩=∑jp(j|i)|⟨k|ψj⟩|2=12∑jp(j|i)=12.quantum-operator-product𝑘subscript𝜎𝑖𝑘bra𝑘subscript𝑗𝑝conditional𝑗𝑖ketsubscript𝜓𝑗brasubscript𝜓𝑗ket𝑘subscript𝑗𝑝conditional𝑗𝑖superscriptinner-product𝑘subscript𝜓𝑗212subscript𝑗𝑝conditional𝑗𝑖12\langle k|\sigma_i|k\rangle=\langle k|\Big(\sum_jp(j|i)|\psi_j\rangle% \langle\psi_j|\Big)|k\rangle=\sum_jp(j|i)|\langle k|\psi_j\rangle|^2% =\frac12\sum_jp(j|i)=\frac12.⟨ italic_k | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_k ⟩ = ⟨ italic_k | ( ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_p ( italic_j | italic_i ) | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | ) | italic_k ⟩ = ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_p ( italic_j | italic_i ) | ⟨ italic_k | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT = divide start_ARG 1 end_ARG start_ARG 2 end_ARG ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_p ( italic_j | italic_i ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG .

Applying Lemma 2, we thus get the following corollary.

Corollary 5

There is no quantum advantage for the game defined in Eq.(1) on any symmetric state ρ𝜌\rhoitalic_ρ with zero discord.

3.2 Case 2: M𝑀Mitalic_M is not full rank

Somewhat surprisingly, the quantum player can have an advantage when M𝑀Mitalic_M is not full-rank. In this section we exhibit a counterexample for n=3𝑛3n=3italic_n = 3. In this case, recall that the payoff matrices are

U1=(2-1-1-12-1-1-12) and U2=(-2111-2111-2).formulae-sequencesubscript𝑈1matrix211121112 and subscript𝑈2matrix211121112U_1=\beginpmatrix2&-1&-1\\ -1&2&-1\\ -1&-1&2\endpmatrix\quad\text and \quad U_2=\beginpmatrix-2&1&1\\ 1&-2&1\\ 1&1&-2\endpmatrix.italic_U start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = ( start_ARG start_ROW start_CELL 2 end_CELL start_CELL - 1 end_CELL start_CELL - 1 end_CELL end_ROW start_ROW start_CELL - 1 end_CELL start_CELL 2 end_CELL start_CELL - 1 end_CELL end_ROW start_ROW start_CELL - 1 end_CELL start_CELL - 1 end_CELL start_CELL 2 end_CELL end_ROW end_ARG ) and italic_U start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = ( start_ARG start_ROW start_CELL - 2 end_CELL start_CELL 1 end_CELL start_CELL 1 end_CELL end_ROW start_ROW start_CELL 1 end_CELL start_CELL - 2 end_CELL start_CELL 1 end_CELL end_ROW start_ROW start_CELL 1 end_CELL start_CELL 1 end_CELL start_CELL - 2 end_CELL end_ROW end_ARG ) . (17)

We consider the following quantum state,

ρ=∑i,j=02p(i,j)|ψi⟩⟨ψi|⊗|ψj⟩⟨ψj|,𝜌superscriptsubscript𝑖𝑗02tensor-product𝑝𝑖𝑗ketsubscript𝜓𝑖brasubscript𝜓𝑖ketsubscript𝜓𝑗brasubscript𝜓𝑗\rho=\sum_i,j=0^2p(i,j)|\psi_i\rangle\langle\psi_i|\otimes|\psi_j% \rangle\langle\psi_j|,italic_ρ = ∑ start_POSTSUBSCRIPT italic_i , italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_p ( italic_i , italic_j ) | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | ⊗ | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ ⟨ italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | , (18)

where

|ψ0⟩=12(|0⟩+|1⟩),|ψ1⟩=12(|0⟩-|1⟩),|ψ2⟩=|2⟩.formulae-sequenceketsubscript𝜓012ket0ket1formulae-sequenceketsubscript𝜓112ket0ket1ketsubscript𝜓2ket2\displaystyle|\psi_0\rangle=\frac1\sqrt2\left(|0\rangle+|1\rangle% \right),\quad|\psi_1\rangle=\frac1\sqrt2\left(|0\rangle-|1\rangle% \right),\quad|\psi_2\rangle=|2\rangle.| italic_ψ start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ⟩ = divide start_ARG 1 end_ARG start_ARG square-root start_ARG 2 end_ARG end_ARG ( | 0 ⟩ + | 1 ⟩ ) , | italic_ψ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ⟩ = divide start_ARG 1 end_ARG start_ARG square-root start_ARG 2 end_ARG end_ARG ( | 0 ⟩ - | 1 ⟩ ) , | italic_ψ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ⟩ = | 2 ⟩ . (19)

It is not hard to calculate M𝑀Mitalic_M:

M=(1/21/201/21/20001).𝑀matrix1212012120001M=\beginpmatrix1/2&1/2&0\\ 1/2&1/2&0\\ 0&0&1\endpmatrix.italic_M = ( start_ARG start_ROW start_CELL 1 / 2 end_CELL start_CELL 1 / 2 end_CELL start_CELL 0 end_CELL end_ROW start_ROW start_CELL 1 / 2 end_CELL start_CELL 1 / 2 end_CELL start_CELL 0 end_CELL end_ROW start_ROW start_CELL 0 end_CELL start_CELL 0 end_CELL start_CELL 1 end_CELL end_ROW end_ARG ) . (20)

which has rank 2. Define

P=(4/900002/902/91/9).𝑃matrix4900002902919P=\beginpmatrix4/9&0&0\\ 0&0&2/9\\ 0&2/9&1/9\endpmatrix.italic_P = ( start_ARG start_ROW start_CELL 4 / 9 end_CELL start_CELL 0 end_CELL start_CELL 0 end_CELL end_ROW start_ROW start_CELL 0 end_CELL start_CELL 0 end_CELL start_CELL 2 / 9 end_CELL end_ROW start_ROW start_CELL 0 end_CELL start_CELL 2 / 9 end_CELL start_CELL 1 / 9 end_CELL end_ROW end_ARG ) . (21)

It can be easily verified that if the two players measure the state in computational basis, the probability distribution yielded is uniform, which is a classical Nash equilibrium.

Now suppose that Player 1 uses a quantum computer. One can verify that the condition in Lemma 2 does not hold. For a concrete illustration, let us consider the protocol in Lemma 2 again. Player 1 first measures in the basis ketketket2\ . With probability 4/9, she observes |+⟩ket|+\rangle| + ⟩, then changes it to |0⟩ket0|0\rangle| 0 ⟩. Player 2’s state is also |+⟩ket|+\rangle| + ⟩ in this case, thus a measurement in the computational basis gives the |00⟩ket00|00\rangle| 00 ⟩ and |01⟩ket01|01\rangle| 01 ⟩ each with half probability. Thus Player 1’s payoff in this case is 2⋅12-1⋅12=12⋅212⋅112122\cdot\frac12-1\cdot\frac12=\frac122 ⋅ divide start_ARG 1 end_ARG start_ARG 2 end_ARG - 1 ⋅ divide start_ARG 1 end_ARG start_ARG 2 end_ARG = divide start_ARG 1 end_ARG start_ARG 2 end_ARG. The second case is that Player 1 observes |-⟩ket|-\rangle| - ⟩, which happens with probability 2/9, and Player 2’s state is |2⟩ket2|2\rangle| 2 ⟩ for sure. Player 1 changes her part to |2⟩ket2|2\rangle| 2 ⟩, and gets payoff 2222. The third case is that Player 1 observes |2⟩ket2|2\rangle| 2 ⟩, which happens with probability 1/3, leaving Player 2 σ3=(2/3)|1⟩⟨1|+(1/3)|2⟩⟨2|subscript𝜎323ket1quantum-operator-product1132bra2\sigma_3=(2/3)|1\rangle\langle 1|+(1/3)|2\rangle\langle 2|italic_σ start_POSTSUBSCRIPT 3 end_POSTSUBSCRIPT = ( 2 / 3 ) | 1 ⟩ ⟨ 1 | + ( 1 / 3 ) | 2 ⟩ ⟨ 2 |. Player 1 then changes her qubit to |1⟩ket1|1\rangle| 1 ⟩, collides with Player 2’s outcome with probability 1/3, thus Player 1’s payoff is 2⋅13-1⋅23=0⋅213⋅12302\cdot\frac13-1\cdot\frac23=02 ⋅ divide start_ARG 1 end_ARG start_ARG 3 end_ARG - 1 ⋅ divide start_ARG 2 end_ARG start_ARG 3 end_ARG = 0. On average, the quantum player has a payoff of (4/9)(1/2)+(2/9)⋅2+(1/3)⋅0=2/3.4912⋅292⋅13023(4/9)(1/2)+(2/9)\cdot 2+(1/3)\cdot 0=2/3.( 4 / 9 ) ( 1 / 2 ) + ( 2 / 9 ) ⋅ 2 + ( 1 / 3 ) ⋅ 0 = 2 / 3 .

It should be pointed out that the matrix P𝑃Pitalic_P achieving the quantum advantage of 2/3 is not unique. For example, the following matrix also works with the same effect:

P=(2/92/90002/91/91/91/9).𝑃matrix292900029191919P=\beginpmatrix2/9&2/9&0\\ 0&0&2/9\\ 1/9&1/9&1/9\endpmatrix.italic_P = ( start_ARG start_ROW start_CELL 2 / 9 end_CELL start_CELL 2 / 9 end_CELL start_CELL 0 end_CELL end_ROW start_ROW start_CELL 0 end_CELL start_CELL 0 end_CELL start_CELL 2 / 9 end_CELL end_ROW start_ROW start_CELL 1 / 9 end_CELL start_CELL 1 / 9 end_CELL start_CELL 1 / 9 end_CELL end_ROW end_ARG ) . (22)

3.3 Optimization

In this subsection, we show that the 3-dimensional example in the above subsection is actually optimal for M𝑀Mitalic_M defined in Eq.(20). Actually the theorem below shows more. Note that if the rank of M𝑀Mitalic_M is 1, it is easy to prove that M𝑀Mitalic_M must be the uniform matrix, and the quantum advantage must be zero, thus in the following we suppose the rank of M𝑀Mitalic_M to be 2.

Theorem 6

Suppose that measuring the state ρ𝜌\rhoitalic_ρ gives a classical correlated equilibrium. Suppose the columns of M𝑀Mitalic_M are M0,M1superscript𝑀0superscript𝑀1M^0,M^1italic_M start_POSTSUPERSCRIPT 0 end_POSTSUPERSCRIPT , italic_M start_POSTSUPERSCRIPT 1 end_POSTSUPERSCRIPT and M2superscript𝑀2M^2italic_M start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT. Without loss of generality, suppose M0=xM1+(1-x)M2superscript𝑀0𝑥superscript𝑀11𝑥superscript𝑀2M^0=xM^1+(1-x)M^2italic_M start_POSTSUPERSCRIPT 0 end_POSTSUPERSCRIPT = italic_x italic_M start_POSTSUPERSCRIPT 1 end_POSTSUPERSCRIPT + ( 1 - italic_x ) italic_M start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT, where 0≤x≤10𝑥10\leq x\leq 10 ≤ italic_x ≤ 1. Then the quantum advantage

QA≤13+13xb,𝑄𝐴1313subscript𝑥𝑏QA\leq\frac13+\frac13x_b,italic_Q italic_A ≤ divide start_ARG 1 end_ARG start_ARG 3 end_ARG + divide start_ARG 1 end_ARG start_ARG 3 italic_x start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT end_ARG , (23)

where xb=maxx,1-xsubscript𝑥𝑏𝑥1𝑥x_b=\max\x,1-x\italic_x start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT = roman_max italic_x , 1 - italic_x .

Proof: By Lemma 1, for any 0≤k,l≤2formulae-sequence0𝑘𝑙20\leq k,l\leq 20 ≤ italic_k , italic_l ≤ 2 we have

∑i,j=02p(i,j)|⟨k|ψi⟩|2⋅|⟨l|ψj⟩|2=19.superscriptsubscript𝑖𝑗02⋅𝑝𝑖𝑗superscriptinner-product𝑘subscript𝜓𝑖2superscriptinner-product𝑙subscript𝜓𝑗219\sum_i,j=0^2p(i,j)|\langle k|\psi_i\rangle|^2\cdot|\langle l|\psi_j% \rangle|^2=\frac19.∑ start_POSTSUBSCRIPT italic_i , italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_p ( italic_i , italic_j ) | ⟨ italic_k | italic_ψ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ⋅ | ⟨ italic_l | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT = divide start_ARG 1 end_ARG start_ARG 9 end_ARG . (24)

This turns out to be equivalent to

M⋅P⋅MT=J9.⋅𝑀𝑃superscript𝑀𝑇𝐽9M\cdot P\cdot M^T=\fracJ9.italic_M ⋅ italic_P ⋅ italic_M start_POSTSUPERSCRIPT italic_T end_POSTSUPERSCRIPT = divide start_ARG italic_J end_ARG start_ARG 9 end_ARG . (25)

Noting that M⋅(J/9)⋅MT=J/9⋅𝑀𝐽9superscript𝑀𝑇𝐽9M\cdot(J/9)\cdot M^T=J/9italic_M ⋅ ( italic_J / 9 ) ⋅ italic_M start_POSTSUPERSCRIPT italic_T end_POSTSUPERSCRIPT = italic_J / 9, we know that P𝑃Pitalic_P can be expressed as

P=J9+P¯,𝑃𝐽9¯𝑃P=\fracJ9+\barP,italic_P = divide start_ARG italic_J end_ARG start_ARG 9 end_ARG + over¯ start_ARG italic_P end_ARG , (26)

where M⋅P¯⋅MT=0⋅𝑀¯𝑃superscript𝑀𝑇0M\cdot\barP\cdot M^T=0italic_M ⋅ over¯ start_ARG italic_P end_ARG ⋅ italic_M start_POSTSUPERSCRIPT italic_T end_POSTSUPERSCRIPT = 0. By straightforward calculation, one can show that Eq.(26) indicates

M⋅P¯=0.⋅𝑀¯𝑃0M\cdot\barP=0.italic_M ⋅ over¯ start_ARG italic_P end_ARG = 0 . (27)

Considering the form of M𝑀Mitalic_M, P¯¯𝑃\barPover¯ start_ARG italic_P end_ARG can now be expressed as

P¯=(k0k1k2-k0x-k1x-k2x-k0(1-x)-k1(1-x)-k2(1-x)),¯𝑃matrixsubscript𝑘0subscript𝑘1subscript𝑘2subscript𝑘0𝑥subscript𝑘1𝑥subscript𝑘2𝑥subscript𝑘01𝑥subscript𝑘11𝑥subscript𝑘21𝑥\barP=\beginpmatrixk_0&k_1&k_2\\ -k_0x&-k_1x&-k_2x\\ -k_0(1-x)&-k_1(1-x)&-k_2(1-x)\endpmatrix,over¯ start_ARG italic_P end_ARG = ( start_ARG start_ROW start_CELL italic_k start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT end_CELL start_CELL italic_k start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT end_CELL start_CELL italic_k start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT end_CELL end_ROW start_ROW start_CELL - italic_k start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT italic_x end_CELL start_CELL - italic_k start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT italic_x end_CELL start_CELL - italic_k start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT italic_x end_CELL end_ROW start_ROW start_CELL - italic_k start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ( 1 - italic_x ) end_CELL start_CELL - italic_k start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( 1 - italic_x ) end_CELL start_CELL - italic_k start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ( 1 - italic_x ) end_CELL end_ROW end_ARG ) , (28)

where k0,k1subscript𝑘0subscript𝑘1k_0,k_1italic_k start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_k start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT and k2subscript𝑘2k_2italic_k start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT are real numbers.

According to the discussion above, we know that the maximal quantum advantage is

QA=∑i=02p1(i)[2⋅⟨li|σi|li⟩-1⋅(1-⟨li|σi|li⟩)],𝑄𝐴superscriptsubscript𝑖02subscript𝑝1𝑖delimited-[]⋅2quantum-operator-productsubscript𝑙𝑖subscript𝜎𝑖subscript𝑙𝑖⋅11quantum-operator-productsubscript𝑙𝑖subscript𝜎𝑖subscript𝑙𝑖QA=\sum_i=0^2p_1(i)[2\cdot\langle l_i|\sigma_i|l_i\rangle-1\cdot(1% -\langle l_i|\sigma_i|l_i\rangle)],italic_Q italic_A = ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) [ 2 ⋅ ⟨ italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ - 1 ⋅ ( 1 - ⟨ italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ ) ] , (29)

where li=maxl⟨l|σi|l⟩subscript𝑙𝑖subscript𝑙conditional𝑙subscript𝜎𝑖𝑙l_i=\max_l\langle l|\sigma_i|l\rangleitalic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = roman_max start_POSTSUBSCRIPT italic_l end_POSTSUBSCRIPT ⟨ italic_l | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_l ⟩. Then it holds that

QA𝑄𝐴\displaystyle QAitalic_Q italic_A =3∑i=02p1(i)⋅⟨li|σi|li⟩-1absent3superscriptsubscript𝑖02⋅subscript𝑝1𝑖quantum-operator-productsubscript𝑙𝑖subscript𝜎𝑖subscript𝑙𝑖1\displaystyle=3\sum_i=0^2p_1(i)\cdot\langle l_i|\sigma_i|l_i% \rangle-1= 3 ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_i ) ⋅ ⟨ italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_σ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ⟩ - 1

=3∑i,j=02p(i,j)|⟨li|ψj⟩|2-1absent3superscriptsubscript𝑖𝑗02𝑝𝑖𝑗superscriptinner-productsubscript𝑙𝑖subscript𝜓𝑗21\displaystyle=3\sum_i,j=0^2p(i,j)|\langle l_i|\psi_j\rangle|^2-1= 3 ∑ start_POSTSUBSCRIPT italic_i , italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_p ( italic_i , italic_j ) | ⟨ italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT - 1

=3∑i,j=02(19+p¯(i,j))|⟨li|ψj⟩|2-1absent3superscriptsubscript𝑖𝑗0219¯𝑝𝑖𝑗superscriptinner-productsubscript𝑙𝑖subscript𝜓𝑗21\displaystyle=3\sum_i,j=0^2\left(\frac19+\barp(i,j)\right)|\langle l% _i|\psi_j\rangle|^2-1= 3 ∑ start_POSTSUBSCRIPT italic_i , italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ( divide start_ARG 1 end_ARG start_ARG 9 end_ARG + over¯ start_ARG italic_p end_ARG ( italic_i , italic_j ) ) | ⟨ italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT - 1

=3∑i=02(∑j=02p¯(i,j)|⟨li|ψj⟩|2),absent3superscriptsubscript𝑖02superscriptsubscript𝑗02¯𝑝𝑖𝑗superscriptinner-productsubscript𝑙𝑖subscript𝜓𝑗2\displaystyle=3\sum_i=0^2\left(\sum_j=0^2\barp(i,j)|\langle l_i|% \psi_j\rangle|^2\right),= 3 ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT over¯ start_ARG italic_p end_ARG ( italic_i , italic_j ) | ⟨ italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) ,

where p¯(i,j)¯𝑝𝑖𝑗\barp(i,j)over¯ start_ARG italic_p end_ARG ( italic_i , italic_j ) is the element of P¯¯𝑃\barPover¯ start_ARG italic_P end_ARG. At the same time, it can be obtained that li=maxl∑jp¯(i,j)|⟨l|ψj⟩|2subscript𝑙𝑖subscript𝑙subscript𝑗¯𝑝𝑖𝑗superscriptinner-product𝑙subscript𝜓𝑗2l_i=\max_l\sum_j\barp(i,j)|\langle l|\psi_j\rangle|^2italic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = roman_max start_POSTSUBSCRIPT italic_l end_POSTSUBSCRIPT ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT over¯ start_ARG italic_p end_ARG ( italic_i , italic_j ) | ⟨ italic_l | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT. Besides, recall that the rank of M𝑀Mitalic_M is 2, then there must be one row of M𝑀Mitalic_M, say M2subscript𝑀2M_2italic_M start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT, has the form of aM0+(1-a)M1𝑎subscript𝑀01𝑎subscript𝑀1aM_0+(1-a)M_1italic_a italic_M start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT + ( 1 - italic_a ) italic_M start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT, where M0subscript𝑀0M_0italic_M start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT and M1subscript𝑀1M_1italic_M start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT are the other two rows of M𝑀Mitalic_M, and 0≤a≤10𝑎10\leq a\leq 10 ≤ italic_a ≤ 1. Then it can be known that every lisubscript𝑙𝑖l_iitalic_l start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT must be 00 or 1111. Based on the form of P¯¯𝑃\barPover¯ start_ARG italic_P end_ARG, we have that l0≠l1=l2subscript𝑙0subscript𝑙1subscript𝑙2l_0

eq l_1=l_2italic_l start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ≠ italic_l start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = italic_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT. Without loss of generality, we suppose l0=0subscript𝑙00l_0=0italic_l start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT = 0, and l1=l2=1subscript𝑙1subscript𝑙21l_1=l_2=1italic_l start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = italic_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = 1. Then

QA𝑄𝐴\displaystyle QAitalic_Q italic_A =3∑j=02p¯(0,j)|⟨0|ψj⟩|2+3∑j=02(p¯(1,j)+p¯(2,j))|⟨1|ψj⟩|2absent3superscriptsubscript𝑗02¯𝑝0𝑗superscriptinner-product0subscript𝜓𝑗23superscriptsubscript𝑗02¯𝑝1𝑗¯𝑝2𝑗superscriptinner-product1subscript𝜓𝑗2\displaystyle=3\sum_j=0^2\barp(0,j)|\langle 0|\psi_j\rangle|^2+3\sum% _j=0^2(\barp(1,j)+\barp(2,j))|\langle 1|\psi_j\rangle|^2= 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT over¯ start_ARG italic_p end_ARG ( 0 , italic_j ) | ⟨ 0 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT + 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ( over¯ start_ARG italic_p end_ARG ( 1 , italic_j ) + over¯ start_ARG italic_p end_ARG ( 2 , italic_j ) ) | ⟨ 1 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT

=3∑j=02p¯(0,j)|⟨0|ψj⟩|2-3∑j=02p¯(0,j)|⟨1|ψj⟩|2.absent3superscriptsubscript𝑗02¯𝑝0𝑗superscriptinner-product0subscript𝜓𝑗23superscriptsubscript𝑗02¯𝑝0𝑗superscriptinner-product1subscript𝜓𝑗2\displaystyle=3\sum_j=0^2\barp(0,j)|\langle 0|\psi_j\rangle|^2-3\sum% _j=0^2\barp(0,j)|\langle 1|\psi_j\rangle|^2.= 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT over¯ start_ARG italic_p end_ARG ( 0 , italic_j ) | ⟨ 0 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT - 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT over¯ start_ARG italic_p end_ARG ( 0 , italic_j ) | ⟨ 1 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT .

Note that P¯+J/9¯𝑃𝐽9\barP+J/9over¯ start_ARG italic_P end_ARG + italic_J / 9 is a matrix with nonnegative elements. Thus, for any 0≤i≤20𝑖20\leq i\leq 20 ≤ italic_i ≤ 2, if ki≥0subscript𝑘𝑖0k_i\geq 0italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≥ 0 we have

-kix≥-19 and -ki(1-x)≥-19,formulae-sequencesubscript𝑘𝑖𝑥19andsubscript𝑘𝑖1𝑥19-k_ix\geq-\frac19\quad\textand\quad-k_i(1-x)\geq-\frac19,- italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_x ≥ - divide start_ARG 1 end_ARG start_ARG 9 end_ARG and - italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( 1 - italic_x ) ≥ - divide start_ARG 1 end_ARG start_ARG 9 end_ARG , (30)

and if ki<0subscript𝑘𝑖0k_i<0italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT <0, we have -ki≤19subscript𝑘𝑖19-k_i\leq\frac19- italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≤ divide start_ARG 1 end_ARG start_ARG 9 end_ARG. And Eq.(30) indicates that if 0<x<10𝑥10<0 <italic_x <1,

ki≤19x and ki≤19(1-x),formulae-sequencesubscript𝑘𝑖19𝑥andsubscript𝑘𝑖191𝑥k_i\leq\frac19x\quad\textand\quad k_i\leq\frac19(1-x),italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≤ divide start_ARG 1 end_ARG start_ARG 9 italic_x end_ARG and italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≤ divide start_ARG 1 end_ARG start_ARG 9 ( 1 - italic_x ) end_ARG , (31)

which is equivalent to

ki≤19xb.subscript𝑘𝑖19subscript𝑥𝑏k_i\leq\frac19x_b.italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≤ divide start_ARG 1 end_ARG start_ARG 9 italic_x start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT end_ARG . (32)

Actually, Eq.(32) also holds when x=0𝑥0x=0italic_x = 0 or x=1𝑥1x=1italic_x = 1. Therefore, we obtain that

QA𝑄𝐴\displaystyle QAitalic_Q italic_A =3∑j=02p¯(0,j)|⟨0|ψj⟩|2-3∑j=02p¯(0,j)|⟨1|ψj⟩|2absent3superscriptsubscript𝑗02¯𝑝0𝑗superscriptinner-product0subscript𝜓𝑗23superscriptsubscript𝑗02¯𝑝0𝑗superscriptinner-product1subscript𝜓𝑗2\displaystyle=3\sum_j=0^2\barp(0,j)|\langle 0|\psi_j\rangle|^2-3\sum% _j=0^2\barp(0,j)|\langle 1|\psi_j\rangle|^2= 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT over¯ start_ARG italic_p end_ARG ( 0 , italic_j ) | ⟨ 0 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT - 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT over¯ start_ARG italic_p end_ARG ( 0 , italic_j ) | ⟨ 1 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT

=3∑j=02kj|⟨0|ψj⟩|2-3∑j=02kj|⟨1|ψj⟩|2absent3superscriptsubscript𝑗02subscript𝑘𝑗superscriptinner-product0subscript𝜓𝑗23superscriptsubscript𝑗02subscript𝑘𝑗superscriptinner-product1subscript𝜓𝑗2\displaystyle=3\sum_j=0^2k_j|\langle 0|\psi_j\rangle|^2-3\sum_j=0^% 2k_j|\langle 1|\psi_j\rangle|^2= 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_k start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | ⟨ 0 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT - 3 ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_k start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | ⟨ 1 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT

≤3⋅19xb+3⋅19absent⋅319subscript𝑥𝑏⋅319\displaystyle\leq 3\cdot\frac19x_b+3\cdot\frac19≤ 3 ⋅ divide start_ARG 1 end_ARG start_ARG 9 italic_x start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT end_ARG + 3 ⋅ divide start_ARG 1 end_ARG start_ARG 9 end_ARG

=13+13xb,absent1313subscript𝑥𝑏\displaystyle=\frac13+\frac13x_b,= divide start_ARG 1 end_ARG start_ARG 3 end_ARG + divide start_ARG 1 end_ARG start_ARG 3 italic_x start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT end_ARG ,

where the relationship ∑j|⟨0|ψj⟩|2=∑j|⟨1|ψj⟩|2=1subscript𝑗superscriptinner-product0subscript𝜓𝑗2subscript𝑗superscriptinner-product1subscript𝜓𝑗21\sum_j|\langle 0|\psi_j\rangle|^2=\sum_j|\langle 1|\psi_j\rangle|^2% =1∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | ⟨ 0 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT = ∑ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT | ⟨ 1 | italic_ψ start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ⟩ | start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT = 1 is utilized.

Go back to the example in the above subsection. Note that for M𝑀Mitalic_M in Eq.(20) we have M0=1⋅M1+0⋅M2superscript𝑀0⋅1superscript𝑀1⋅0superscript𝑀2M^0=1\cdot M^1+0\cdot M^2italic_M start_POSTSUPERSCRIPT 0 end_POSTSUPERSCRIPT = 1 ⋅ italic_M start_POSTSUPERSCRIPT 1 end_POSTSUPERSCRIPT + 0 ⋅ italic_M start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT(thus in order to utilize Theorem.6, we need to adjust the order of the columns). Thus we can choose x=0𝑥0x=0italic_x = 0, and then xb=1subscript𝑥𝑏1x_b=1italic_x start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT = 1. As a result, the discussion above shows that QA≤2/3𝑄𝐴23QA\leq 2/3italic_Q italic_A ≤ 2 / 3, which means the choice of P𝑃Pitalic_P in Eq.(21) is optimal for M𝑀Mitalic_M in Eq.(20).

In this paper, we have shown that in certain fair equilibria of some natural games, the player with a quantum computer can be more powerful than the classical opponent, even if the equilibria have zero entanglement or discord. This indicates that at least in games, the standard understanding that nonzero discord is necessary to produce non-classical correlations needs to be adjusted. Our work provides new visions for further studies on quantum information, especially when at least two parties are involved with different objectives.

From the mathematical perspective, some questions remain open. Two of them are listed as below: (1) What is the maximum gain in a zero-sum [-1,1]11[-1,1][ - 1 , 1 ]-normalized game222A game is [-1,1]11[-1,1][ - 1 , 1 ]-normalized if all utility functions have ranges within [-1,1]11[-1,1][ - 1 , 1 ]. on a state in symmetric subspace without entanglement? (2) What is the maximum gain in a zero-sum [-1,1]11[-1,1][ - 1 , 1 ]-normalized game on a state in symmetric subspace without discord?

Z.W. thanks Leong Chuan Kwek and Luming Duan for helpful comments. Z.W. was supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13 and the WBS grant under contract no. R-710-000-007-271. S.Z. was supported by Research Grants Council of the Hong Kong S.A.R. (Project no. CUHK419011, CUHK419413), and this research benefited from a visit to Tsinghua University partially supported by China Basic Research Grant 2011CBA00300 (sub-project 2011CBA00301).

Website: https://actorhockey8.werite.net/post/2022/06/28/In-This-Article

### Forums

Topics Started: 0

Replies Created: 0

Forum Role: Participant