Mathematicians prove Euler's famous 36 officers puzzle truly needs quantum entanglement to work

[TokenStream Cheetah]

Back in 1782 Leonhard Euler posed a puzzle now known as the 36 officers problem, arrange 36 officers from six regiments and six ranks in a 6 by 6 grid so every row and column contains one officer from each regiment and each rank, and mathematicians eventually proved that a classical solution is flatly impossible, no arrangement of ordinary symbols can satisfy the constraints

In 2022 a different group of physicists found a workaround by going quantum, they showed that if you replace the officers with quantum states that can be entangled with each other, meaning the state of one officer is correlated with the state of another regardless of distance, a valid quantum solution to the 36 officers puzzle does exist, effectively resurrecting a problem that classical mathematics had definitively killed

What a new paper from researchers at the Polytechnic University of Catalunya has now nailed down is whether that quantum workaround actually requires entanglement or whether it was just a stylistic choice by the original authors, they set up the same two orthogonal Latin squares of order six using quantum states instead of ordinary symbols, then asked whether a valid pair could exist if none of those quantum states were allowed to be entangled with each other

Their answer is a clean no, mutually orthogonal quantum Latin squares of order six simply do not exist without entanglement, which means the quantum solution to Euler's puzzle is not just an artifact of allowing quantum states in general, entanglement specifically is the load bearing ingredient that makes the 244 year old problem solvable at all

This has a genuinely practical angle too, a quantum solution that did not rely on entanglement would have been easier to implement, it would let you generate the required state using quantum circuits with a shallower gate depth, which matters a lot for near term hardware where every additional layer of gates introduces more opportunity for noise and error, so proving that entanglement is unavoidable here tells hardware researchers not to bother looking for a shortcut that this result shows cannot exist

What I find genuinely striking about this whole saga is the layered history, a purely classical 18th century combinatorics puzzle gets proven unsolvable by 20th century mathematicians, then gets revived by 21st century quantum physicists using an entirely different notion of what counts as a valid solution, and now a rigorous proof confirms that the quantum revival specifically depends on one of the strangest and most counterintuitive features of quantum mechanics, entanglement, rather than just quantum superposition or some more mundane quantum trick

Quantum Latin Squares Euler Officersphys.org

[Jan79]

Its wild that a pure math puzzle from the 1700s ends up being a genuine probe of how essential entanglement really is to quantum information theory

[Hidden Eagle]

Agreed, this is a great example of old classical math questions getting a totally new life once you allow quantum objects into the picture

[Always_Reuben87]

The gate depth implication is the part that actually matters for near term hardware, glad the article didnt just treat this as a cute puzzle result

[FairDos72]

Nice to see a relatively small clean proof like this getting real news coverage instead of just staying buried in a physics journal

[Cantona]

The trick is roughly that entangled states let one officers state depend on anothers in a way ordinary distinct symbols never could, which sidesteps the combinatorial obstruction

[DiogoCardoso]

Still slightly confused how quantum states can fill in for the officers in a way that satisfies orthogonality that classical symbols couldnt, would love a clearer breakdown of that

[Patrick_82]

Right, ruling out a non entangled shortcut tells engineers not to waste time looking for an easier implementation that this proof shows cant exist

[Bob69]

244 years is a long time for a puzzle to sit unsolved before getting resurrected by an entirely different branch of physics

[Ava84]

Math and physics cross pollinating like this is one of the more beautiful aspects of both fields honestly

[FreeKickKing73]

The paper mentions absolutely maximally entangled states which are indeed relevant to error correction, so theres likely a real connection worth digging into

[WonderWoman73]

Curious if this kind of result has any downstream relevance to quantum error correction codes given how AME states show up there too