Physicists find the answer to a math puzzle that was judged to be unsolvable

Sudoku game is popular all over the world. Whether you love to play it or not, you have at least heard of the rules of this game: a 9×9 grid is divided into nine 3×3 “houses”, and the numbers 1~9 are filled in In these grids, it is necessary to ensure that there are no repeated numbers in each row, column, and house. Generally, a Sudoku game will give some hints, and the remaining numbers need to be filled in by the player's reasoning. It is such a simple rule that has derived a lot of problem-solving skills, which has attracted countless players to enjoy it.

The predecessor of Sudoku can be traced back to Europe in the 18th century. The mathematician Leonhard Euler summarized a popular crossword puzzle called Latin square. The rule of the game is to fill in n kinds of Latin letters in the n-order square grid (similar to the number 1~2 in the second-order Sudoku, and 1-3 in the third-order Sudoku) so that each letter in each row and column will not be repeated. This square matrix is ​​not limited to the 9th order, and there is no palace limit, but it retains the most basic requirement of Sudoku no repetition of each row and column.

But it was a more complicated version of the Latin phalanx that fascinated Euler. Euler considered filling each grid with a Latin letter and a Greek letter so that the letters in each row and column will not be repeated, and the Greek-Latin letter pairs in each grid will not be repeated. This kind of square is called Greco-Latin square, and its essence is to combine two orthogonal Latin squares into one square. The "orthogonal" here means that the ordered pairs formed by the corresponding lattices of the two square matrices are not repeated. If you also want to try, the elements in the grid do not have to be Greek and Latin letters, you can also use combinations of suits of playing cards, or even pairs of ordered numbers.

The same third-order Greek-Latin square matrix is ​​represented by letters, poker suits, and ordered number pairs. (Image source: arXiv:2104.05122v2)

Unsolvable 36 officer problem

After carefully examining the Greek-Latin square matrix, Euler discovered an interesting phenomenon: the Greek-Latin square matrix of order 3, 4, 5, and 7 can be constructed, but the Greek-Latin square matrix of order 2 and 6 cannot be constructed. Latin square. The 2nd-order problem is easier to deal with. Through the exhaustive method, it can be seen that such a Greek-Latin square matrix does not exist, and the 6th-order problem is relatively complicated. Euler repeated this problem in a more popular language: a total of 36 officers with 6 different military ranks were selected from each of the 6 legions, and the 36 officers were arranged in a square array. Different regiments and ranks?

The solution of the 3rd, 4th, 5th, and 7th rank officer problem. The color of the grid represents the legion, and the symbols in the grid represent the military rank

Euler believed that this "36 officer problem" problem is unsolvable, that is, there is no Greek-Latin phalanx of order 6. And he conjectured that all Greek-Latin square matrices whose order is divided by 4 mod 2 do not exist, that is to say, no Greek-Latin square matrices of order 2, 6, 10, 14... do not exist.

More than a century later, in 1901, the French mathematician Gaston Tarry proved through the exhaustive method that the square matrix of order 6 constructed according to the rules will always have repeated elements in the lattice, and the order 6 The Greek-Latin phalanx really didn't exist. In 1959, some mathematicians proved that Euler's further conjecture was untenable, that is to say, except for the 2nd and 6th order, the Greek-Latin square matrices of other orders exist. So far, this question about the original version of Sudoku has a mathematical answer.

Quantum solution

The time came to the 21st century, and a group of physicists rediscovered Euler's 36 officer problem. Although this problem has been settled mathematically, they opened up a brain hole from the perspective of physics: if these 36 officers are in a quantum superposition state, each officer "partially" belongs to a regiment and a rank, and partially belonged to another regiment and another rank, is there still a solution to this problem?

Following this line of thought, some physicists modified the construction rules of the Greek-Latin square matrix and gave a quantum version of the Sudoku game. In quantum mechanics, the state of an object can be represented by a vector. In the quantum version of the 36-officer problem, the regiment to which each officer belongs can be expressed as a vector in a 6-dimensional space, and the rank to which each officer belongs can be expressed as a vector in another 6-dimensional space. Since officers can be in various superposition states, these vectors can be different, and the 6×6 square matrix they are arranged in can easily meet the requirement of vectors in each row and column are different, but this has not been studied value. Physicists are interested in whether the vectors in each row and column form an orthonormal basis for the space to which they belong.

To understand the so-called orthogonal basis, you can make an analogy. 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-axis directions in the coordinate system constitute a set of standard orthogonal bases. These three vectors satisfy all of which are unit length in size. The 36 officer problem can be understood in a similar way, which means that the vectors representing the officer corps and military rank in the 6×6 square matrix must satisfy: the vectors in each row and column are perpendicular to each other, and the size is unit length.

In fact, the 6-dimensional space representing the corps and the 6-dimensional space representing the military rank can be expanded into a 36-dimensional space, and the corps and military rank of each officer can be represented by a vector in this 36-dimensional space. The 6×6 square matrix formed by these vectors still needs to satisfy the vectors in each row and column are perpendicular to each other, and the size is unit length.

In a recent preprint paper submitted to Physical Review Letters, physicists from the Indian Institute of Technology, Jagiellonian University in Poland, and others found an answer to this quantum version of the 36-officer problem. They first constructed an approximate solution to the classical 6×6 Greek-Latin square matrix (meaning that some elements in the grid are repeated), and then, with the help of a computer, adjusted this approximate solution to a quantum version untie. They did this using an algorithm that was a bit like brute-force solving a Rubik's cube, starting with the first row, then the first column, then the second column, and so on, until finally the complete Rubik's cube was solved. When they repeated the algorithm over and over, they got a quantum version of the 36-officer solution.

A solution to the quantum version of the 36 officer problem. The cards in each grid are in a superposition state of two types of points and two suits, and the size of the font reflects the size of the superposition component. (Image source: arXiv:2104.05122v2)

This paper replaces officers with playing cards: A, K, Q, J, 10, 9 for legions; suits ♠, ♣, ♦, ♥, ✿, ✷ for ranks. In the final quantum solution, the cards on each grid are in the superposition state of two kinds of points and two suits. It is worth noting that whenever point A appears in the grid, the superimposed point must be K; Q and J, 10 and 9 are the same. And if the suit ♠ appears in the grid, the superimposed suit must be ♣; ♦ and ♥ ✿ and ✷ are the same. This shows that quantum entanglement occurs in pairs of points and suits. It is precise because of the existence of entanglement that the entire square matrix cannot be decomposed into two independent Latin squares according to the points and suits like the classic Greek-Latin square. This is also the special feature of the quantum Latin square.

The quantum solution to this ancient Sudoku problem is equivalent to an Absolutely Maximally Entangled state of a 4-particle system, the researchers say. 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 a quantum computer, even if the data is damaged, the information can be preserved. This ancient mathematical problem originated from Euler, who got a new answer in physics after 243 years. Perhaps for theoretical physicists, this is just fun brainstorming, but it has benefited researchers in the fields of quantum communication and quantum computing. Scientific progress often happens in such games.