Quantum refereed game


Quantum refereed game in quantum information processing is a class of games in the general theory of quantum games. It is played between two players, Alice and Bob, and arbitrated by a referee. The referee outputs the pay-off for the players after interacting with them for a fixed number of rounds, while exchanging quantum information.

Definition

An -turn quantum referee performs rounds of interaction with the player Alice and Bob. Each interaction involves receiving some quantum states from Alice and Bob, processing the quantum states together with the "left-over" state from the previous interaction, producing some output state, and sending part of the output state to the players. At the end of the rounds, the referee processes the final state received from the players and decides the pay-off for Alice and Bob.
Mathematically, an n-turn referee is a measuring co-strategy whose input spaces and output spaces are of the form
for complex Euclidean spaces and.
represent the message sent by the referee to Alice and Bob during turn, and correspond to their responses. At the end of turns, the referee produces an output
An -turn quantum refereed game consists of an n-turn referee along with functions that maps each measurement output to Alice's and Bob's pay-off.
Individual quantum refereed games may place specific restrictions on strategies Alice and Bob can choose from. For example, in nonlocal games and pseudo-telepathy games, Alice and Bob are allowed to share entanglement but are forbidden from communicating. In general, such restrictions may not apply in quantum refereed games.

Zero-sum quantum refereed game

Similar to a classical zero-sum game, a zero-sum quantum refereed game is a quantum refereed game with the additional constraint.
It is natural to assume Alice and Bob play independent strategies in a zero-sum quantum refereed game, since it cannot simultaneously be to both players' advantage to communicate directly with one another or to initially share an entanglement state. In this case, Alice's and Bob's strategy can be represented by
where is the set of all n-turn strategies having input space and output space.
The combined strategy is then.

Min-max theorem

Define, and, then Alice's expected pay-off is
The optimal strategy for Alice then lies in the min-max problem
The above equality holds because are drawn from compact and convex sets and. It is called the min-max theorem for zero-sum quantum games.

Quantum Interactive Proof with Competing Provers

A quantum interactive proof with two competing provers is a generalization of the single prover quantum interactive proof system. It can be modelled by zero-sum refereed games where Alice and Bob are the competing provers, and the referee is the verifier. The referee is assumed to be computationally bounded, whereas Alice and Bob can be computationally unrestricted. Alice, Bob and the referee receive a common string, and after fixed rounds of interactions, the referee decides whether Alice wins or Bob wins.

Classical RG

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. 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.
In the language of complexity theory, a promise problem has a classical refereed game if there exists a referee described by polynomial time randomized computation, such that
It is known that RG = EXP.

QRG

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. Therefore, QRG can be seen as the following problem. Alice, Bob and the referee is given some statement. 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 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.
More formally, QRG denotes the complexity class for all promise problems having quantum refereed games defined as follows. Given a string, a promise problem is in QRG if there is a referee represented by a polynomial time generated quantum circuit such that
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.

Semidefinite Program Formulation

For a quantum refereed game, at the end of all the interactions, the referee outputs one of the two possible outcomes to indicate whether Alice wins or Bob wins.
Setting 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, Alice may pick a strategy from, and Bob from. Define
where is the partial trace operator.
The referee outputs with probability, and with probability. can be considered as a co-strategy that merges Alice's strategy with the referee's.
For any given strategy Alice chooses, the maximum winning probability for Bob is
which, by the property of the strategy representation, is equal to
Therefore, to maximize Alice's winning probability, , the maximum winning probability for Bob, needs to be minimized over all possible strategies. The goal is then to compute
This minimization problem can be expressed by the following SDP problem:
The dimension of the input and output space of this SPD is exponential in, 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, it follows that QRG ⊆ EXP.