Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution

Quantum Latin squares were quickly adopted by a community of theoretical physicists and mathematicians interested in their unusual properties. Last year, the French mathematical physicists Ion Nechita and Jordi Pillet created a quantum version of Sudoku—SudoQ. Instead of using the integers 0 through 9, in SudoQ the rows, columns, and subsquares each have nine perpendicular vectors.

These advances led Adam Burchardt, a postdoctoral researcher at Jagiellonian University in Poland, and his colleagues to reexamine Euler’s old puzzle about the 36 officers. What if, they wondered, Euler’s officers were made quantum?

In the classical version of the problem, each entry is an officer with a well-defined rank and regiment. It’s helpful to conceive of the 36 officers as colorful chess pieces, whose rank can be  king, queen, rook, bishop, knight, or pawn, and whose regiment is represented by red, orange, yellow, green, blue, or purple. But in the quantum version, officers are formed from superpositions of ranks and regiments. An officer could be a superposition of a red king and an orange queen, for instance.

Critically, the quantum states that compose these officers have a special relationship called entanglement, which involves a correlation between different entities. If a red king is entangled with an orange queen, for instance, then even if the king and queen are both in superpositions of multiple regiments, observing that the king is red tells you immediately that the queen is orange. It’s because of the peculiar nature of entanglement that officers along each line can all be perpendicular.

The theory seemed to work, but to prove it, the authors had to construct a 6-by-6 array filled with quantum officers. A vast number of possible configurations and entanglements meant they had to rely on computer help. The researchers plugged in a classical near-solution (an arrangement of 36 classical officers with only a few repeats of ranks and regiments in a row or column) and applied an algorithm that tweaked the arrangement toward a true quantum solution. The algorithm works a little like solving a Rubik’s Cube with brute force, where you fix the first row, then the first column, second column and so on. When they repeated the algorithm over and over, the puzzle array cycled closer and closer to being a true solution. Eventually, the researchers reached a point where they could see the pattern and fill in the few remaining entries by hand.

Euler was, in a sense, proved wrong—though he couldn’t have known, in the 18th century, about the possibility of quantum officers.

“They close the book on this problem, which is already very nice,” said Nechita. “It’s a very beautiful result, and I like the way they obtain it.”

One surprising feature of their solution, according to coauthor Suhail Rather, a physicist at the Indian Institute of Technology Madras in Chennai, was that officer ranks are entangled only with adjacent ranks (kings with queens, rooks with bishops, knights with pawns) and regiments with adjacent regiments. Another surprise was the coefficients that appear in the entries of the quantum Latin square. These coefficients are numbers that tell you, essentially, how much weight to give different terms in a superposition. Curiously, the ratio of the coefficients that the algorithm landed on was Φ, or 1.618…, the famous golden ratio.