Over 240 years ago, famous mathematician Leonhard Euler came up with a question: if six army regiments each have six officers of six different ranks, can they be arranged in a square formation such that no row or column repeats either a rank or regiment?
After searching in vain for a solution, Euler declared the problem impossible – and over a century later, the French mathematician Gaston Tarry proved him right. Then, 60 years after that, when the advent of computers removed the need for laboriously testing every possible combination by hand, the mathematicians Parker, Bose, and Shrikhande proved an even stronger result: not only is the six-by-six square impossible, but it’s the only size of square other than two-by-two that doesn’t have a solution at all.
Now, in mathematics, once a theorem is proven, it’s proven forever. So it may be surprising to learn that a 2022 paper, published in the journal Physical Review Letters, has apparently found a solution. There’s just one catch: the officers have to exist in a state of quantum entanglement.
“I think their paper is very beautiful,” quantum physicist Gemma De las Cuevas, who was not involved with the work, told Quanta Magazine at the time. “There’s a lot of quantum magic in there. And not only that, but you can feel throughout the paper [the authors’] love for the problem.”
To explain what’s going on, let’s start with a classical example. Euler’s “36 Officers” problem, as it is known, is a special type of magic square called an “orthogonal Latin square” – think of it like two sudokus that you have to solve at the same time in the same grid. For example, a four-by-four orthogonal Latin square might look like this:
No color repeats in any direction; no number repeats in any direction; all numbers in all colors are represented.
Image credit: IFLScience
With each square in the grid defined like this – with a fixed number and a fixed color – Euler’s original six-by-six problem is impossible. However, in the quantum world, things are more flexible: things exist in superpositions of states.
In basic terms – or at least, as basic as it can get when we’re talking about quantum physics – this means that any given general can be multiple ranks of multiple regiments at the same time. Using our colorful double-sudoku example, we could imagine a square in the grid being filled with, say, a superposition of a green two and a red one.
Reen owo? Gred Tone?
Image credit: IFLScience
Now, the researchers thought, Euler’s problem would have a solution. But what was it?
At first glance, it might seem that the team had made their job a lot harder. Not only did they have to solve a six-by-six double sudoku that was known to be impossible in the classical setting, but now they had to do it in multiple dimensions at once.
Luckily, though, they had a couple of things on their side: first, a classical near-solution that they could use as a jumping-off point, and second, the seemingly mysterious property of quantum entanglement.
Put simply, two states are said to be entangled when one state tells you something about the other. As a classical analogy, imagine you know your friend has two children, A and B (your friend isn’t good at names) of the same gender. That means that knowing that child A is a girl tells you with certainty that child B is also a girl – the two children’s genders are entangled.
Entanglement doesn’t always work out this nicely, where one state tells you absolutely everything about the other – but when it does, it’s called an absolutely maximally entangled (AME) state. Another example might be flipping coins: if Alice and Bob each flip a coin and Alice gets heads, then if the coins are entangled, Bob knows without looking that he got tails, and vice versa.
Remarkably, the solution to this quantum officer problem turned out to have this property – and this is where it gets really interesting. See, the example above works for two coins, and for three, but for four, it’s impossible. But the 36 Officers problem isn’t like flipping dice, the authors realized – it’s more like rolling entangled dice.
“[Imagine that] Alice selects any two dice and rolls them, obtaining one of 36 equally likely outcomes, as Bob rolls the remaining ones. If the entire state is AME, Alice can always deduce the result obtained in Bob’s part of the four-party system,” the paper explains.
“Furthermore, such a state allows one to teleport any unknown, two-dice quantum state, from any two owners of two subsystems to the lab possessing the two other dice of the entangled state of the four-party system,” the authors continue. “This is not possible if the dice are replaced by two-sided coins.”
Because these AME systems can often be explained using orthogonal Latin squares, researchers already knew that they exist for four people throwing dice with any number of sides at all – any, that is, other than two or six. Remember: those orthogonal Latin squares don’t exist, so they can’t be used to prove the existence of an AME state in that dimension.
However, by finding a solution to Euler’s 243-year-old problem, the researchers had done something amazing: they had found an AME system of four parties of dimension six. In doing so, they may even have discovered a whole new kind of AME – one with no analog in a classical system.
“Euler … claimed in 1779 that no solution exists. The proof, by Tarry, came only 121 years later in 1900,” the authors write. “After another 121 years, we have presented a solution to the quantum version wherein the officers can be entangled.”
“The quantum design presented here will likely trigger further research in the nascent field of quantum combinatorics,” they conclude.
The study is published in Physical Review Letters.
An earlier version of this article was published in January 2022.
Source Link: "Impossible" Puzzle Solved After 243 Years Using Quantum Entanglement
