Thirty-six quantum officers are entangled

This paper demonstrates that while the classical problem of Euler's thirty-six officers has no solution for order six, a solution exists using entangled quantum Latin squares, whereas mutually orthogonal quantum Latin squares of order six are impossible without entanglement.

The Gist

Here is an explanation of the paper "Thirty-six quantum officers are entangled" using simple language and creative analogies.

The Big Picture: Euler's Impossible Puzzle

Imagine a game of Sudoku, but instead of numbers 1–9, you have 36 different "officers." In the 18th century, a famous mathematician named Leonhard Euler posed a challenge: Can you arrange 36 officers (6 ranks and 6 regiments) in a 6x6 grid so that:

1. Every row has one officer of each rank.
2. Every column has one officer of each regiment.
3. No two officers in the same row or column share the same rank and regiment combination.

For 200 years, mathematicians tried and failed. In 1900, a man named Tarry proved it was impossible. You simply cannot arrange these 36 officers without breaking the rules. It's like trying to fit a square peg in a round hole; the geometry just doesn't work.

The Quantum Twist: Entanglement

Fast forward to 2022. Physicists discovered that if you treat these officers not as solid objects, but as quantum particles that can be "entangled" (a spooky connection where particles share a state), the impossible puzzle suddenly becomes solvable.

Think of entanglement like a pair of magic dice. If you roll one in New York and the other in Tokyo, they always land on matching numbers, even though they are far apart. In the quantum version of the puzzle, the officers are "fuzzy" and linked. This allows them to occupy a state that classical objects cannot, solving the 36-officer problem.

The New Question: Can We Do It Without Magic?

The authors of this paper asked a follow-up question: Do we need that quantum magic (entanglement) to solve the puzzle?

In quantum physics, there are two types of states:

1. Entangled: The particles are linked in a complex, non-separable way (the "magic" solution).
2. Non-entangled (Classical): The particles act independently, like normal objects, even if they are described by quantum math.

The paper asks: Can we arrange 36 quantum officers in a 6x6 grid using only "non-entangled" states? In other words, can we solve the puzzle if we strip away the "spooky" connections and treat the officers more like normal, independent entities?

The Answer: No.

The authors prove that it is impossible.

If you try to solve the 36-officer puzzle using only non-entangled quantum states, you hit the exact same wall that Euler hit 200 years ago. The "quantum" nature of the officers isn't enough to save the day unless they are truly entangled.

How Did They Prove It? (The Detective Work)

To prove this, the authors used a mix of logic, graph theory, and computer power. Here is the analogy of their method:

1. The "Pattern" Detective
Imagine every officer is a card with a pattern of lights on it. Some cards have one light on, some have two, some have three. The rules of the game say that if two officers are in the same row or column, their light patterns must not overlap in a specific way.
The authors analyzed these "light patterns" (which they call unitary patterns). They showed that if you try to arrange them without entanglement, the patterns eventually force a contradiction. It's like trying to build a house of cards where the rules of physics say the cards must be sticky, but you are trying to build them with dry, non-sticky cards. Eventually, the structure collapses.

2. The "Twelve Castles" Analogy
The authors knew that in the classical world, there are exactly 12 different ways to arrange a 6x6 Latin square (the grid without the quantum stuff). They treated these 12 arrangements as 12 different "castles."
They then tried to build a "quantum partner" for each of these 12 castles. They wrote a computer program to check if a quantum grid could fit next to each castle without breaking the rules.

• Result: For 10 of the castles, the computer immediately said "No, it doesn't fit."
• The Tricky Two: For the remaining 2 castles, the computer couldn't decide immediately. So, the authors had to do deep manual math to prove that even for these two, a quantum partner is impossible.

3. The "Sub-square" Trap
They discovered that if a solution did exist, it would have to contain a smaller 3x3 "sub-square" inside it. They then proved that if you have this specific 3x3 sub-square, the math forces the officers to have "weights" (complexity levels) that contradict the rules of the game. It's a logical trap: the moment you assume a solution exists, you create a contradiction.

Why Does This Matter?

This paper is significant for a few reasons:

• It defines the boundary of Quantum Magic: It tells us exactly how much quantumness is needed to solve this problem. You can't just use "light" quantum effects; you need the full power of entanglement.
• It solves a long-standing mystery: For a while, people wondered if the quantum solution was just a fluke or if there was a simpler, non-entangled way to do it. This paper closes that door.
• It helps with future tech: Understanding these "Quantum Latin Squares" helps scientists design better quantum computers and secure communication systems (Quantum Key Distribution). Knowing what doesn't work is just as important as knowing what does.

The One Remaining Mystery

The paper leaves one door slightly open. They proved it's impossible for grids of size 4, 5, and 6. They also proved that for size 9, you can have a solution where one square is classical and the other is quantum.

The big open question now is: What about size 7?
Is it possible to solve the "49 officers" puzzle (7x7) with non-entangled quantum states? The authors suspect the answer is "No," but they haven't proven it yet. That is the next puzzle for the world's best mathematicians to solve.

Summary

• Euler's Puzzle: Impossible with normal objects.
• Quantum Solution: Possible with entangled objects.
• This Paper's Discovery: Impossible with non-entangled quantum objects.
• Conclusion: To solve the 36-officer problem, you absolutely need the "spooky" power of quantum entanglement. There is no halfway house.

Technical Summary

Here is a detailed technical summary of the paper "Thirty-six quantum officers are entangled" by Simeon Ball and Robin Simoens.

1. Problem Statement

The paper addresses the existence of Mutually Orthogonal Quantum Latin Squares (MOQLS) of order six.

• Classical Context: Euler's "36 Officers Problem" asks for a pair of orthogonal Latin squares of order 6. Tarry (1900) proved this is impossible.
• Quantum Context: In 2022, Rather et al. demonstrated that a "quantum solution" exists if entanglement is allowed (specifically, entangled quantum Latin squares equivalent to an Absolutely Maximally Entangled (AME) state of 4 parties and dimension 6).
• The Open Question: While entangled solutions exist, it was unknown whether non-entangled (classical or "genuinely quantum" but not entangled) pairs of orthogonal quantum Latin squares of order 6 exist.
• Main Goal: To prove that no pair of orthogonal quantum Latin squares of order 6 exists if entanglement is not allowed.

2. Definitions and Preliminaries

The authors establish rigorous definitions for the objects of study:

• Quantum Latin Square (QLS): An $n \times n$ matrix with entries in $\mathbb{C}^n$ where every row and column forms an orthonormal basis of $\mathbb{C}^n$.
• Orthogonality (Definition 2): Two QLSs $(\psi_{ij})$ and $(\phi_{ij})$ are orthogonal if the set of tensor products $\{\psi_{ij} \otimes \phi_{ij}\}$ forms an orthonormal basis of $\mathbb{C}^n \otimes \mathbb{C}^n$.
• Entangled vs. Non-Entangled:
  • A QLS is classical (or not genuinely quantum) if, up to isotopy, all entries are basis vectors $|k\rangle$.
  • The paper focuses on non-entangled pairs, which implies the entries do not form an AME state in the specific sense required for the "entangled officers" solution.
• Patterns: The authors utilize the concept of patterns (binary matrices indicating the support of vector entries) to analyze the structure of QLSs. They define rules for these patterns based on orthogonality and unitarity constraints.

3. Methodology

The proof employs a combination of combinatorial arguments, linear algebra, and graph theory, structured in several logical steps:

A. Reduction to Classical Cases

The authors first prove that if a pair of MOQLS(6) exists, one of them can be assumed to be classical.

• Lemma 13: If a QLS has no entries of weight $\ge 3$ (where weight is the number of non-zero components), it can be transformed into a classical Latin square without losing orthogonality with its partner.
• Lemmas 16–19: Through a detailed analysis of "unitary patterns," the authors show that if one square has an entry of weight 4 or 3, strict constraints are placed on the partner square. They prove that if a pair exists, at least one square must effectively behave classically (having only weight 1 entries) or be reducible to a classical form.
• Theorem 20: If 2 MOQLS(6) exist, then there exist 2 MOQLS(6) where one is classical.

B. Graph Theoretic Formulation

Once reduced to the case where one square ($\Psi$) is classical, the problem is translated into graph theory:

• Latin Square Graph: A graph where vertices are the $n^2$ cells, and edges connect cells in the same row, column, or with the same symbol.
• Orthogonal Representation: The existence of an orthogonal mate $\Phi$ is equivalent to finding an orthonormal representation of the complement of the Latin square graph in $\mathbb{C}^6$.
• Classification: There are exactly 12 non-paratopic (main classes) Latin squares of order 6. The authors must check if the complement of the graph for any of these 12 squares admits an orthonormal representation in $\mathbb{C}^6$.

C. Algorithmic Verification

• Algorithm 1 & 2: The authors developed a computational algorithm to test for the existence of orthonormal representations.
  • The algorithm iteratively adds edges to the graph based on orthogonality constraints (if a vertex is adjacent to two points on a projective line, it must be adjacent to the third).
  • It checks for cliques of size 7 (impossible in 6 dimensions) and checks for dependent sets of vectors in tripartite subgraphs.
• Results of Algorithm: For 10 of the 12 Latin squares, the algorithm returned False (no representation exists).
• Remaining Cases: Two cases yielded an inconclusive "True." However, both of these specific Latin squares contain a subsquare of order 3.

D. The Subsquare of Order 3

The final step involves proving that if a classical Latin square of order 6 contains a subsquare of order 3, it cannot have a quantum orthogonal mate.

• Lemma 23 & 24: If $\Psi$ is classical with a $3 \times 3$subsquare, the entries of the partner square$\Phi$ in the corresponding block must be distinct and satisfy specific orthogonality constraints.
• Lemma 25: By analyzing the weights of entries in the partner square, the authors prove that all entries in the relevant block must have a weight of at most 2.
• Theorem 26: Combining the weight constraints with the unitary pattern rules, the authors derive a contradiction. Specifically, they show that the required orthogonality conditions force the existence of entries with impossible weights or linear dependencies.

4. Key Results

1. Theorem 6 (Main Result): There does not exist a pair of orthogonal quantum Latin squares of order six.
   • This confirms that the "quantum solution" to Euler's 36 officers problem requires entanglement. Without entanglement, the problem remains unsolvable.
2. Theorem 11 & 12: For orders $n=4$ and $n=5$, any pair of MOQLS is necessarily classical.
3. Upper Bound: The paper reinforces that there are at most $n-1$ MOQLS of order $n$. If equality holds ($n-1$), they are classical and equivalent to a projective plane.

5. Significance and Implications

• Resolution of the "Quantum Officers" Problem: The paper clarifies the boundary between classical and quantum combinatorial designs. It proves that the existence of the AME(4,6) state found by Rather et al. is a strictly quantum phenomenon that cannot be mimicked by non-entangled quantum structures.
• Classification of MOQLS: The authors narrow down the open cases for the existence of non-classical MOQLS.
  • $n=2, 3$: Trivial/Impossible.
  • $n=4, 5, 6$: Proven to be impossible (non-classical pairs do not exist).
  • $n=7$: Remains the only open case. The paper poses the question: "Are 2 MOQLS(7) classical?"
• Methodological Contribution: The paper introduces a powerful framework combining unitary patterns, orthonormal graph representations, and computational verification to solve high-dimensional quantum combinatorial problems. This approach could be applied to other problems involving quantum designs and entanglement.
• Connection to Projective Planes: The work reinforces the deep link between the existence of $n-1$ MOQLS and the existence of projective planes of order $n$.

Conclusion

Ball and Simoens provide a definitive negative answer to the existence of non-entangled orthogonal quantum Latin squares of order 6. Their proof demonstrates that the "quantum advantage" in solving Euler's 36 officers problem is inextricably linked to the presence of entanglement, and that without it, the classical impossibility result holds firm even in the quantum formalism.