20.06.2022 change 20.06.2022

Scientists find quantum solution to Euler’s classically unsolvable problem

A new entangled state presented by scientists in the solution to Euler's 36 officers puzzle would assume a set of four dice entangled in such a way that observing the result of any two dice allows to predict the result of the throw with the remaining two dice. Photo: Authors' materials A new entangled state presented by scientists in the solution to Euler's 36 officers puzzle would assume a set of four dice entangled in such a way that observing the result of any two dice allows to predict the result of the throw with the remaining two dice. Photo: Authors' materials

An ‘impossible-to-solve’ problem from the 18th century has been cracked by scientists in Poland and India with the help of quantum mechanics.

There were 25 officers: each of the 5 army regiments had 5 officers of 5 different ranks. In each row and in each column there should be exactly one officer of a given rank and exactly one from each regiment. The easiest way to imagine it is as a 5x5 sudoku, but to make things more difficult, colours are also assigned to numbers. Not only numbers, but also colours must be arranged in rows and columns without repetitions.

Being an outstanding mathematician, Euler soon found a solution for 25 officers, but the problem can be considered for squares of any size - later called Graeco-Latin squares or Euler squares (chess pieces of different colours are often used to illustrate such squares).

It turns out that a solution exists for squares with a side of 3, 4, 5, 7, 8, 9, 10 and all subsequent natural numbers. The exception is the number 6, for which there is no solution. This problem was called the Euler's 36 officers puzzle. The mathematical proof that officers cannot be arranged in a square without any repetitions was presented in the early 20th century by the French amateur mathematician Gaston Tarry, whose solution was presented to the French Academy of Sciences.

Kwadraty o boku 3, 4, 5, 7 i każdej kolejnej licznie naturalnej daje się przestawić w postaci klasycznego kwadratu łacińskiego. A o boku 6 - nie. Rys.: Cmglee  CC BY-SA 4.0, via Wikipedia
Squares with a side of 3, 4, 5, 7 and all subsequent natural numbers can be presented in the form of a classic Latin square. A squares with the side of 6 cannot. Credit: Cmglee  CC BY-SA 4.0, via Wikipedia

Euler's 36 officers puzzle was bugging the physicists from the Polish team. The researchers wondered if the task could be solved if the problem was slightly reformulated to accept the quantum nature of officers. This means that one place can be occupied not necessarily by one officer, but by their quantum mix - in the right proportions. However, this change introduces an unimaginably large range of additional possibilities allowed by the rules of mathematics, which should be tested.

Przedstawione przez polski-hinduski zespół kwantowe rozwiązanie problemu 36 oficerów Eulera. Rozmiary figur reprezentują prawdopodobieństwo znalezienia się danego oficera w jakimś polu. Rys: Alpodiopa, CC BY-SA 4.0, via Wikipedia
The solution to Euler's 36 officers puzzle presented by the team of scientists from Poland and India. The relative sizes of chess pieces denote the contribution of the corresponding quantum states. Credit: Alpodiopa, CC BY-SA 4.0, via Wikipedia

The physicists returned to their computers with new curiosity, began to test further ideas and it turned out that there was also a strict solution to the problem. This solution uses a previously unknown extreme state of quantum entanglement of four subsystems. The results were published in Physical Review Letters in a paper highlighted by editors. 

Rozwiązanie kwantowego problemu Eulera przedstawione na szachownicy 6 na 6:  każde pole symbolizuje oficera odpowiadającego superpozycji stanów kwantowych,  a wielkość każdej figury odzwierciedla jej udział w danym stanie. Kolory wyznaczają podział 36 oficerów na 9 grup,  każda po czterech  oficerów.  Rys. Wojciech Bruzda
Quantum solution to Euler's problem presented on a 6 by 6 chessboard. Each field symbolizes the officer corresponding to the superposition of quantum states, and the size of each piece denotes its contribution to a given state. The colours determine the division of 36 officers into 9 groups, four officers each. Credit: Wojciech Bruzda

Dr. Karol Życzkowski from the Jagiellonian University and the Center for Theoretical Physics of the Polish Academy of Sciences said: “Quantum entanglement is an unexpected correlations of systems. Translating it to a macroscopic scale, if we have two absolutely maximally entangled coins, after learning the result of the first coin toss, we would also know the result of tossing the second coin.”

He added that the entanglement of two systems (quite well described in physics) is not enough to find a solution to the quantum version of Euler's puzzle.

Dr. Grzegorz Rajchel-Mieldzioć, who defended his doctorate at the Center for Theoretical Physics PAS in Warsaw, currently working at the ICFO Institute in Barcelona, continued that in order to solve Euler's puzzle, it was necessary to look for systems entangled in a more complicated way. He said: “Physicists were inclined to say that there could not be absolutely maximally entangled four six-sided systems, the same as the size of the Euler's square. And yet we showed mathematically that such an entanglement exists and can be relatively simply constructed, despite the fact that the classic methods did not work for the construction of this entanglement.”

To explain what this new entangled state, physicists use comparison with the throw of four cubic dice of four colours, and the results describe another variable in the system: the row and column in the square, as well as the rank and regiment of the officer. In a tangled quantum state, the dice are so entangled that observation of the result of any two dice allows to predict the result of the remaining two dice.

Jeśli cztery kostki znajdą się w maksymalnie splątanym stanie kwantowym przedstawionym na zdjęciu w konwencji brydżowej,  to  wynik rzutu dwóch dowolnie wybranych kostek pozwoli przewidzieć wyniki rzutu pozostałych dwóch  (fot. Paulina Rajchel-Mieldzioć).
If the four dice are in the absolutely maximally entangled quantum state shown in the photo in the bridge convention, the result of the throw of any two dice will allow to predict the results of the other two dice (credit: Paulina Rajchel-Mieldzioć).

The solution presented by the physicists is additionally quite elegant from a mathematical point of view: it uses the division of the board into nine blocks, each consisting of four fields. And also the golden ratio φ, characteristic of the golden division of the section known in ancient times, in which the ratio of the longer part to the whole is the same as the ratio of its shorter part to a longer one.

It would all remain a beautiful theory combining quantum mechanics and logical puzzles, but at one of the scientific conferences an idea appeared for using the work of the scientists from Poland and India in practice. It turns out that the absolutely maximally entangled states described in Phys. Rev. Letters can be used to test the power of quantum computers.

Dr. Adam Burchardt, who defended his doctorate in physics at the Jagiellonian University and is currently working at QuSoft in Amsterdam, said: “Quantum computers are weak for now: they either have few qbits and low computing power, or a lot of qbits and low accuracy.

'However, we can expect that their capabilities will increase over time. So it would be good to have methods up your sleeve that will allow to test how fast and accurate the calculations on a given quantum computer are. Algorithms in which it would be necessary to produce maximally entangled states - such as the ones we propose - would be a good method of conducting the test, whether the computer is already powerful enough. Because if a quantum computer is not able to entangle qbits in the way we have proposed, it means that it is not very powerful.”

PAP - Science in Poland, Ludwika Tomala

lt/ ekr/ kap/

tr. RL

Przed dodaniem komentarza prosimy o zapoznanie z Regulaminem forum serwisu Nauka w Polsce.

Copyright © Foundation PAP 2023