The puzzle
In the 18th century, Leonhard Euler, one of the most prolific and prominent mathematicians that ever lived, proposed the following math puzzle:
“Six different regiments have six officers, each one belonging to different ranks. Can these 36 officers be arranged in a square formation so that each row and column contains one officer of each rank and one of each regiment?”
The thirty-six officers sudoku-style problem is a particular case of the generalization to the NxN, with N > 1, whose solution is known as the Graeco-Latin Squares. Take, for example, 2 regiments, a black regiment, and a red regiment. Each regiment has two officers, say, a colonel and a lieutenant. It is easy to verify that the 2X2 boxes square has no possible arrangement following Euler’s rules. That means there are no Graeco-Latin Squares for the 2×2 case. However, adding a third blue regiment and a third officer, say a major, can be neatly organized in Graeco-Latin Squares.
Euler used a card game to visualize the solution. Fig1.
Here officers’ ranks would be kings, queens, and aces; and their possible regiment diamonds, clubs, and spades. Ignore the colors.
It is also easy to figure the solutions out for N=4 and N=5. Imagine a complicated sudoku where numbers have labels and they are actually human beings: they can’t stand in 2 boxes of the square at the same time.
However, Euler observed that the 36 officers’ arrangement as Graeco-Latin Squares was impossible. It was not until 1900 that the French mathematician Gaston Tarry formally proved that the problem has no solution—using classical tools.
The general NXN solution has been proven to exist for odd numbers and multiples of 4.
A quantum physics solution: the entangled officers
In a recent work published in Physical Review Letters, Suhail Rather and collaborations reformulated the Euler puzzle defining the officers in the realm of quantum mechanics. For example, a single quantum officer could be a colonel in the black regiment and a lieutenant in the red regiment at the same time. Now, the rank and the regiment are quantum labels.
The researchers defined each quantum officer so that they are entangled. That means the components of a single quantum officer are inseparable; each component cannot be fully described without considering all others. In other words, they become a single quantum object. In this mathematical setting, Rather and collaborations found an analytic solution for the 36 officers Euler problem. In fig. 2., extracted from their preprint in arxiv.org, they use an extension to the “card game” to visualize the quantum solution. Note that a classical solution would include only one card per box, while the quantum solution has one quantum entangled officer, where kings are entangled to aces, queens to jokers, and 9s to 10s. They did not entangled colors in the visualization.
Applications in quantum information
Quantum entanglement has many exciting applications, such as quantum computing, teleportation, and quantum information, enabling spy-proof communications. Scientists have identified a class of entanglement called absolutely maximally entangled (AME). Maximally entangled means they are perfectly correlated. It doesn’t matter how far apart its components are, they remain entangled. AME objects are needed in quantum information and teleportation; any other kind of entangled object does not work properly.
Rather and collaborators found that their Quantum Graeco-Latin Squares solution to the Euler problem is maximally entangled, providing clues on how to solve a particular AME case that has been challenging to define for decades. Moreover, they proposed and proved a theorem of the existence of its solution.
The history of mathematics has many examples of solving long-standing problems, creating new structures, and even new areas of math using physics. Quantum mechanics has demonstrated to be a powerful tool.
References
Rather, S. A., Burchardt, A., Bruzda, W., Rajchel-Mieldzioć, G., Lakshminarayan, A., & ŻYczkowski, K. (2022). Thirty-six Entangled Officers of Euler: Quantum Solution to a Classically Impossible Problem. Physical Review Letters, 128(8). https://doi.org/10.1103/physrevlett.128.080507
A revised version of their preprint is available here: https://arxiv.org/abs/2104.05122
Tarry, G. (1900). Le problème de 36 officiers. Compte Rendu de l’Association Française pour l’Avancement des Sciences. Secrétariat de l’Association. 1, 122 .
Featured illustration by Suhail Rather et al.
