The 36 km Euler officer’s problem becomes

The rules of the Latin square are simple: you have to fill in a table with Not line and Not Columns where each row and column must contain only once every number between 1 and Not (Such as Sudoku on a 9 x 9 grid, but without the additional restrictions associated with 3 x 3 squares. Now imagine that instead of having one parameter (the number), we have two (the number and the color, a Latin letter and a Greek letter, etc.). We must fill in what is then called the “Greek-Latin square”, with the same rules, but for both transactions at the same time. You can play with 3 x 3, 4 x 4, 5 x 5, 7 x 7, 8 x 8 grids… except for the trivial 2 x 2 grid, as well as another, more surprising, 6 x grid. He has no solution. At least in its classic version. Because he becomes able to accept a solution, provided the rules are subtly modified by taking inspiration from a quantum phenomenon, the phenomenon of superposition of states. This was recently demonstrated by Sohail Ahmed instead of the Indian Institute of Technology in Madras, Adam Borchardt of the Jagiellonian University in Krakow, Poland, and their colleagues. The unexpected results of this unprecedented solution open up interesting prospects for quantum computers, beyond the fun framework.

According to legend, Euler became interested in Greek-Latin squares when Empress Catherine of Russia gave him a puzzle: an army of six regiments, each marked by color. In each regiment, there are six officers of six different ranks (lieutenant, captain, colonel, etc.). Is it possible to fill a Greek-Latin square with these 36 officers and have only one repetition per color and each officer rank in each class and each column? Euler showed that all the Greek-Latin squares (number of rows or columns) single or multiple of 4 have a solution. Only the order boxes remain Not of the form 4K + 2, i.e. Not = 2, Not = 6 (status of the 36 officers), Not = 10, Not = 14, etc. Euler predicted that these cases had no solutions.

the case Not = 2 It is easy to show by exhausting all possibilities. This is two regiments, one red and one green, each commanded by a lieutenant and a commander. If we put the green lieutenant first, at the top left, the red lieutenant must necessarily be at the bottom right. But it is then impossible to respect the constraints of colors by the captain’s pose.

for the case Not = 6, it was necessary to wait nearly one hundred and twenty years after Euler for evidence of the impossibility of a solution. In 1900, the Frenchman Gaston Tarry listed all the possible cases, or 9408 distinct squares, and showed that nothing solves the problem.

In 1959, the Indian mathematicians Raj Chandra Bose and Charadchandra Shrikhandi provided a counterexample to Euler’s conjecture with an order square of 22. Then the following year, thanks to modern mathematical tools, particularly group theory, they generally invalidated Euler’s conjecture. Arrange the boxes Not of the form 4K +2 has solutions for Not Greater than 6. Cases Not = 2 and Not = 6 are the only exceptions.

So the question was solved…but that was a computation without the imagination of mathematicians and physicists. In 2020, Ion Nichita, of the Laboratory of Theoretical Physics in Toulouse, and Jordi Bilt, of the University of Burgundy, imagine a quantum version of the Latin square. A fruitful approach continues today with the work of Sohail Ahmed and even his colleagues, with their quantitative solution to the problem of the 36 officers.

To fully understand the transition from the classical to the quantum state, we must begin by formalizing the classical problem. The Greek-Latin square is a generalization of Sudoku in which the number occupying a square is replaced by a vector, which in this case is a multiple of numbers (IAnd the I) with I And the I Take values ​​between 1 and Notwhere Not It is after the box. In the previous formulation of the problem, I It is the rank of an officer I his regiment. The rules for filling in the square are then: both Not² Pairs appear only once in the entire square; all value I Based on I It only appears once per row and column.

In the quantum version, the “superposition” of vectors in the cells of the square is allowed. The idea is the same as that found in the wave functions that describe quantum systems. These functions are linear combinations of different states (or vectors) that the system has access to. The system is then said to be in a superposition of states as long as it is not measured, in which case the wave function “collapses” and the system finds itself in one state. This is the situation illustrated by Schrödinger’s cat, who finds himself in his box in a superposition of the “dead” and “alive” states as long as the box is not open.

For the quantum Greek-Latin square, then it remains to transpose the classical rules adapted to the fact that vector superpositions now fill the squares. The first condition becomes: all vectors in every row and every column must be perpendicular to each other. For example, vectors (1, 1) and (1, – 1) are perpendicular to each other. To be convinced of this, it is enough to draw it (or check that its standard product is zero). The second constraint is more precise, it consists in summing up all vectors in each line and in each column and in assuming that these sums meet the so-called “maximum entanglement” criterion.

Does this transformation of the quantum world solve the problem of the 36 officers? The superposition of states in each square of the grid results in a huge number of quantum configurations to populate the grid. But restrictions are difficult to respect, especially the second. To verify that this quantitative approach is likely to recognize a solution that meets all the criteria, Sohail Ahmed and colleagues instead started from the classical configuration that almost fits. Then they used an algorithm that modifies the cases with little touches, by injecting an overlay of graded and colored adjusters. And so they produced a quantum solution, the properties of which are amazing!

The first observation is that the coefficients that appear in superpositions of states are related to the golden ratio, (1 + √5) / 2, a number found in various fields of mathematics, for example in the following Fibonacci, in the geometric construction of a pentagon or as the only true solution to a polynomial x² –x – 1 = 0.

But the most interesting is that the obtained solution corresponds, by construction, to a composition belonging to the category of so-called “maximally entangled” states, which are actively sought by specialists in quantum information, which have not yet been found. In general, in a quantum system, two particles are said to be “entangled” when their properties are strongly correlated, at a level that cannot be explained by classical physics. These entangled systems are very useful in designing quantum computers, error-correcting codes, cryptographic tools, etc.

Extreme entanglement states are the extreme case of entangled systems, where the connections are as strong as possible. Although these instances are very useful, they are difficult to configure, and in some configurations, it is not known if they exist. In cases with two or three entangled particles, those used in the Bell and GHZ (Greenberger-Horne-Zeilinger) experiments, where the source emits two or three entangled particles toward as many observers as possible, we know very well how to say when the system is maximally entangled limit or not.

Of the four entangled particles, one does not know how well to describe what is happening, and the question of the existence of these maximally entangled states becomes even more interesting. It is then necessary to divide the problem into subparts and look at the number of cases (we are talking about local dimensions ) that can be taken by both particles. for = 2, the particles behave like coins and take the value “tails” or “heads”. In this case, specialists know that there is no maximally interlocking solution. Thus, it is possible to have two or three pieces that are interlocked to the maximum, but not four.

On the other hand, for four particles and Greater than 2, solutions are known…except = 6. Thus, from the point of view of a quantum information specialist, the question arises whether there are maximally entangled states of four particles with = 6, which amounts to the study of a quantum system of four six-sided dice. Practically speaking, if such a system is really maximally entangled, then this means that if one person (Alice) takes any pair of these four dice and rolls them, and another person (Bob) rolls the other two, then Alice can always deduce on his own The dice score obtained by Bob.

In 2020, Pawe Horodecki and colleagues from the University of Gdańsk, Poland, identified the problem of a four-particle maximum entanglement system with = 6 as one of the five biggest open problems in quantum computing.

However, the solution of the 6-dimensional Greek-Latin square obtained by Sohail Ahmed Rather and colleagues proves the existence of maximally entangled systems of four six-sided dice, by providing an example. This result will be particularly useful for designing error-correcting codes, which are a key component of quantum computers, because they allow detection and correction of errors in qubits (the units of information in these computers) without revealing the exact state of these qubits, otherwise the efficiency of these machines will be reduced to nothing. .