Quantum refereed game
Quantum refereed game
- Quantum refereed game** in quantum information processing is a class of [[game-theory|games]] in the [[quantum-game-theory|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 <math>n</math>-turn quantum referee performs <math>n</math> 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 <math>n</math> 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. When Alice and Bob return the qubits to the referee, the referee then checks their final states.
Mathematically, an n-turn referee is a measuring co-strategy <math>\{R_a:a\in\Sigma\}</math> whose input spaces <math>\mathcal X_1,\cdots, \mathcal X_n</math> and output spaces <math>\mathcal Y_1,\cdots, \mathcal Y_n</math> are of the form
:<math>\mathcal X_k = \mathcal A_k\otimes \mathcal B_k</math> and <math> \mathcal Y_k = \mathcal C_k\otimes\mathcal D_k</math>
for complex Euclidean spaces <math>\mathcal A_k,\mathcal B_k,\mathcal C_k</math> and <math>\mathcal D_k,\ 1\leq k\leq n</math>.
<math>\mathcal A_k,\mathcal B_k</math> represent the message sent by the referee to Alice and Bob during turn <math>k</math>, and <math>\mathcal C_k,\mathcal D_k</math> correspond to their responses. At the end of <math>n</math> turns, the referee produces an output <math>a\in\Sigma</math>
An <math>n</math>-turn quantum refereed game consists of an n-turn referee along with functions <math> V_A, V_B:\Sigma\mapsto\mathbb R</math> that maps each measurement output <math> a</math> 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.
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.