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 n {\displaystyle n} -turn quantum referee performs n {\displaystyle n} 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 n {\displaystyle n} 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 { R a : a ∈ Σ } {\displaystyle \{R_{a}:a\in \Sigma \}} whose input spaces X 1 , ⋯ , X n {\displaystyle {\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}} and output spaces Y 1 , ⋯ , Y n {\displaystyle {\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}} are of the form
X k = A k ⊗ B k {\displaystyle {\mathcal {X}}_{k}={\mathcal {A}}_{k}\otimes {\mathcal {B}}_{k}} and Y k = C k ⊗ D k {\displaystyle {\mathcal {Y}}_{k}={\mathcal {C}}_{k}\otimes {\mathcal {D}}_{k}}
for complex Euclidean spaces A k , B k , C k {\displaystyle {\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}} and D k , 1 ≤ k ≤ n {\displaystyle {\mathcal {D}}_{k},\ 1\leq k\leq n} .
A k , B k {\displaystyle {\mathcal {A}}_{k},{\mathcal {B}}_{k}} represent the message sent by the referee to Alice and Bob during turn k {\displaystyle k} , and C k , D k {\displaystyle {\mathcal {C}}_{k},{\mathcal {D}}_{k}} correspond to their responses. At the end of n {\displaystyle n} turns, the referee produces an output a ∈ Σ {\displaystyle a\in \Sigma }
An n {\displaystyle n} -turn quantum refereed game consists of an n-turn referee along with functions V A , V B : Σ ↦ R {\displaystyle V_{A},V_{B}:\Sigma \mapsto \mathbb {R} } that maps each measurement output a {\displaystyle a} 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.
… excerpt ends here. Continue reading the full article.
