Shulou(Shulou.com)11/24 Report--

Picture source: Pixabay mathematician Euler asked a question of 36 officers similar to 6 × 6 Sudoku: 36 officers of 6 different ranks were selected from 6 regiments, and these 36 officers were arranged into a phalanx, can each row and column of officers belong to a different regiment and rank? Later, mathematicians proved that similar problems of order 5 and order 7 have a solution, but there is no solution at order 6. Later, a group of physicists came up with the idea: if every officer is in a state of superposition of two legions and two ranks, is there any solution to this problem? They really found a quantum solution.

Sudoku games are popular all over the world, whether you like to play or not, at least you have heard of the rules of this game: a 9 × 9 grid is divided into nine 3 × 3 "palaces". Fill the number 1x9 into these lattices. make sure there are no duplicate numbers in each row, column and house. In general, a Sudoku game will give some hints, and the rest of the 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, attracting countless players to enjoy it.

The predecessor of Sudoku can be traced back to Europe in the 18th century, when mathematician Leonhard Euler summed up a popular crossword puzzle called "Latin phalanx" (Latin square). The rule of the game is to fill in n Latin letters in the square grid of order n (similar to the number 1x 2 in order 2 Sudoku and 1 # 3 in order 3 Sudoku), so that the letters in each row and column will not repeat. This square matrix is not limited to the ninth order and has no palace restrictions, but it retains the most basic "no repetition per row and column" requirement of Sudoku.

But what fascinates Euler is a more complex version of the Latin phalanx. Euler considered filling each grid with a Latin letter and a Greek letter so that the letters in each line and column would not be repeated, and the Greek-Latin pairs in each grid would not be repeated. This kind of square is called "Greek-Latin square matrix" (Graeco-Latin square), and its essence is to combine two orthogonal Latin square matrices (orthogonal Latin squares) into one square matrix. The "orthogonal" here means that the ordered pairs of the corresponding lattices of the two matrices are not repeated. If you want to try, 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 ordered pairs.

The same third-order Greco-Latin phalanx is represented by letters, playing cards, and ordered pairs. (photo Source: arXiv:2104.05122v2) the unsolved 36-officer problem Euler found an interesting phenomenon after carefully examining the Greco-Latin phalanx: a Greco-Latin phalanx of order 3, 4, 5, and 7 can be constructed, but it is impossible to construct a 2-order and 6-order Greek-Latin matrix. The problem of order 2 is easy to deal with, through the exhaustive method, we can see that such a Greek-Latin matrix does not exist, while the problem of order 6 is relatively complex. Euler repeated the question in more popular language: 36 officers of six different ranks were selected from each of the six legions, and the 36 officers were lined up in a phalanx. Can each row and column of officers belong to different legions and ranks?

The solution to the problem of officers of rank 7. The color of the lattice represents the legion, and the symbol in the lattice represents the rank (photo source: Wikipedia) Euler believes that the "36 officer problem" problem is unsolvable, that is, there is no sixth-order Greco-Latin phalanx. And he guessed that all Greek-Latin squares with orders divided by 4 and 2 did not exist, that is to say, 2meme, 6pm, 10pm, 14. The Greek-Latin phalanx of order does not exist.

More than a century later, in 1901, the French mathematician Gaston Tarry proved by the method of exhaustion that the elements in the lattice of the 6th-order square matrix constructed according to the rules are always repeated, and the 6th-order Greco-Latin matrix does not exist. By 1959, mathematicians had proved that Euler's further conjecture was not valid, that is to say, all Greek-Latin matrices of order 2 and 6 existed. At this point, the question about the original version of Sudoku has been answered mathematically.

When the quantum solution time came to the 21st century, a group of physicists rediscovered Euler's 36 officer problem. Although the problem has been mathematically determined, they have opened up a brain from the point of view of physics: if these 36 officers are in a quantum superposition state, each officer "partly" belongs to one regiment and one rank, and "partly" belongs to another regiment and another rank, is there a solution to this problem?

Along this line of thinking, some physicists modified the construction rules of the Greco-Latin square matrix and gave a quantum version of the Sudoku game. In quantum mechanics, the state of an object can be expressed 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 six-dimensional space, and the rank can be expressed as a vector in another six-dimensional space. Because officers can be in a variety of superposition states, these vectors can be different, their arrangement into a 6 × 6 square matrix can easily meet the requirement of "different vectors in each row and column", but this is of no research value. Physicists are interested in whether the vectors of each row and column constitute a set of standard orthogonal bases of the space to which they belong.

Photo source: Olena Shmahalo can make an analogy to understand the so-called "standard orthogonal basis". In the three-dimensional space that we are familiar with, we can establish a Cartesian coordinate system, and the unit vectors along the direction of the x _ ray _ y _ Z axis in the coordinate system form a set of standard orthogonal bases. These three vectors satisfy: pairwise perpendicular in direction and unit length in size. The problem of 36 officers can be similarly understood, which means that the vectors representing the legions and ranks of officers in the 6 × 6 matrix should be satisfied: the vectors of each row and column are vertical and the size is unit length.

In fact, the 6-dimensional space representing the legion and the 6-dimensional space representing the rank can be expanded to a 36-dimensional space, and the regiment and rank of each officer can be represented by a vector in this 36-dimensional space. The 6 × 6 square matrix of these vectors still needs to be satisfied: the vectors of each row and column are vertical, and the size is unit length.

In a preprinted paper recently submitted to the physical Review KuaiBao, physicists from the Indian Institute of Technology and the University of Yagalon in Poland found an understanding of this quantum version of the 36-officer problem. They first constructed an approximate solution of a classic 6 × 6 Greek-Latin square matrix (which means that some of the elements in the grid are repeated), and then adjusted the approximate solution to a quantum version with the help of a computer. They used an algorithm to achieve this, which is a bit like brute force to solve the Rubik's cube, first spell the first row, then spell the first column, the second column, and so on, until finally spell out the complete Rubik's cube. When they repeated the algorithm over and over again, they got the solution of the quantum version of the 36 officer problem.

A solution to the quantum version 36 officer problem, the cards in each grid are in a superposition of two points and two colors, in which the size of the font reflects the size of the superposition component. (photo source: arXiv:2104.05122v2) in this paper, playing cards are used instead of officers: points A _ Magi, K _ Q, Q _ Q, J _ 10, J _ 10 and 9, and colors ♠, ♣, ♦, ♥, ✿, ✷, instead of ranks. In the final quantum solution, the cards on each lattice are in the superposition of two points and two colors. It is worth noting that whenever there is a point An in the lattice, the number of points superimposed with it must be the same as that of Kten Q and JMagol 10 and 9. Where there is a pattern ♠ in the lattice, the pattern and color superimposed with it must be ♣; ♦ and ♥, ✿ and ✷. This shows that quantum entanglement occurs in pairs of points and colors. It is precisely because of the existence of entangled states that the whole square matrix can not be decomposed into two independent Latin square matrices according to points and colors like the classical Greco-Latin square. This is also what makes the quantum Latin square special.

The researchers say that the quantum solution of this ancient Sudoku problem is equivalent to the absolute maximally entangled state (Absolutely Maximally Entangled state) of a four-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 a quantum computer, even if the data is damaged. This ancient mathematical problem, which originated from Euler, got a new answer in physics after 243 years. Perhaps this is just a fun brain for theoretical physicists, but it benefits researchers in the fields of quantum communication and quantum computing. Scientific progress often takes place in such games.

Reference link:

Https://www.quantamagazine.org/eulers-243-year-old-impossible-puzzle-gets-a-quantum-solution-20220110/

Links to papers:

Https://arxiv.org/abs/2104.05122

This article comes from the official account of Wechat: global Science (ID:huanqiukexue), written by Bai Defan, revision: Erqi

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.