Scientists find quantum solution to Euler’s classically unsolvable problem
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.
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.
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.
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.
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/