Euler's 36 officers need entanglement, not just quantum notation

Robin Simoens and Simeon Ball of the Polytechnic University of Catalunya have proved that a quantum version of Euler's 36 officers problem has no solution unless the quantum states filling the grid are entangled, in a paper published in Physical Review Letters ^[2]. The result matters because it separates two things routinely conflated in quantum advantage arguments: restating a problem in quantum language, and actually paying for a quantum resource ^[5][3].

The original question is old. In 1782 Leonhard Euler asked for 36 officers from six regiments and six ranks to be placed in a 6-by-6 grid so that every row and every column contained one officer of each regiment and each rank ^[1]. Mathematicians later established that no classical arrangement works ^[6]; Simoens frames the new theorem as the quantum counterpart of Tarry's proof that two mutually orthogonal Latin squares of order six do not exist ^[7]. Latin squares themselves are not academic curiosities: they underpin experimental design, cryptographic constructions and other combinatorial structures, and have been studied for more than three centuries ^[4].

The quantum reformulation replaces each symbol with a mathematical description of a quantum state ^[5]. According to Simoens, the recent quantum solution by Rather et al. works only because the ranks of the officers take several values at once in a way that makes them depend on each other, which is entanglement ^[8]. He describes the question his team asked as whether a simpler in-between solution exists, comparable to a sudoku in which you may write several numbers in one cell but nothing more exotic ^[9].

There was a concrete reason to want that weaker version. An entanglement-free quantum solution would allow the corresponding state to be prepared by circuits with lower gate depth ^[10]. Since no such solution exists, that cheaper preparation route is closed, and any circuit producing the state has to carry the entangling structure ^[11].

The proof is combinatorial rather than physical ^[12]. The authors took two 6-by-6 Latin squares over six symbols, required them to be orthogonal so that superimposing them yields every ordered pair exactly once, and replaced the symbols with quantum states written as vectors in a state space ^[13]. Simoens says the hardest step was showing that one of the two quantum Latin squares can be assumed classical, which he likens to solving a very hard sudoku ^[14]. The remainder reduced to a graph theory question, whether a Latin square graph admits an orthonormal representation, and a computer algorithm showed it does not ^[15].

Simoens describes this as the last open case for product-orthogonal quantum Latin squares, which were already known to exist in every dimension except six ^[16]. Taken with the new nonexistence result, six is now the sole dimension in which such pairs fail, in the quantum regime as well as the classical one ^[17].

Two things are worth watching. The final step rests on a computer search, so independent reimplementation of that algorithm is the obvious check on the result ^[15]. The second is whether the reduction technique, assuming one square classical and then asking for orthonormal representations of the associated graph, generalises to other quantum designs where entanglement-free constructions are currently assumed rather than ruled out ^[14][15].