# Quantum solution to an 18th century puzzle

(ORDO NEWS) — Euler’s 243-year-old mathematical puzzle, which is not known to have a classical solution, has been found to be solvable if objects arranged in a square grid exhibit quantum behavior. It consists in finding a way to arrange objects in a grid so that their properties are not repeated in any row or column.

A mathematical problem that does not have a classical solution turns out to be solvable using quantum rules. A sudoku-style mathematical puzzle, which is known to have no classical solution, turned out to be solvable if objects arranged in a square grid exhibit quantum behavior [1].

The problem, posed by the Swiss mathematician Leonhard Euler in 1779, is to find a way to arrange objects in a grid so that their properties do not repeat in any row or column.

A quantum solution can be useful for solving problems in the field of quantum information processing, for example, for creating error correction algorithms in quantum computing.

Euler envisioned a group of 36 army officers, six from each of six regiments, with each officer holding one of six different ranks. Is it possible to arrange them in the form of a square so that no regiment or rank is repeated in any row or column?

Solutions can be found for all squares (3×3, 4×4, and so on, given the appropriate number of officers), except for 2×2 and the 6×6 Euler case. In 1900, the impossibility of solving the 6 × 6 problem was proved by the French mathematician Gaston Tarry.

But Suhail Rather of the Indian Institute of Technology Madras (IITM), Adam Burchardt of the Jagiellonian University in Poland and their colleagues wondered if the problem could be solved if the objects were not classical, but quantum mechanical.

Then objects could be placed in combinations (superpositions) of different possible states: one officer could be, say, part colonel from the red regiment and part lieutenant from the blue regiment.

This quantum version requires a more precise definition of when two such states can be considered “different”. Quantum superpositions can be represented as vectors in the space of possible component states, and the team hypothesized that two superpositions are mutually exclusive if their vectors are perpendicular (orthogonal) to each other.

The researchers used a computer algorithm to find such quantum solutions to Euler’s “36 officers” problem. They started with a classic configuration that only had a few repetitions in rows and columns and tried to improve on it by adding superposition.

They found that a complete quantum solution to the 6×6 problem exists for a certain set of superposition states.

The superposition of two quantum objects often implies that they are entangled: their properties are interdependent and correlated. If, say, one quantum officer turns out (when tested) to be a colonel, then the other one, with whom he is confused, may turn out to be a lieutenant.

The quantum solution requires a complex set of entanglements between officers, reminiscent of the entanglements created between quantum bits (qubits) in quantum computing.

The researchers realized that their solution was closely related to the problem of quantum information processing, involving “absolutely maximally entangled” (AME) states, in which the correlation between any pair of entangled qubits in a group is as strong as it can be.

Such states are important for quantum error correction, where errors in a quantum computation must be identified and corrected without actually reading the states of the qubits. AME states are also important for quantum teleportation, where the quantum state of one particle in an entangled pair is recreated in another particle.

Qubits have two possible reading states, 0 and 1, but quantum objects can in principle have three (qutrits) or more states. Theorists have developed mathematical expressions for the AME states for groups of quantum objects of various sizes, but the AME state for four six-state objects (so-called quex objects, such as quantum dice) has proven difficult to achieve.

Rather and colleagues found that their quantum solution to the 6×6 Euler problem shows how four quantum dice can be entangled to also get this so-called AME(4,6) solution. The absence of the AME(4,6) state has puzzled theorists, but the solution requires an approach not previously considered. The result shows a new design principle for creating states with entangled particles,

Finding the AME(4,6) state solves “a problem that has been studied by several researchers over the past few years,” says quantum information theorist Barbara Kraus of the University of Innsbruck in Austria. Quantum technologist Hoi-Kwong Lo of the University of Toronto says the work is potentially meaningful.

“The argument looks plausible, and if the result is correct, I think it’s very important, with implications for quantum error correction.” But he admits that it is not intuitively easy to understand why the case of six states is so special, both for the Euler problem and for the AME states.

Online: