Quantum refereed game

Define ${\displaystyle V(a)=V_{A}(a)=-V_{B}(a)}$, and ${\displaystyle R=\sum _{a\in \Sigma }V(a)R_{a}}$, then Alice's expected pay-off is ${\displaystyle \sum _{a\in \Sigma }V(a)\langle A\otimes B,R_{a}\rangle =\langle A\otimes B,R\rangle }$

The optimal strategy for Alice then lies in the min-max problem

${\displaystyle \max _{A}\min _{B}\langle A\otimes B,R\rangle =\min _{B}\max _{A}\langle A\otimes B,R\rangle }$.

The above equality holds because ${\displaystyle A,B}$ are drawn from compact and convex sets ${\displaystyle {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$ and ${\displaystyle {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$. It is called the min-max theorem for zero-sum quantum games.

In the classical setting, RG can be viewed as the following problem. Alice, Bob, and the referee is given some statement. Alice is trying to convince the referee that the statement is true while Bob is trying to convince the referee that the statement is false. The referee, who has limited computing power, will look at the proofs provided by Alice and Bob, ask them questions, and at the end of the day decide which player is correct (wins). The goal is for the referee to find an algorithm such that if the statement is true, there is a way for Alice to win with probability greater than 3/4, and if the statement is false, there is a way for Bob to win with probability greater than 3/4. This probability is equal to 1-ε.[5]

In the language of complexity theory, a promise problem ${\displaystyle L=(L_{\text{yes}},L_{\text{no}})}$ has a classical refereed game (classical RG) if there exists a referee described by polynomial time randomized computation, such that

1. for each ${\displaystyle x\in L_{\text{yes}}}$, there is a strategy for Alice to win with probability ≥ 3/4, and

2. for each ${\displaystyle x\in L_{\text{no}}}$, there is a strategy for Bob to win with probability ≥ 3/4.

It is known that RG = EXP.[10][11]

Quantum interactive proof systems with competing provers is a generalization of the classical RG where the referee is now restricted to polynomial-time generated quantum circuits and may exchange quantum information with the players.[1] Therefore, QRG can be seen as the following problem. Alice, Bob and the referee is given some statement (it may involve a quantum state). Alice is trying to convince the referee the statement is true while Bob is trying to convince the referee the statement is false. The referee can ask the provers questions via quantum states, receive answers in quantum states, and analyse the received quantum states using a quantum computer. After communicating with Alice and Bob for ${\displaystyle n}$ rounds, the referee decides whether the statement is true or false. If there is a way for the referee to make a correct decision with probability ≥ 3/4, the game is in QRG. This probability is ≥ 1-ε.[5]

More formally, QRG denotes the complexity class for all promise problems having quantum refereed games defined as follows. Given a string ${\displaystyle x}$, a promise problem ${\displaystyle L=(L_{\text{yes}},L_{\text{no}})}$ is in QRG if there is a referee represented by a polynomial time generated quantum circuit such that

1. if ${\displaystyle x\in L_{\text{yes}}}$, there exists a strategy for Alice to win with probability ≥ 3/4, and

2. if ${\displaystyle x\in L_{\text{no}}}$, there exists a strategy for Bob to win with probability ≥ 3/4.

It turns out that QRG = EXP — allowing the referee to use quantum circuit and send or receive quantum information does not give the referee any extra power. EXP ⊆ QRG follows from the fact that EXP = RG ⊆ QRG. proved QRG ⊆ EXP by a formulation of QRG using semidefinite programs (SDP).

For a quantum refereed game, at the end of all the interactions, the referee outputs one of the two possible outcomes ${\displaystyle \{a,b\}}$ to indicate whether Alice wins ${\displaystyle (a)}$ or Bob wins ${\displaystyle (b)}$.

Setting ${\displaystyle V(a)=1,V(b)=0}$ results in a quantum refereed game whose value is the maximum winning probability for Alice.

Using the same notation as the zero sum quantum refereed game as above, the referee is represented by operators ${\displaystyle \{R_{a},R_{b}\}}$, Alice may pick a strategy from ${\displaystyle A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$, and Bob from ${\displaystyle B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$. Define

${\displaystyle \Omega _{a}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{a})}$ , and

${\displaystyle \Omega _{b}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{b})}$,

where ${\displaystyle \operatorname {Tr} _{\mathcal {X}}(Z)}$ is the partial trace operator.

The referee outputs ${\displaystyle a}$ with probability ${\displaystyle \langle A\otimes B,R_{a}\rangle =\langle B,\Omega _{a}(A)\rangle }$, and ${\displaystyle b}$ with probability ${\displaystyle \langle A\otimes B,R_{b}\rangle =\langle B,\Omega _{b}(A)\rangle }$. ${\displaystyle \{\Omega _{a}(A),\Omega _{b}(A)\}}$ can be considered as a co-strategy that merges Alice's strategy with the referee's.

For any given strategy ${\displaystyle A}$ Alice chooses, the maximum winning probability for Bob is

${\displaystyle \max _{B}\langle B,\Omega _{b}(A)\rangle }$,

which, by the property of the strategy representation, is equal to

${\displaystyle \min\{p\geq 0:\Omega _{b}(A)\leq pQ,\ Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\}}$.

Therefore, to maximize Alice's winning probability, ${\displaystyle p}$, the maximum winning probability for Bob, needs to be minimized over all possible strategies. The goal is then to compute

${\displaystyle {\begin{array}{rl}\min &p\\{\text{subject to}}&\Omega _{b}(A)\leq pQ,\\&A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n}),\\&Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\end{array}}}$.

This minimization problem can be expressed by the following SDP problem:[1]

${\displaystyle {\begin{array}{rll}\min &\operatorname {Tr} (P_{1})\\{\text{subject to}}&\Omega _{b}(A_{n})\leq Q,\\&\operatorname {Tr} _{{\mathcal {C}}_{k}}(A_{k})=A_{k-1}\otimes I_{{\mathcal {A}}_{k}}&(2\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {C}}_{1}}(A_{1})=I_{{\mathcal {A}}_{1}},\\&Q_{k}=P_{k}\otimes I_{{\mathcal {D}}_{k}}&(1\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {B}}_{k}}(P_{k})=Q_{k-1}&(2\leq k\leq n),\\&A_{k}\in \operatorname {Pos} ({\mathcal {C}}_{1\cdots k}\otimes A_{1\cdots k})&(1\leq k\leq n),\\&Q_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\&P_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\\end{array}}}$.

The dimension of the input and output space of this SPD is exponential (from the tensor product states) in ${\displaystyle n}$, and the SDP has a size polynomial in the dimension of its input and output space. Since there are efficient algorithms that can solve SDP in polynomial-time,[12][13][14] it follows that QRG ⊆ EXP.