Leonhard Euler, a prominent mathematician, posed a question over 240 years ago: if six army regiments each contain six commanders of six different ranks, can they organized in a square so that no rank or regiment repeated in any row or column. After failing to find a solution, Euler called the issue intractable — and the French mathematician Gaston Tarry proved him correct over a century later. The mathematicians Parker, Bose, and Shrikhande demonstrated an even stronger result 60 years later, when the introduction of computers eliminated the necessity for laboriously testing every conceivable combination by hand.
In mathematics, once a theorem is established, it established forever. Therefore, it may come as a surprise to read that a new work, which is now available as a preprint and has submitted to the journal Physical Review Letters, has supposedly discovered a solution. Only one condition applies: the cops must be in a state of quantum entanglement. “I think their study is quite beautiful,” non-participating quantum physicist Gemma De las Cuevas told Quanta Magazine. “There’s a lot of quantum wizardry in there,” says the narrator. Not only that, but you can sense [the writers’] passion for the topic throughout the work.”
Let us start with a famous example to clarify what is going on. Euler’s “36 Officers” problem is a specific form of magic square known as an “orthogonal Latin square” — think of it as two sudoku puzzles in the same grid to solve at the same time. A four-by-four orthogonal Latin square, for example, would look like this: Euler’s original six-by-six issue is impossible to solve with each square in the grid defined in this way — with a fixed number and a fixed color. Things are more flexible in the quantum world, where things exist in superpositions of states.
In nonprofessional’s terms – or as non-technical language as quantum physics allows – this means that any given general can be various ranks of numerous regiments at the same time. We could envisage a square in the grid filled with, say, a superposition of a green two and a red one, using our colorful double-sudoku example. Euler’s dilemma, the researchers reasoned, would now have a solution. However, what was it, exactly?
At first sight, it appears as if the crew has made their task much more difficult. They had to solve six-by-six double sudoku that was known to be impossible in a traditional environment, but they also had to complete it in multiple dimensions at the same time. Fortunately, they had a couple of things working in their favor: first, a classical near-solution that they could use as a starting point, and second, quantum entanglement, which appears to be a puzzling phenomenon.
Simply put, when one state informs you about the other, they said to intertwine. Consider the following scenario: you know your friend has two children of the same gender, A and B (your friend is not good with names). That example, knowing that child A is a girl ensures that child B is a female as well – the two children’s genders are inextricably linked. When one state tells you absolutely everything about the other, it has termed a maximally entangled (AME) state. Entanglement does not often work out this well, but when it does, it has called an maximally entangled (AME) state.
Another example is flipping coins: if Alice and Bob each flip a coin and Alice gets heads, Bob knows without seeing that he got tails, and vice versa if the coins are entangled. Surprisingly, the solution to the quantum officer problem has this quality – and this is where things get fascinating. As you can see, the example above works for two coins and three coins, but it is impossible for four coins. The writers realized that the 36 Officers problem is more like rolling entangled dice than flipping dice.