The classic puzzle: 36 officers, no classical solution
In the 18th century, Empress Catherine the Great of Russia posed a famous problem to Euler: can 36 officers — from 6 regiments with 6 ranks each — be arranged in a 6×6 grid so that every row and column contains no repeated rank and no repeated regiment?
Euler believed it was impossible. In 1900, Tarry rigorously proved by exhaustive enumeration that the puzzle truly has no solution in the classical world.
That conclusion stood for 122 years. In 2022, Rather et al. at Jagiellonian University discovered that if the problem is 'quantized,' a solution exists — using entangled quantum Latin squares.
In 2026, Simeon Ball (Ghent University, Belgium) and Robin Simoens (Universitat Politècnica de Catalunya, Spain) published *Thirty-six quantum officers are entangled* in Physical Review Letters (arXiv:2603.02334), proving that entanglement is precisely what makes the quantum solution work. Strip away the entanglement and the quantum Latin squares fail, hitting the same wall as the classical case.
Three key facts
- Classically unsolvable for 122 years → quantum solution found in 2022 → 2026 proof that the solution must rely on entanglement
- The work identifies a new class of Absolutely Maximally Entangled (AME) states — special quantum states that are important resources for quantum computing and quantum communication
- The proof combines mathematical reduction with computer search: 6×6 classical Latin squares fall into essentially 12 'families.' The authors programmatically tested each family for a quantum partner — 10 were directly ruled out, and the remaining 2 were refuted via a '3×3 subsquare trap' argument
- Traditional surface codes: 1 logical qubit ≈ hundreds to thousands of physical qubits (code distance 7–31)
- AME-encoded route: potentially an order-of-magnitude reduction (still a research goal, not an engineering result)
- Superposition alone: insufficient — no solution
- Superposition + entanglement: sufficient — solution found
- Superposition without entanglement: back to classical impossibility
Why this matters to the quantum computing industry
AME states are not ordinary quantum states. They are a maximally entangled resource in n-body systems — every subsystem is maximally entangled across all possible subsets. Three direct application areas:
1. Quantum error-correcting codes: AME states naturally serve as codewords for certain stabilizer codes, since maximum information is retained even when subsystems are lost 2. Quantum communication: AME states are core resources in secret sharing and quantum key distribution protocols 3. Quantum networks: multipartite entanglement acts as 'shared memory' between nodes in distributed quantum computing
This work is the first to link the construction of AME states to a concrete mathematical problem — giving researchers a new, provably viable construction path instead of heuristic search.
Next steps for fault-tolerant quantum computers
The real bottleneck for practical quantum computers is not qubit count but error rates and error-correction overhead. The mainstream route today is surface-code error correction — used by Google's Willow and the Zuchongzhi 3.2 processor from Pan Jianwei's team.
AME states offer a kind of built-in entanglement protection layer. Error-correcting codes built on AME states could, in principle, reduce dependence on auxiliary qubits:
A signal to watch over the next 12 months: whether IBM, Quantinuum, or Pan Jianwei's team mentions AME states in any published error-correction scheme. If so, the error-correction overhead curve may see a downturn around 2027–2028.
What this means for the boundary of quantum advantage
The paper has a second significance: it draws a precise boundary between the classical and quantum worlds. Within the quantum Latin square framework:
Why this is now being popularized
The 36 officers problem is inherently science-communication friendly — the narrative arc from Euler to Tarry to Rather to Simoens/Ball makes it easy to explain what quantum entanglement is actually good for.
Meanwhile, the engineering value of AME states is exactly what industry capital and research teams are watching in 2026 H2. Pan Jianwei's Zuchongzhi 3.2 has achieved 'below-threshold' surface-code operation at code distance 7; Google's Willow hit the same milestone first but via a 'DC-pulse qubit leakage suppression' route with less favorable scalability.
The AME discovery offers both Chinese and US error-correction roadmaps a possible alternative or complement — not a replacement for surface codes, but a way to reduce auxiliary-qubit overhead in specific architectures.
A concrete test to watch in the next 12 months: which quantum hardware vendor first builds AME states into the physical qubit layout of its next-generation processor (IBM Kookaburra, a Quantinuum Helios successor, or Google's next chip). That is the key litmus test for whether the quantum-advantage narrative moves toward engineering in 2027.