Playing with a quantum coin
Hello, 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 a 1999 article by Gilles Brassard [1]. Quantum mechanics is an amazing thing in itself, and the possibility of using it in games is doubly surprising!
There are two players (let's call them Alice and Bob), a coin and a box. Before starting the game, put the 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 Alice again. Each of the players in his turn can turn the coin over, or leave it in the same state (I remind you that the players do not see which side the coin is facing up). If, at the end of the third move, the coin lies eagle up, then Alice wins, if by tails - Bob.
This game is very simple, so it’s easy to consider all the options for the development of events. Iterating through all the outcomes is convenient in the form of a table (a similar table in game theory is called the payoff matrix).
The letters “P” and “H” correspond to the player’s actions: flip a coin and do nothing. In each cell of the table the name of the winner is indicated. This immediately shows that the probability of winning Alice is. 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 gambler: she wants to win more than half the time! And quantum mechanics can help her with this!
For further reading, it is advisable to be familiar with the basics of quantum mechanics and cubitology. Comrade devpony published a post in which all this is explained at a qualitative level. You can also read the relevant literature [2].
Let’s imagine now that we have the same box, but inside it lies a “quantum coin”. This coin can be any two-level quantum system (qubit): an electron with spin up / down, a photon with polarization clockwise and counterclockwise, or a superconducting qubit whose state is determined by the direction of current flow. There are a lot of options. But we will work with an abstract qubit model, independent of physical implementation. And here the fact that the players do not see the coin plays an extremely important role. Monitoring the state of the coin corresponds to the measurement procedure, which kills all the salt - the ability of the coin to be in a state of superposition of the eagle and tails.
We introduce two states for the cases “coin with the eagle up” and “coin with the tails up”:
Now we need to determine the quantum operations corresponding to the classical actions of the players. Well, it’s all simple: flipping a coin corresponds to a quantum gate NOT
which translates state in and vice versa. And the action "do nothing" corresponds to the identical transformation
We assume that Alice carefully listened to the course of quantum mechanics at the institute and knows that in addition to these two transformations (similar to classical actions), any transformation described by a unitary matrix can be performed on a qubit. But Bob was a parasite, and believes that quantum mechanics is no different from classical mechanics, and only two of the above operations can be performed on it.
Alice selects the Hadamard valve. This valve is important in that it can be used to create a superposition of states
On our "monetary" state, it acts as follows:
The latter notation has been introduced for convenience of further use.
Bob, with some probability (unknown to Alice), performs one of the following actions: or . 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 in the form of a density matrix. This is a more general form of representation of quantum states, which has a very wide application (more details can be found here [4]). However, for now, the simplest definition is enough for us: if there is an initial state, then the corresponding density matrix will be specified as . This is a two-dimensional matrix 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 defined as follows
If the quantum transformation is represented by the Kraus operators, then the formula changes slightly
Where Are the Kraus operators satisfying the condition of expansion of unity
It is easy to see that unitary evolution is a special case of evolution in terms of the Kraus operators (when there is only one component in total).
Going back to Bob. He is likely flips a coin, and, accordingly, with probability does not change her condition. This action is described by two Kraus operators:
Taking the root is due to the need to satisfy the decomposition condition of the unit 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 in a state with probability 1. Using this method, Alice can win in all games (until she meets an opponent 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. Preskill “Quantum information and quantum computing”, 2008.
[3] H.-P. Breuer, F. Petruccione, “Theory of open quantum systems”, 2010.
[4] M. Nielsen, I. Chang. “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 a 1999 article by Gilles Brassard [1]. Quantum mechanics is an amazing thing in itself, and the possibility of using it in games is doubly surprising!
“If quantum mechanics did not shock you to the core, then you have not understood it yet.” (Niels Bohr)In this post we will talk about the most primitive game - tossing a coin. Although it will be more accurate to say turning coins over. 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 starting the game, put the 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 Alice again. Each of the players in his turn can turn the coin over, or leave it in the same state (I remind you that the players do not see which side the coin is facing up). If, at the end of the third move, the coin lies eagle up, then Alice wins, if by tails - Bob.
Classic version
This game is very simple, so it’s easy to consider all the options for the development of events. Iterating through all the outcomes is convenient in the form of a table (a similar table in game theory is called the payoff matrix).
The letters “P” and “H” correspond to the player’s actions: flip a coin and do nothing. In each cell of the table the name of the winner is indicated. This immediately shows that the probability of winning Alice is. 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 gambler: she wants to win more than half the time! And quantum mechanics can help her with this!
For further reading, it is advisable to be familiar with the basics of quantum mechanics and cubitology. Comrade devpony published a post in which all this is explained at a qualitative level. You can also read the relevant literature [2].
Quantum option
Let’s imagine now that we have the same box, but inside it lies a “quantum coin”. This coin can be any two-level quantum system (qubit): an electron with spin up / down, a photon with polarization clockwise and counterclockwise, or a superconducting qubit whose state is determined by the direction of current flow. There are a lot of options. But we will work with an abstract qubit model, independent of physical implementation. And here the fact that the players do not see the coin plays an extremely important role. Monitoring the state of the coin corresponds to the measurement procedure, which kills all the salt - the ability of the coin to be in a state of superposition of the eagle and tails.
We introduce two states for the cases “coin with the eagle up” and “coin with the tails up”:
Now we need to determine the quantum operations corresponding to the classical actions of the players. Well, it’s all simple: flipping a coin corresponds to a quantum gate NOT
which translates state in and vice versa. And the action "do nothing" corresponds to the identical transformation
We assume that Alice carefully listened to the course of quantum mechanics at the institute and knows that in addition to these two transformations (similar to classical actions), any transformation described by a unitary matrix can be performed on a qubit. But Bob was a parasite, and believes that quantum mechanics is no different from classical mechanics, and only two of the above operations can be performed on it.
Alice selects the Hadamard valve. This valve is important in that it can be used to create a superposition of states
On our "monetary" state, it acts as follows:
The latter notation has been introduced for convenience of further use.
Bob, with some probability (unknown to Alice), performs one of the following actions: or . 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 in the form of a density matrix. This is a more general form of representation of quantum states, which has a very wide application (more details can be found here [4]). However, for now, the simplest definition is enough for us: if there is an initial state, then the corresponding density matrix will be specified as . This is a two-dimensional matrix 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 defined as follows
If the quantum transformation is represented by the Kraus operators, then the formula changes slightly
Where Are the Kraus operators satisfying the condition of expansion of unity
Going back to Bob. He is likely flips a coin, and, accordingly, with probability does not change her condition. This action is described by two Kraus operators:
Taking the root is due to the need to satisfy the decomposition condition of the unit 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!
- Stroke 0 ) The coin is in the box in the state, the corresponding density matrix is .
- Move 1 ) Alice walks first: she applies the Admar transform
- Move 2 ) Now it’s Bob’s turn, he’s likely flips a coin We separately consider the action of the NOT gate on the superposition state: . 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.
- Move 3 ) Alice's winning move: using the Hadamard operator
At the end of all moves, the coin will be in a state with probability 1. Using this method, Alice can win in all games (until she meets an opponent 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. Preskill “Quantum information and quantum computing”, 2008.
[3] H.-P. Breuer, F. Petruccione, “Theory of open quantum systems”, 2010.
[4] M. Nielsen, I. Chang. “Quantum computing and quantum information”, 2006.
