Image source: Pixabay
The mathematician Euler once asked a question similar to the 36 officers of 6×6 Sudoku: 36 officers of 6 different ranks were selected from 6 corps, and the 36 officers were arranged in a phalanx, could each line and column of officers belong to different corps and ranks? Later mathematicians proved that similar 5th- and 7th-order problems have solutions, except for 6th-order problems. Later, a group of physicists opened their minds: If every officer was in a superposition of two corps and two ranks, was there any solution to this problem? They really found a quantum solution...
Sudoku is all the rage around the world, whether you love to play it or not, at least you have heard the rules of this game: a grid of 9×9 is divided into 9 "houses" of 3×3, and the numbers 1 to 9 are filled into these grids to ensure that there are no duplicate numbers in each row, column and house. Generally, a Sudoku game will give a part of the number of hints, and the remaining numbers need to be filled in by the player's reasoning. It is such a simple rule that has spawned a lot of problem-solving skills that have attracted countless players to enjoy it.
The predecessor of Sudoku dates back to 18th-century Europe, and mathematician Leonhard Euler summed up a popular crossword puzzle of the time called the Latin square. The rule of the game is to fill in n Latin letters in a square grid of n orders (similar to the 2nd order Of Sudoku, fill in the numbers 1 to 2, and the 3rd order of Sudoku fill in 1 to 3) so that the letters of each row and column are not repeated. This phalanx is not limited to the 9th order, nor is there a limit to the palace, but retains the most basic "no repetition per row and every column" requirement of Sudoku.
But what fascinates Ou la is a more complex version of the Latin phalanx. Euler considered filling each cell with a Latin letter and a Greek letter so that the letters in each row and column were not repeated, and the Greco-Latin pairs in each cell were not duplicated. This phalanx is called the "Graeco-Latin square", and its essence is to combine two orthogonal Latin squares into one square. The "orthogonal" here means that the ordered pairs of two squares corresponding to the lattice are not repeated. If you want to try it too, the elements in the grid don't have to be Greek and Latin letters, you can also use a combination of playing cards, or even an ordered number pair.
The same third-order Greek-Latin phalanx is represented by pairs of letters, poker suits, and ordinal numbers. (Image source: arXiv: 2104.05122v2)
Unsolved 36 officer questions
Euler found an interesting phenomenon after carefully examining the Greco-Latin squares: 3rd, 4th, 5th, and 7th orders of Greek-Latin squares can be constructed, but 2nd and 6th order Greco-Latin squares cannot be constructed. The problem of the 2nd order is easier to deal with, and it can be seen through exhaustive method that such a Greek-Latin phalanx does not exist, while the problem of the 6th order is relatively complicated. Euler repeated the problem in more colloquial language: 36 officers from each of the 6 corps with 6 different ranks, and arranging these 36 officers in a phalanx, can each line and column of officers belong to different regiments and ranks?
Solution to the 3rd, 4th, 5th, 7th rank officer problem. The color of the lattice represents the legion, and the symbol in the lattice represents the rank (Image: Wikipedia)
Euler believed that the "36 officer problem" problem was unsolvable, that is, there was no 6th order Greek-Latin phalanx. And he guessed that all Greco-Latin squares of order divided by 4 more than 2 do not exist, that is, 2, 6, 10, 14... Neither the Hellenistic-Latin phalanx of the order exists.
More than a century later, in 1901, the French mathematician Gaston Tarry confirmed by exhaustive example that the 6th-order phalanx constructed according to the rules always had the elements in the lattice being repeated, and the 6th-order Greco-Latin phalanx did not exist. By 1959, mathematicians had shown that Euler's further conjectures were untenable, that is, Greek-Latin squares of all orders except for the 2nd and 6th orders existed. At this point, the question about the original Sudoku has a mathematical answer.
Quantum solution
Fast forward to the 21st century, and a bunch of physicists have revisited Euler's 36 officer problem. Although the question has been mathematically settled, they have a hole in physics: If these 36 officers are in a quantum superposition state, and each officer belongs "partially" to one corps and one rank, and "partly" to another corps and another rank, is there a solution to this problem?
Along this line of thinking, physicists have modified the construction rules of the Greco-Latin square matrix to give a quantum version of the Sudoku game. In quantum mechanics, the state of an object can be represented by a vector. In the Quantum Edition 36 Officer problem, the legion to which each officer belongs can be represented as a vector in a 6-dimensional space, and the rank to which it belongs can be represented as a vector in another 6-dimensional space. Since officers can be in various superpositions, these vectors can be different, and the 6×6 squares they are arranged into can easily meet the requirement that "the vectors of each row and column are different", but this has no research value. Physicists are interested in whether the vectors of each row and column constitute a set of standard orthogonal bases in the space to which they belong.
Image credit: Olena Shmahalo
To understand the so-called "standard orthogonal basis", an analogy can be made. In the three-dimensional space we are familiar with, a Cartesian coordinate system can be established, and the unit vectors along the x, y, and z axes in the coordinate system constitute a set of standard orthogonal bases, and these three vectors are satisfied: two vertical in the direction, and the unit length in size. The 36 officer problem can be understood similarly, which means that the vectors representing the officer corps and rank in the 6×6 phalanx must be satisfied: the vectors of each row and column are two vertical and two vertical, and the size is the unit length.
In fact, the 6-dimensional space representing the corps and the 6-dimensional space representing the rank can be expanded into a 36-dimensional space, and the corps and rank of each officer can be represented by a vector in this 36-dimensional space. These vectors are arranged into 6×6 squares that still need to be satisfied: the vectors of each row and column are two vertical and two vertical, and the size is per unit length.
In a recent preprint paper submitted to The Physical Review Letters, physicists from the Indian Institute of Technology, the Jagiellonian University in Poland and other institutions found insight into the quantum version of the 36 officer problem. They first constructed a classical 6×6 Greek-Latin phalanx approximation (meaning that some of the elements in the lattice are duplicated), and then, with the help of a computer, adjusted the approximation to a quantum version of the solution. They did this using an algorithm that was a bit like a brute force cube, spelling the first row first, then the first column, the second column, and so on, until finally spelling out the complete Rubik's cube. When they repeated the algorithm over and over again, they got the solution to the quantum version of the 36 officer problem.
A solution to the Quantum Edition 36 Officer problem, the cards in each grid are in a superposition of two points and two suits, where the size of the font reflects the size of the superimposed weight. (Image source: arXiv: 2104.05122v2)
The paper replaced the officers with playing cards: points A, K, Q, J, 10, 9 replaced the legions; the suit ,,,,, replaced the ranks. In the final quantum solution, the cards on each grid are in a superposition of two points and two suits. It is worth noting that whereever a point A appears in the grid, the number of points superimposed on it must be K; Q and J, 10 and 9 are the same. And wherever a suit color appears in the lattice, the color superimposed on it must be; and, with the same reason. This shows that the number of points and the suit color are quantum entangled in pairs. It is precisely because of the existence of entanglement that the entire phalanx cannot be decomposed into two independent Latin phalanxes by points and suits like the classical Greek-Latin phalanx. This is also what makes the quantum Latin square matrix special.
The researchers say the quantum solution to this ancient Sudoku problem is equivalent to an absolutely Maximally Entangled state of a 4-particle system. This entangled state can be applied to many scenarios such as error correction in quantum computing, such as storing redundant information in this state in quantum computers, even if the data is corrupted, the information can be saved. This ancient mathematical problem, which originated in Euler, received a new physical solution 243 years later. Perhaps for theoretical physicists, this is just a fun brain hole, but it has benefited researchers in the field of quantum communication and quantum computing. Advances in science often happen in games like this.
Written by | Bai Defan
Review |27
Reference Links:
https://www.quantamagazine.org/eulers-243-year-old-impossible-puzzle-gets-a-quantum-solution-20220110/
Thesis Link:
https://arxiv.org/abs/2104.05122
The reproduced content represents the views of the author only
Does not represent the position of the Institute of Physics, Chinese Academy of Sciences
Source: Global Science
EDIT: Hidden Idiot