User:Applixy/sandbox

A multiple round interactive quantum games is a subset of games that falls under the general theory of quantum games.^[1]

Background

Game theory had been studied extensively by mathematicians using classical (non-quantum mechanical) models. Around the year 2000, many researchers^[2] ^[3] {references} explored ways to extend games well studied in classical game theory to allow the players to use quantum strategies, and showed that the quantum version would give significant advantages over the classical counterparts. Even though classical games can be considered as a special case of quantum games, some controversy were drawn ^[4]^[5] because the results of such games lack the generality ^[1] to be applied to any other areas of quantum information and computation. A more general theory of quantum game was proposed in 2007 by Gutoski^[1], where a quantum game can be a general set of rules that allows the players to choose their strategies with no restrictions beyond the ones imposed by the theory of quantum information.

Multiple round interaction competitive quantum games fall under the general theory of quantum games, and have applications a variety of fields such as quantum cryptography, computational complexity, communication complexity, and distributed computation. ^[1]

Definitions

The information used for quantum strategies are represented by vectors in complex Euclidean space, or finite dimensional inner product space over the complex numbers. A (finite) sequence of complex Euclidean spaces, ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}$ are represented by the tensor product notation ${\mathcal {X}}_{1}\otimes \cdots \otimes {\mathcal {X}}_{n}$ .

An operator between complex Euclidean spaces ${\mathcal {X}}$ and ${\mathcal {Y}}$ is a linear mapping denoted by $L({\mathcal {X}},{\mathcal {Y}})$ . $L({\mathcal {X}})$ is a short form for $L({\mathcal {X}},{\mathcal {X}})$ .

A super-operator is a linear mapping of the form $\Phi :L({\mathcal {X}})\rightarrow L({\mathcal {Y}})$ .

A $n$ -turn quantum interactive strategy is a combination of $n$ -turn strategy and co-strategy, which correspond to the strategies players Alice and Bob can choose from.

Let ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n},{\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n},{\mathcal {Z}}_{1},\cdots ,{\mathcal {Z}}_{n},{\mathcal {W}}_{1},\cdots ,{\mathcal {W}}_{n}$ be complex Euclidean spaces.

Quantum Strategy

n-turn strategy

An n-turn non-measuring strategy with the input spaces ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n},$ and output spaces ${\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}$ consist of

1. a memory space ${\mathcal {Z}}_{1},\cdots ,{\mathcal {Z}}_{n}$

2. an n-tuple of admissible mappings $(\Phi _{1},\cdots ,\Phi _{n})$ of the form

\Phi _{1}:L({\mathcal {X}}_{1})\rightarrow L({\mathcal {Y}}_{1}\otimes {\mathcal {Z}}_{1})

\Phi _{k}:L({\mathcal {X}}_{k}\otimes Z_{k-1})\rightarrow L({\mathcal {Y}}_{k}\otimes {\mathcal {Z}}_{k}),\ (2\leq k\leq n)

An $n$ -turn measuring strategy consists of 1 and 2 above and

3. a measurement $\{P_{a}:a\in \Sigma \}$

n-turn co-strategy

Similar to $n$ -turn strategy, an $n$ -turn co-strategy consists of input spaces ${\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}$ , output spaces ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n},$ , as well as the following:

1. a memory space ${\mathcal {W}}_{0},\cdots ,{\mathcal {W}}_{n}$

2. a density operator $\rho _{0}=D({\mathcal {X}}_{1}\otimes {\mathcal {W}}_{0})$

3. an n-tuple of admissible mappings $(\Psi _{1},\cdots ,\Psi _{n})$ of the form

\Psi _{k}:L({\mathcal {Y}}_{k}\otimes {\mathcal {W}}_{k-1})\rightarrow L({\mathcal {X}}_{k+1}\otimes {\mathcal {W}}_{k})

\Psi _{n}:L({\mathcal {Y}}_{n}\otimes {\mathcal {W}}_{n-1})\rightarrow L({\mathcal {W}}_{n})

An n-turn measuring co-strategy consists of 1, 2 and 3 above and

4. a measurement $\{Q_{b}:b\in \Gamma \}$

Example

2 Turn Interactive Quantum Game

Consider the interaction between a 2-turn measuring strategy and co-strategy. Assume Alice and Bob are players of a 2-turn interactive quantum game shown in the figure on the left.

Bob (with 2-turn co-strategy) starts with some state $\rho _{0}\in D({\mathcal {X}}_{1}\otimes {\mathcal {W}}_{0})$ , and sends part of the state in $L({\mathcal {X}}_{1})$ to Alice, while keeping $L({\mathcal {W}}_{1})$ .

Alice (with 2-turn strategy) applies operator $\Phi _{1}$ on $L({\mathcal {X}}_{1})$ he receives, which outputs some state in $L({\mathcal {Y}}_{1}\otimes Z_{1})$ . Alice sends $L({\mathcal {Y}}_{1})$ to Bob.

Bob applies $\Psi _{1}$ to the state $L({\mathcal {W}}_{1})$ he kept and $L({\mathcal {Y}}_{1})$ he received to get $L({\mathcal {X}}_{2}\otimes {\mathcal {W}}_{2})$ , and sends $L({\mathcal {X}}_{2})$ to Alice.

Alice applies $\Phi _{2}$ on state in $L({\mathcal {X}}_{2}\otimes {\mathcal {Z}}_{2})$ , and sends $L({\mathcal {Y}}_{2})$ to Bob. For a 2-turn measuring strategy, Alice measures her state in $L({\mathcal {Z}}_{2})$ with $\{P_{a}\}$ to get value $a$ .

Bob applies $\Psi _{2}$ on state in $L({\mathcal {Y}}_{2}\otimes {\mathcal {W}}_{2})$ to get a final state $L({\mathcal {W}}_{2})$ . For a 2-turn measuring co-strategy, Bob measures his state in $L({\mathcal {W}}_{2})$ with $\{Q_{b}\}$ to get $b$ .

$(a,b)$ are the outcome of the quantum strategies Bob and Alice chose, which can be used to determine the pay-off of the game. The probability of getting the outcome $(a,b)$ is

\langle P_{a}\otimes Q_{b},(I_{L_{{\mathcal {Z}}_{2}}}\otimes \Psi _{2})(\Phi _{2}\otimes I_{L_{{\mathcal {Z}}_{2}}})(I_{L_{{\mathcal {Z}}_{1}}}\otimes \Psi _{1})(\Phi _{1}\otimes I_{L_{{\mathcal {Z}}_{1}}})\rho _{0}\rangle

.

In general, for an n-turn quantum interactive strategy with measuring strategy and co-strategy, the probability of arriving at output $(a,b)\in \Sigma \times \Gamma$ is

\langle P_{a}\otimes Q_{b},(I_{L_{{\mathcal {Z}}_{n}}}\otimes \Psi _{n})(\Phi _{n}\otimes I_{L_{{\mathcal {Z}}_{n}}})\cdots (I_{L_{{\mathcal {Z}}_{1}}}\otimes \Psi _{1})(\Phi _{1}\otimes I_{L_{{\mathcal {Z}}_{1}}})\rho _{0}\rangle

Representation of Strategy

Although $n$ -turn strategy and co-strategy can be described by a sequence of super-operators, this representation can be inconvenient in some situations.^[1] It is possible to describe a sequence of super-operators $(\Phi _{1},\cdots ,\Phi _{n})$ for a strategy using a single super-operator

\Xi :L({\mathcal {X}}_{1\cdots n})\rightarrow L({\mathcal {Y}}_{1\cdots n})

.

Quantum Strategy Representation

The super operator $\Xi$ takes input state $\xi$ from spaces ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}$ one piece at a time, applying the corresponding $\Phi _{k}$ super operator, and trace out space ${\mathcal {Z}}_{n}$ at the end to give $\Xi (\xi )\in D({\mathcal {Y}}_{1\cdots n})$ . The Choi-Jamiolkowski representation of the strategy $(\Phi _{1},\cdots ,\Phi _{n})$ is defined as the Choi-Jamiolkowski representation $J(\Xi )$ of the super-operator $\Xi$ , where

J(\Phi )=\sum _{i\leq i,j\leq N}\Phi (|i\rangle \langle j|)\otimes |i\rangle \langle j|\in L({\mathcal {Y}}\otimes {\mathcal {X}})

.

Although $n$ -turn strategy and co-strategy can be described by a sequence of super-operators, this representation can be inconvenient in some situations.^[1] It is possible to describe a sequence of super-operators $(\Phi _{1},\cdots ,\Phi _{n})$ for a strategy using a single super-operator

A measuring strategy with measurement $\{P_{a}:a\in \Sigma \}$ can be described by the collection of super-operators $\{\Xi _{a}:a\in \Sigma \}$ . Each of them has the form $\Xi _{a}:L({\mathcal {X}}_{1\cdots n})\rightarrow L({\mathcal {Y}}_{1\cdots n})$ , and are defined almost exactly the same way as $\Xi$ , except the partial trace on ${\mathcal {Z}}_{n}$ is replaced by the mapping

X\mapsto \operatorname {Tr} _{{\mathcal {Z}}_{n}}((P_{a}\otimes I_{{\mathcal {Y}}_{1\cdots n}})X)

.

A measurement must satisfy $\sum _{a}P_{a}=I$ so $\sum _{a}\Xi _{a}=\Xi$ .

Linear isometry representation

An alternative way of expressing the Choi-Jamiolkowski representation of a strategy is based on its linear isometry descriptions $(A_{1},\cdots ,A_{n})$ . Define $A\in L({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots ,n}\otimes {\mathcal {Z}}_{n})$ to be

A=(I_{{\mathcal {Y}}_{1\cdots n-1}}\otimes A_{n})((I_{{\mathcal {Y}}_{1\cdots n-2}}\otimes A_{n-1}\otimes I_{{\mathcal {X}}_{n}})\cdots (A_{1}\otimes I_{{\mathcal {X}}_{1\cdots n-1}})

.

Then the Choi-Jamiolkowski representation is $Q=\operatorname {Tr} _{{\mathcal {Z}}_{n}}(\operatorname {vec} (A)\operatorname {vec} (A)^{*})$ where $\operatorname {vec}$ is the vectorization operation.

The representation for a measuring strategy measurement $\{P_{a}:a\in \Sigma \}$ is then $\{Q_{a}:a\in \Sigma \}$ defined by

Q_{a}=\operatorname {Tr} _{{\mathcal {Z}}_{n}}(\operatorname {vec} (B_{a})\operatorname {vec} (B_{a})^{*})

where

B_{a}=({\sqrt {P_{a}}}\otimes I_{{\mathcal {Y}}_{1\cdots n}})A

.

The Choi-Jamiolkowski representation of measuring and non-measuring co-strategies are defined similarly, with the resulting operators transposed due to technical reasons.

Properties

Representing n-turn strategy and co-strategy in Choi-Jamilkowski representation lead to the discovery of the following three properties of the representations. ^[1]

Define ${\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})$ to be the set of all representation of n-turn strategies, and ${\text{co-}}{\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})$ to be the set of all representation of n-turn co-strategies.

Interaction output probabilities

The probability of getting output $(a,b)$ at the end of an n-turn interaction with a measuring strategy $\{Q_{b}:b\in \Gamma \}$ and a measuring co-strategy $\{R_{a}:a\in \Sigma \}$ is

\langle Q_{a},R_{b}\rangle

where $\langle A,B\rangle ={\text{Tr}}(A^{*}B)$ is the Hilbert-Schmidt inner product.

Characterization of strategy representations

Let $\operatorname {Pos} ({\mathcal {X}})$ denote the set of all positive-semidefinite operators acting on space ${\mathcal {X}}$ . Given $Q\in \operatorname {Pos} ({\mathcal {Y}}_{1\cdots n}\otimes {\mathcal {X}}_{1\cdots n})$ , $Q\in {\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})$ , i.e. $Q$ is a representation for a strategy if and only if

\operatorname {Tr} _{{\mathcal {Y}}_{n}}(Q)=R\otimes I_{{\mathcal {X}}_{n}}

for $R\in {\mathcal {S}}_{n-1}({\mathcal {X}}_{1\cdots n-1},{\mathcal {Y}}_{1\cdots n-1})$

Maximum Output Probabilities

Given an n-turn measuring strategy $\{Q_{a}:a\in \Sigma \}$ , the maximum probability for this strategy to be forced to output $a$ across all compatible co-strategies is

\min\{p\in [0,1]:Q_{a}\leq pR{\text{ for some }}R\in {\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})\}

Applications

Strong coin flipping

Quantum refereed game

References

^ ^a ^b ^c ^d ^e ^f ^g Gutoski, G (2007). "Toward a general theory of quantum games". Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing: 565–574. arXiv:quant-ph/0611234. doi:10.1145/1250790.1250873. ISBN 9781595936318. S2CID 2329605. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Eisert, J (1999). "Quantum games and quantum strategies". Physical Review Letters. 83 (15): 3077–3080. arXiv:quant-ph/9806088. doi:10.1103/PhysRevLett.83.3077. S2CID 30550760. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Myer, D (1999). "Quantum Strategies". Physical Review Letters. 82 (5): 1502–1555. arXiv:quant-ph/9804010. doi:10.1103/PhysRevLett.82.1052. S2CID 7361611.
^ Enk, S.V. (2002). "Classical rules in quantum games". Physical Review A. 66 (2): 024306. arXiv:quant-ph/0203133. doi:10.1103/PhysRevA.66.024306. S2CID 119509677. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Benjamin, S (2001). "Comment on "Quantum games and quantum strategeis"". Physical Review Letters. 87 (6): 069801. arXiv:quant-ph/0003036. doi:10.1103/PhysRevLett.87.069801. S2CID 17148657. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[general_qg-1] ^ ^a ^b ^c ^d ^e ^f ^g Gutoski, G (2007). "Toward a general theory of quantum games". Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing: 565–574. arXiv:quant-ph/0611234. doi:10.1145/1250790.1250873. ISBN 9781595936318. S2CID 2329605. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[2] Eisert, J (1999). "Quantum games and quantum strategies". Physical Review Letters. 83 (15): 3077–3080. arXiv:quant-ph/9806088. doi:10.1103/PhysRevLett.83.3077. S2CID 30550760. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[3] Myer, D (1999). "Quantum Strategies". Physical Review Letters. 82 (5): 1502–1555. arXiv:quant-ph/9804010. doi:10.1103/PhysRevLett.82.1052. S2CID 7361611.

[4] Enk, S.V. (2002). "Classical rules in quantum games". Physical Review A. 66 (2): 024306. arXiv:quant-ph/0203133. doi:10.1103/PhysRevA.66.024306. S2CID 119509677. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[5] Benjamin, S (2001). "Comment on "Quantum games and quantum strategeis"". Physical Review Letters. 87 (6): 069801. arXiv:quant-ph/0003036. doi:10.1103/PhysRevLett.87.069801. S2CID 17148657. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[1]

[2]

[3]

[4]

[5]