"Impossible" Puzzle Solved After 243 Years Using Quantum Entanglement

 

Famed mathematician Leonhard Euler posed the following query more than 240 years ago: can six army regiments, each with six commanders of six distinct ranks, be placed in a square arrangement so that no row or column repeats a rank or regiment?

The French mathematician Gaston Tarry validated Euler's declaration that the problem was impossible after he spent more than a century trying in vain to find a solution. The mathematicians Parker, Bose, and Shrikhande then demonstrated an even more compelling result sixty years later: not only is the six-by-six square impossible, but it is the only square size other than two-by-two that has no solution at all. This was made possible by the development of computers, which eliminated the need for tediously testing every possible combination by hand.

A theorem in mathematics is now considered proven for all time upon proof. Therefore, it might come as a surprise to hear that a 2022 study that was released in the journal Physical Review Letters seems to have solved the problem. The police must exist in a state of quantum entanglement, but there's a catch.

At the time, quantum physicist Gemma De las Cuevas, who was not involved with the experiment, told Quanta Magazine, "I think their paper is very beautiful." "A lot of quantum wizardry is present there. Furthermore, the author's passion for the issue is evident throughout the entire text.

To begin elucidating the situation, let us consider a traditional example. Euler's "36 Officers" problem is a unique kind of magic square known as an "orthogonal Latin square"; it can be compared to two sudoku puzzles that must be solved concurrently in the same grid. A four-by-four orthogonal Latin square, for instance, would resemble this:

This definition of a fixed number and color for each square in the grid makes Euler's original six-by-six issue unworkable. Things are more malleable in the quantum world, though, where entities exist as superpositions of states.

This basically means that any given general can be several ranks of numerous regiments at the same time, or as basic as it gets when we're talking about quantum physics. We could envision a square in the grid being filled with, say, a superposition of a green two and a red one, using our colorful double-sudoku example.

It could appear that the crew had significantly increased the difficulty of their work at initially. They had to tackle a six-by-six double sudoku puzzle, which was known to be unsolvable in a classical environment, in addition to doing it simultaneously in multiple dimensions.

Fortunately, they were aided by two factors: the first was a classical near-solution that they could utilize as a starting point, and the second was the enigmatic characteristic of quantum entanglement.

To put it simply, when one state reveals information about another, two states are said to be entangled. Using a traditional example, let's say you are aware that your friend has two identically titled children, A and B (your friend isn't very good at names). In other words, the genders of the two children are intertwined, thus knowing that child A is a girl gives you confidence that child B is a female as well.

When entanglement functions in such a way that one state provides complete information about the other, it is referred to as an absolutely maximally entangled (AME) state. However, this is not always the case. Another example would be tossing coins. If Bob and Alice each toss and Alice come up with heads, Bob will know without having to look that he got tails, and vice versa, if the coins are intertwined.

This is where things get very interesting: the quantum officer problem's solution, surprisingly, turned out to have this feature. As you can see, the aforementioned example functions with two coins and with three, but not with four. The writers came to the realization that the 36 Officers dilemma is more akin to rolling entangled dice than it is to flipping dice.

Imagine that Bob rolls the other six dice, and Alice rolls any two she chooses, getting one of the 36 equally possible results. The study states that Alice can always infer the outcome of Bob's portion of the four-party system if the full state is AME.

"On top of that, this kind of state permits the teleportation of any unknown, two-dice quantum state, from any two subsystem owners to the lab that has the other two dice of the entangled state of the four-party system," the authors write. "If two-sided coins are used in place of the dice, this is not possible.”

Researchers previously recognized that these AME systems exist for four persons throwing dice with any number of sides at all — that is, any other than two or six – since these systems can frequently be explained using orthogonal Latin squares. Recall that there is no way to use those nonexistent orthogonal Latin squares to demonstrate the presence of an AME state in that dimension.

But the researchers had accomplished something extraordinary by solving Euler's 243-year-old puzzle: they had discovered an AME system of four parties in dimension six. They might have even found a completely new type of AME in the process, one that has no homolog in a classical system.

In 1779, Euler asserted that there is no known solution. The authors state that Tarry's evidence was discovered just 121 years later, in 1900. "We have solved the quantum version where the officers can be entangled, after an additional 121 years."

They end by saying, "More research in the emerging field of quantum combinatorics will probably be sparked by the quantum design presented here."