Playing with a quantum coin
Hi, Habr!
I decided to devote my first post to quantum computer science and its application to game theory. This idea is absolutely not new and has its roots in the 1999 article by Gilles Brassard [1]. Quantum mechanics is an amazing thing in itself, and the possibility of using it in games is surprisingly double!
')
There are two players (let's call them Alice and Bob), a coin and a box. Before the start of the game, put a coin in the box with the eagle up. Alice and Bob are blindfolded and the game begins: the first move is after Alice, the second is Bob, and the third move is again Alice. Each of the players in their turn can turn the coin, or leave it in the same condition (I remind you that players do not see which side the coin lies up). If at the end of the third move the coin lies with an eagle up, then Alice wins, if the tail is Bob.
This game is completely unpretentious, so it's easy to consider all variants of the development of events. It is convenient to sort through all the outcomes in the form of a table (such a table in game theory is called the payoff matrix).
The letters "P" and "H" correspond to the player's actions: turn the coin around and do nothing. Each cell in the table shows the name of the winner. This immediately shows that the probability of winning Alice is $ inline $ \ frac {1} {2} $ inline $ . Whatever strategies the players resort to, the probability of winning each of them remains constant. And everything would be fine, but Alice was a very gambling player: she wants to win more often than half the time! And quantum mechanics can help her with this!
For further reading, it is desirable to be familiar with the basics of quantum mechanics and cubitology. Comrade devpony published a post in which at a qualitative level all this is explained. You can also read the relevant literature [2].
Let us now imagine that we have the same box, but inside it there is a “quantum coin”. Any two-level quantum system (qubit) can act as this coin: an electron with a spin up / down, a photon with polarization clockwise and counterclockwise, or a superconducting qubit, the state of which is determined by the direction of current flow. There are a lot of options. But we will work with an abstract qubit model that is independent of the physical implementation. And here plays an extremely important role the fact that the players do not see the coin. Monitoring the state of the coin corresponds to the measurement procedure, which kills the whole salt - the possibility of the coin to be in a state of superposition of the eagle and tails.
We introduce two states for the cases of "coin eagle up" and "coin heads up":
Now we need to determine the quantum operations corresponding to the classic actions of the players. Well, everything is simple: a quantum gate NOT corresponds to a coin turning.
which translates the state $ inline $ | eagle \ rangle $ inline $ at $ inline $ | tails \ rangle $ inline $ and vice versa. And the action “do nothing” corresponds to the identity transformation
We assume that Alice listened attentively to the course of quantum mechanics at the institute and knows that in addition to these two transformations (similar to classical actions), any transformation can be performed on a qubit, which is described by the unitary matrix. And Bob was a parasite, and believes that quantum mechanics is no different from the classical, and only two of the above operations can be performed on it.
Alice chooses Hadamard valve. This valve is important because it can be used to create a superposition of states.
On our "monetary" state, it acts as follows:
The latest notation is introduced for easy reference.
With some probability (unknown to Alice), Bob performs one of the following actions: $ inline $ x $ inline $ or $ inline $ i $ inline $ . Unfortunately, such a transformation cannot be described by a unitary matrix. But the theory of open quantum systems tells us that such a transformation can be described using the so-called Kraus operators [3]. For further consideration, we will need to present our state as a density matrix. This is a more general form of representation of quantum states, which has a very wide application (you can read more here [4]). However, now the simplest definition is enough for us: if there is an initial state $ inline $ | \ psi \ rangle $ inline $ then the density matrix corresponding to it will be defined as $ inline $ \ rho = | \ psi \ rangle \ langle \ psi | $ inline $ . This is a matrix of dimension two with a unit trace and real non-negative eigenvalues ​​(you can try to prove these two facts). Unitary evolution in terms of density matrices is given as follows.
If the quantum transformation is represented by Kraus operators, then the formula changes slightly
Where $ inline $ E_k $ inline $ - Kraus operators satisfying the condition of unit decomposition
It is easy to see that unitary evolution is a special case of evolution in terms of Kraus operators (when there is only one component in the sum).
We return to Bob. He is with probability $ inline $ p $ inline $ flips a coin, and accordingly, with probability $ inline $ 1-p $ inline $ does not change its state. This action is described by two Kraus operators:
Taking the root due to the need to satisfy the condition of decomposition of the unit which was discussed above.
Now we have all the necessary tools for a detailed analysis of this game. Let's finally play along with Alice and Bob!
At the end of all moves, the coin will be able to $ inline $ | eagle \ rangle $ inline $ with probability 1. Using this method, Alice can win in all games (until she meets a rival who also knows quantum mechanics).
[1] G. Brassard, R. Cleve, A. Tapp "The cost of exactly simulating quantum entanglement with classical communication", 1999, arxiv.org/pdf/quant-ph/9901035.pdf .
[2] J. Presquill, Quantum Information and Quantum Computing, 2008.
[3] H.-P. Breuer, F. Petruccione “The Theory of Open Quantum Systems”, 2010.
[4] Nielsen M., Chang I., “Quantum Computing and Quantum Information,” 2006.
I decided to devote my first post to quantum computer science and its application to game theory. This idea is absolutely not new and has its roots in the 1999 article by Gilles Brassard [1]. Quantum mechanics is an amazing thing in itself, and the possibility of using it in games is surprisingly double!
“If quantum mechanics has not shook you to the depths of the soul, then you have not understood it yet.” (Niels Bohr)In this post we will discuss the most primitive game - tossing a coin. Although it would be more accurate to say turning the coin. The essence of the game is as follows:
')
Game Description
There are two players (let's call them Alice and Bob), a coin and a box. Before the start of the game, put a coin in the box with the eagle up. Alice and Bob are blindfolded and the game begins: the first move is after Alice, the second is Bob, and the third move is again Alice. Each of the players in their turn can turn the coin, or leave it in the same condition (I remind you that players do not see which side the coin lies up). If at the end of the third move the coin lies with an eagle up, then Alice wins, if the tail is Bob.
Classic option
This game is completely unpretentious, so it's easy to consider all variants of the development of events. It is convenient to sort through all the outcomes in the form of a table (such a table in game theory is called the payoff matrix).
The letters "P" and "H" correspond to the player's actions: turn the coin around and do nothing. Each cell in the table shows the name of the winner. This immediately shows that the probability of winning Alice is $ inline $ \ frac {1} {2} $ inline $ . Whatever strategies the players resort to, the probability of winning each of them remains constant. And everything would be fine, but Alice was a very gambling player: she wants to win more often than half the time! And quantum mechanics can help her with this!
For further reading, it is desirable to be familiar with the basics of quantum mechanics and cubitology. Comrade devpony published a post in which at a qualitative level all this is explained. You can also read the relevant literature [2].
Quantum variant
Let us now imagine that we have the same box, but inside it there is a “quantum coin”. Any two-level quantum system (qubit) can act as this coin: an electron with a spin up / down, a photon with polarization clockwise and counterclockwise, or a superconducting qubit, the state of which is determined by the direction of current flow. There are a lot of options. But we will work with an abstract qubit model that is independent of the physical implementation. And here plays an extremely important role the fact that the players do not see the coin. Monitoring the state of the coin corresponds to the measurement procedure, which kills the whole salt - the possibility of the coin to be in a state of superposition of the eagle and tails.
We introduce two states for the cases of "coin eagle up" and "coin heads up":
Now we need to determine the quantum operations corresponding to the classic actions of the players. Well, everything is simple: a quantum gate NOT corresponds to a coin turning.
which translates the state $ inline $ | eagle \ rangle $ inline $ at $ inline $ | tails \ rangle $ inline $ and vice versa. And the action “do nothing” corresponds to the identity transformation
We assume that Alice listened attentively to the course of quantum mechanics at the institute and knows that in addition to these two transformations (similar to classical actions), any transformation can be performed on a qubit, which is described by the unitary matrix. And Bob was a parasite, and believes that quantum mechanics is no different from the classical, and only two of the above operations can be performed on it.
Alice chooses Hadamard valve. This valve is important because it can be used to create a superposition of states.
On our "monetary" state, it acts as follows:
The latest notation is introduced for easy reference.
With some probability (unknown to Alice), Bob performs one of the following actions: $ inline $ x $ inline $ or $ inline $ i $ inline $ . Unfortunately, such a transformation cannot be described by a unitary matrix. But the theory of open quantum systems tells us that such a transformation can be described using the so-called Kraus operators [3]. For further consideration, we will need to present our state as a density matrix. This is a more general form of representation of quantum states, which has a very wide application (you can read more here [4]). However, now the simplest definition is enough for us: if there is an initial state $ inline $ | \ psi \ rangle $ inline $ then the density matrix corresponding to it will be defined as $ inline $ \ rho = | \ psi \ rangle \ langle \ psi | $ inline $ . This is a matrix of dimension two with a unit trace and real non-negative eigenvalues ​​(you can try to prove these two facts). Unitary evolution in terms of density matrices is given as follows.
If the quantum transformation is represented by Kraus operators, then the formula changes slightly
Where $ inline $ E_k $ inline $ - Kraus operators satisfying the condition of unit decomposition
We return to Bob. He is with probability $ inline $ p $ inline $ flips a coin, and accordingly, with probability $ inline $ 1-p $ inline $ does not change its state. This action is described by two Kraus operators:
Taking the root due to the need to satisfy the condition of decomposition of the unit which was discussed above.
Now we have all the necessary tools for a detailed analysis of this game. Let's finally play along with Alice and Bob!
- Move 0 ) The coin is in the box in the state $ inline $ | eagle \ rangle $ inline $ the corresponding density matrix is $ inline $ \ rho_0 = | eagle \ rangle \ langlerelated | $ inline $ .
- Turn 1 ) First walks Alice: she applies the Admar transformation
- Turn 2 ) Now it's Bob's turn, he is with probability $ inline $ p $ inline $ flips a coinConsider separately the effect of the gate NOT on the state of superposition: $ inline $ X | + \ rangle = \ frac {1} {\ sqrt {2}} (X | eagle \ rangle + X | tails \ rangle) = \ frac {1} {\ sqrt {2}} (| tails \ rangle + | eagle \ rangle) = | + \ rangle $ inline $ . It turns out that it does not change it, therefore:
we got a state the same as after Alice’s move, that is, Bob’s move doesn’t affect anything at all ! This fact allows Alice to win the game.
- Turn 3 ) Alice’s winning move: the use of the Hadamard operator
At the end of all moves, the coin will be able to $ inline $ | eagle \ rangle $ inline $ with probability 1. Using this method, Alice can win in all games (until she meets a rival who also knows quantum mechanics).
Literature
[1] G. Brassard, R. Cleve, A. Tapp "The cost of exactly simulating quantum entanglement with classical communication", 1999, arxiv.org/pdf/quant-ph/9901035.pdf .
[2] J. Presquill, Quantum Information and Quantum Computing, 2008.
[3] H.-P. Breuer, F. Petruccione “The Theory of Open Quantum Systems”, 2010.
[4] Nielsen M., Chang I., “Quantum Computing and Quantum Information,” 2006.
Source: https://habr.com/ru/post/338202/
All Articles