Hello, Habr!

I decided to continue a series of articles on non-standard applications of quantum computing. Under the cut, we will talk about a game for two players, which is best played in after studying the principles of quantum mechanics.

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

Before reading

For a complete understanding of the material, knowledge of the basic terms of quantum informatics is required: qubits, measurement of qubits 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 bottom line is pretty simple. Our two standard players (Alice and Bob) play by the following rules:

1. A judge generates two random bits $$ and $$(let's call them input bits). Then sends a bit$$ Alice, a bit $$ - Bob.
2. Alice and Bob, looking at the received bits (each player sees only his own bit), answers the judge again with one bit. We introduce the following notation:$$ - Alice's output bit, $$ - 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:$$where $$ - logical "And", and $$- 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 provides 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 benefits it can bring. Everything is simple here: since the function$$ is zero in 75 percent of cases, then sending bits to the judge is the most profitable strategy. $$, $$. Thus, the probability of winning is

$$

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. This connection Gilles Brassard in one of his works [2] called pseudo telepathy and suggested taking it into account using entangled quantum states shared between players.

So let's do it: take a two-qubit entangled state$$. We will give the first qubit from this pair to Alice, and the second - to Bob. Next, we will figure out how to use it.

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

$$

Where $$- an arbitrary angle. It is easy to verify that this basis is orthonormal. Let Alice use the angle to measure$$if received input bit $$and angle $$if the input bit $$. Similarly, Bob uses angles$$ and $$if received input bit $$ and $$respectively. The measurement determines the output bit of each player. If during measurement he received a condition$$, then he sends the judge zero, and if he received $$then sends the unit. That is, quantum mechanics will determine the strategy of the game!

We now go through all sorts of combinations of input bits:

1. $$, $$
   Alice and Bob win if they answer $$, $$ or $$, $$. The probability of winning in this case will be
   

   $$

   By simple, but rather tedious calculations, we obtain
   

   $$

2. $$, $$
   Alice and Bob win if they answer $$, $$ or $$, $$. Probability of this
   

   $$

3. $$, $$
   Alice and Bob will win if they answer again $$, $$ or $$, $$. Probability of this
   

   $$

4. $$, $$
   Alice and Bob win if they answer $$, $$ or $$, $$. Probability of this
   

   $$

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

$$

or

$$

Since we did not impose any restrictions on the angles of the measuring bases, we choose the following values: $$, $$, $$ and $$. Then we get a rather unexpected probability value

$$

Well, or the same result can be obtained by solving the problem of optimizing the function $$in any suitable way.

For example, listing a minimalistic Python program 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 execution:

Max value = 0.8535533904794891

That is, we got that $$. Therefore, using quantum strategy, Alice and Bob increase their chances of winning.

conclusions

Learn quanta and win!

Literature

[1] B.-H. Stib, 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.