Quantum refereed game
The referee outputs the pay-off for the players after interacting with them for a fixed number of rounds, while exchanging quantum information.
rounds, the referee processes the final state received from the players and decides the pay-off for Alice and Bob.
The role of the referee is to pass along qubits to players Alice and Bob.
It is the referee's job to entangle the qubits, which is argued to be essential in quantum games.
represent the message sent by the referee to Alice and Bob during turn
Individual quantum refereed games may place specific restrictions on strategies Alice and Bob can choose from.
In general, such restrictions may not apply in quantum refereed games.
A language L is considered to have a refereed game with error ε if it has a polynomial time verifier satisfying these conditions: for each string x∈L Alice (the yes prover) can convince the referee to accept x with probability of at least 1-ε regardless of Bob's strategy (the no prover) and for each string x∉L Bob can convince the referee to reject x with a probability of at least 1-ε regardless of Alice's strategy.
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 {reference}.
The optimal strategy for Alice then lies in the min-max problem The above equality holds because
It is called the min-max theorem for zero-sum quantum games.
The game works by having each player send a density matrix to the referee who then plugs those states into his quantum circuit.
[6] A turn consists of the referee sending a message to the prover (Alice or Bob) and then Alice or Bob sending a response back to the referee.
[5] The order of the game goes as follows: Alice sends the referee her density matrix, then the referee processes Alice's state and sends a state to Bob, Bob then measures the state and sends a classical result back to the referee, the referee then checks Bob's measurement and either produces a "yes" meaning Alice wins or produces a "no" and Bob wins.
The referee gives Alice and Bob three conditions about what is behind each of the doors.
The aim of this game is for Alice and Bob to find a matching pair behind the doors.
In quantum terms, this means that Alice and Bob produce matching density states.
By strategizing, Alice and Bob's probability of producing matching quantum states increases from 2/3 to 3/4.
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.
Alice, Bob and the referee is given some statement (it may involve a quantum state).
If there is a way for the referee to make a correct decision with probability ≥ 3/4, the game is in QRG.
[5] More formally, QRG denotes the complexity class for all promise problems having quantum refereed games defined as follows.
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.
results in a quantum refereed game whose value is the maximum winning probability for Alice.
can be considered as a co-strategy that merges Alice's strategy with the referee's.
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 goal is then to compute This minimization problem can be expressed by the following SDP problem:[1] The dimension of the input and output space of this SPD is exponential (from the tensor product states) 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,[12][13][14] it follows that QRG ⊆ EXP.
