In quantum games, you can’t count on luck

In these games, quantum entanglement, infinity and the impossibility of calculating the probability of winning are combined. But if researchers can figure them out, they will reveal to us the deep secrets of mathematics.

In the 1950s, four US Army math enthusiasts used primitive electronic calculators to calculate the optimal blackjack strategy. Their results were later published in the Journal of the American Statistical Association, and described the best decisions that a player can make in any situation in the game.

However, such a strategy, which gambling fans later dubbed the “rules” [of the book], does not guarantee victory to the player. Blackjack, as well as solitaire, checkers or many other games, have a certain "ceiling" in the percentage of games that a player can win - even if he plays perfectly every time.

However, there are especially strange games in which, in principle, it is impossible to calculate the maximum probability of winning. Instead, mathematicians and computer scientists are trying to determine whether it is possible at least to give an approximate estimate of the percentage of winnings for such games. And the existence of this possibility depends on the compatibility of two very different approaches to physics.
')
Such "non-local" games were first thought up in 1960 by the physicist John Stuart Bell , trying to understand such a strange quantum phenomenon as quantum entanglement . Although entanglement is complex, non-local games are inherently simple. There are two players, each of whom is asked a simple question. They win if their answers are in some way related. Unfortunately, they cannot communicate with each other, so they have to guess the answer of the other. Bell proved that if players can use pairs of entangled quantum particles, they can improve the correlation of answers and win games more often than one would expect.

In recent years, researchers have developed the work of Bell, as we have already written in the article " Simple quantum games reveal the primary complexity of the universe ." The work of William Slofstra from 2016 and Andrea Koladangelo and Yaleksa Stark from 2018 proved that in some non-local games the pattern is observed - the more pairs of entangled particles the players have, the better they play. And this relationship is preserved in infinity, that is, for the best possible game, players will need an infinite number of pairs of particles (or particles with an infinite number of independent properties).

One of the consequences of these results is that it is impossible to calculate the probability of the maximum winning percentage for some non-local games. Computers do not work with infinite quantities, so if an ideal strategy requires an infinite number of entangled particles, the computer cannot calculate how often the strategy justifies itself.

“There is no such generalized algorithm so that you can enter a description of the game and get an answer in the form of the probability of the maximum percentage of winnings,” said Henry Yuy , a specialist in theoretical computer science from the University of Toronto.

But if we do not know the exact probability of the maximum percentage of winnings, can we not calculate it with at least some error?

Mathematicians are actively working on this issue. Oddly enough, their success depends on the compatibility of two very different approaches to physics.

Recall that players in a non-local game cannot coordinate answers. This can be achieved in two ways. The first is to physically isolate them from each other by placing them in different rooms or at different ends of the universe. Spatial isolation provides a lack of communication. Researchers analyze this situation using the tensor product model.

However, there is another way to prevent players from agreeing. Instead of separating them, you can put forward another requirement: a sequence in which two players measure entangled particles and give an answer cannot influence their answers. “If the order in which they measure is irrelevant, then they obviously cannot communicate with each other,” said Yuyen.

When the procedure in mathematics does not affect the answer, the operation is said to be commutative: a × b = b × a. Such an approach to non-local games — based on sequence independence, rather than spatial separation — is called the “switching operator” model.

The product of tensors and the commuting operator are used in physics, especially when studying the interactions of subatomic particles in quantum field theory. These models are two different approaches to reasoning about the causal independence of physical phenomena. Although the model of the product of tensors is more intuitive - we usually see causal independence as a spatial separation - the model of the switching operator gives a more logical mathematical platform. This is because “spatial independence” is a vague idea, and the commuting relationship can be described clearly.

“For people studying quantum field theory, the concept of spatial separation of objects is unnatural,” said Yuyen. “At the mathematical level, it is not always possible to place two independent things in two separate places of the Universe.”

And this is how all this is connected with non-local games.

Computer scientists can use the tensor product model to calculate the minimum probability of the maximum percentage of winnings. The algorithm they use ensures that this probability is higher than a certain threshold. Similarly, researchers can use the model of the switching operator to limit the probability from above. This algorithm ensures that the probability does not exceed a certain threshold.

With such tools, researchers want to bring these restrictions together as closely as possible, like two pistons. They know that it is impossible to make these limits touch and give the only and exact probability value of the maximum percentage of winnings - in the recent work by Slofstra, Koladangelo and Stark proved that the exact probability cannot be calculated - but the closer they bring them down, the more accurately they will be able to determine this probability.

Indeed, the longer these algorithms work, the more closely two pistons come together, giving an ever more accurate approximation to an inexpressible average value, which they will never achieve. However, it is unclear whether this apparent convergence will last forever. “These algorithms are completely mysterious. This is not a gradual and smooth improvement of values. We just don’t understand how quickly they come closer, ”said Yuyen.

The piston strategy is based on the equivalence of the two models. It assumes that the upper and lower constraints extrude the mean value. If these two models and the truth are equivalent, then the two pistons will really converge at an arbitrarily small distance. Conversely, if you prove that the two pistons will move closer to an arbitrarily small distance, this will prove the equivalence of the models.

However, it is possible that these two models are not different ways of designating the same. It is possible that they are incommensurable, and that in the end it turns out that the upper limit falls below the lower one. Then computer scientists will lose their best approximation strategy for probabilities. Unfortunately, nobody knows for sure.

Over the past couple of years, the greatest progress is expressed by two proofs that demonstrate only the complexity of this whole task.

In 2018, Thomas Vidic and Anand Natarajan proved that it is at least as difficult to evaluate the probabilities of the maximum percentage of winning in a non-local game as solving insanely complex tasks such as the traveling salesman problem. In the same year, Yuen, Vidic, Joseph Fitmsims, and Zhengfeng Ji proved that in the process of convergence of the pistons, the computational resources necessary for their further convergence grow exponentially.

Another turn in history - the question of the equivalence of models is a direct analogy of the important and complex open problem of mathematics called "Conn's hypothesis about embeddability". This situation puts mathematicians and computer scientists in a position where you can kill three birds with one stone. Having proved the equivalence of the models of tensor product and commuting operator, they immediately get an algorithm for calculating the probabilities of the maximum percentage of wins and determine the truth of the Conn hypothesis. Such an achievement deserves recognition in all related areas.

It would be appropriate to say that all these questions are deeply confused.