Hi, Habr!

I decided to continue the series of articles on non-standard applications of quantum computing. Under the cut, we’ll talk about the two-player game, which is best played after first studying the principles of quantum mechanics.

“There is nothing special in the world. No magic Only physics. "(Chuck Palahniuk)

Before reading

A complete understanding of the material requires knowledge of the basic terms of quantum informatics: qubits, qubit measurement and entanglement. You can read about all this in [1], a brief theory is described there and a set of tasks for each topic is given.
')

Game Description

John Clauser, Michael Horne, Abner Shimony and Richard Holt developed an alternative approach to Bell's inequalities and presented it as a simple game, calling it CHSH Game. The essence is pretty simple. Our two standard players (Alice and Bob) play according to the following rules:

1. Some judge generates two random bits. $$$x$ and $$$y$ (let's call them input bits). Then sends a bit $$$x$ Alice and bit $$$y$ - Bob.
2. Alice and Bob, looking at the received bits (each of the players sees only his own bit), answers the judge again with one bit. We introduce the notation: $$$a$ - Alice's output bit, $$$b$ - Bob's output bit.
3. The judge based on the bits of Alice and Bob makes a verdict - the victory of the players or their defeat. The victory condition is as follows: $$$x \ cdot y = a \ oplus b$ where $$$x \ cdot y$ - logical "And", and $$$a \ oplus b$ - operation "XOR".
   Ps. We consider the judge to be 100% honest.

As can be seen from the conditions, the game is cooperative. The goal of Alice and Bob is to develop a strategy that ensures the maximum probability of winning. However, they can discuss plans only before the game, communication is prohibited during the game.

Classic strategy

First, consider the classic strategy of the game, and what kind of benefits it can bring. Everything is simple: since the function $$$x \ cdot y$ equal to zero in 75 percent of cases, the most profitable strategy will be to send the judge bits $$$a = 0$ , $$$b = 0$ . Thus, the probability of winning is

$$

$$P_ {Classic} = \ frac {3} {4}$$

Quantum strategy

The possibility of applying a quantum strategy is explained by the presence of a certain connection between the players at the level of quantum-mechanical phenomena. In one of his works [2], Gilles Brassard called this connection pseudo telepathy and suggested taking it into account with the help of entangled quantum states divided between players.

So do: take a two-qubit entangled state $$$| \ psi_ {AB} \ rangle = \ frac {1} {\ sqrt {2}} (| 00 \ rangle + | 11 \ rangle)$ . The first qubit from this pair is given to Alice, and the second to Bob. Next, we will understand how to use it.

After receiving the input bits, Alice and Bob choose a basis in which they measure their halves of the entangled state. We denote this basis as

$$

$$| \ nu_0 (\ theta) \ rangle = \ cos \ theta | 0 \ rangle + \ sin \ theta | 1 \ rangle \\ | \ nu_1 (\ theta) \ rangle = \ sin \ theta | 0 \ rangle- \ cos \ theta | 1 \ rangle$$

Where $$$\ theta$ - arbitrary angle. It is easy to verify that this basis is orthonormal. Let Alice use angle to measure. $$$\ alpha_0$ if received input bit $$$x = 0$ and angle $$$\ alpha_1$ if the input bit $$$x = 1$ . Similarly, bob uses angles $$$\ beta_0$ and $$$\ beta_1$ if received input bit $$$y = 0$ and $$$y = 1$ respectively. The measurement determines the output bit of each player. If the measurement he received the state $$$| \ nu_0 (\ theta) \ rangle$ then he sends the judge a zero, and if received $$$| \ nu_1 (\ theta) \ rangle$ , then sends the unit. That is, quantum mechanics will determine the strategy of the game!

Now let's sort through all possible combinations of input bits:

1. $$$x = 0$ , $$$y = 0$
   Alice and Bob win if they answer $$$a = 0$ , $$$b = 0$ or $$$a = 1$ , $$$b = 1$ . The probability of winning in this case will be
   

   $$

   $$P (x = 0, y = 0) = | \ langle \ nu_0 (\ alpha_0), \ nu_0 (\ beta_0) | \ psi_ {AB} \ rangle | ^ 2 + | \ langle \ nu_1 (\ alpha_0), \ nu_1 (\ beta_0) | \ psi_ {AB} \ rangle | ^ 2$$
   By simple, but rather tedious, calculations we get
   

   $$

   $$P (x = 0, y = 0) = \ cos ^ 2 (\ alpha_0- \ beta_0)$$
2. $$$x = 0$ , $$$y = 1$
   Alice and Bob win if they answer $$$a = 0$ , $$$b = 0$ or $$$a = 1$ , $$$b = 1$ . Probability of this
   

   $$

   $$P (x = 0, y = 1) = | \ langle \ nu_0 (\ alpha_0), \ nu_0 (\ beta_1) | \ psi_ {AB} \ rangle | ^ 2 + | \ langle \ nu_1 (\ alpha_0), \ nu_1 (\ beta_1) | \ psi_ {AB} \ rangle | ^ 2 = \ cos ^ 2 (\ alpha_0- \ beta_1)$$
3. $$$x = 1$ , $$$y = 0$
   Alice and Bob win if they answer again. $$$a = 0$ , $$$b = 0$ or $$$a = 1$ , $$$b = 1$ . Probability of this
   

   $$

   $$P (x = 1, y = 0) = | \ langle \ nu_0 (\ alpha_1), \ nu_0 (\ beta_0) | \ psi_ {AB} \ rangle | ^ 2 + | \ langle \ nu_1 (\ alpha_1), \ nu_1 (\ beta_0) | \ psi_ {AB} \ rangle | ^ 2 = \ cos ^ 2 (\ alpha_1- \ beta_0)$$
4. $$$x = 1$ , $$$y = 1$
   Alice and Bob win if they answer $$$a = 0$ , $$$b = 1$ or $$$a = 1$ , $$$b = 0$ . Probability of this
   

   $$

   $$P (x = 1, y = 1) = | \ langle \ nu_0 (\ alpha_1), \ nu_1 (\ beta_1) | \ psi_ {AB} \ rangle | ^ 2 + | \ langle \ nu_1 (\ alpha_1), \ nu_0 (\ beta_1) | \ psi_ {AB} \ rangle | ^ 2 = \ sin ^ 2 (\ alpha_1- \ beta_1)$$

Since the values ​​of the input bits are equally likely, the overall probability that determines success when using a quantum strategy is given by the formula

$$

$$P_ {Quantum} = \ frac {1} {4} [P (x = 0, y = 0) + P (x = 0, y = 1) + P (x = 1, y = 0) + P ( x = 1, y = 1)]$$

or

$$

$$P_ {Quantum} = \ frac {1} {4} [\ cos ^ 2 (\ alpha_0- \ beta_0) + \ cos ^ 2 (\ alpha_0- \ beta_1) + \ cos ^ 2 (\ alpha_1- \ beta_0) + \ sin ^ 2 (\ alpha_1- \ beta_1)]$$

Since we did not impose any restrictions on the angles of the measurement bases, we choose the following values: $$$\ alpha_0 = 0$ , $$$\ alpha_1 = \ frac {\ pi} {4}$ , $$$\ beta_0 = \ frac {\ pi} {8}$ and $$$\ beta_1 = - \ frac {\ pi} {8}$ . Then we get a rather unexpected probability value.

$$

$$P_ {Quantum} = \ frac {1} {2} + \ frac {1} {2 \ sqrt {2}} \ approx0.854$$

Well, or the same result can be obtained by solving the function optimization problem. $$$P_ {Quantum}$ in any suitable way.

For example, the listing of the minimalist Python applet that solves this problem:

from scipy.optimize import minimize from math import sin, cos, pi f = lambda x: -(cos(x[0] - x[2])**2 + cos(x[0] - x[3])**2 + cos(x[1] - x[2])**2 + sin(x[1] - x[3])**2) / 4 res = minimize(f, [pi] * 4, method='Nelder-Mead') print("Max value =", abs(f(res.x))) 

And the result of the implementation:

 Max value = 0.8535533904794891 

So we got that $$$P_ {Quantum}> P_ {Classic}$ . Therefore, using a quantum strategy, Alice and Bob increase their chances of winning.

findings

Learn quanta and win!

Literature

[1] V.-H. Stieb, J. Hardy Problems and their solutions in quantum computing and quantum information theory, Ed. Regular and chaotic dynamics, 2007.
[2] Gilles Brassard, Anne Broadbent, Alain Tapp, Quantum Pseudo-telepathy, Foundations of Physics, Vol. 35, Issue 11, 2005.