A Quantum Solution to an 18th-Century Puzzle
A sudoku-style mathematical puzzle that is known to have no classical solution has been found to be soluble if the objects being arrayed in a square grid show quantum behavior [1]. The problem, posed by Swiss mathematician Leonard Euler in 1779, involves finding a way to arrange objects in a grid so that their properties don’t repeat in any row or column. The quantum solution might be useful for problems in quantum information processing, such as creating algorithms for correcting errors in quantum computing.
Euler imagined a group of 36 army officers, six from each of six regiments, with each officer having one of six different ranks. Can they be arranged in a square formation such that no regiment or rank is repeated in any row or column?
Solutions can be found for all squares ( , , and so on, assuming the appropriate number of officers) except for and Euler’s case of . In 1900, the impossibility of a solution was proven by the French mathematician Gaston Tarry. But Suhail Rather of the Indian Institute of Technology Madras (IITM), Adam Burchardt of Jagiellonian University in Poland, and their colleagues wondered if the problem could be solved if the objects were quantum mechanical instead of classical. Then the objects could be placed in combinations (superpositions) of the various possible states: a single officer could be, say, partially a colonel from the red regiment and partially a lieutenant from the blue regiment.
This quantum version requires an adjusted definition of when two such states can be considered “different.” Quantum superpositions can be represented as vectors in the space of possible states of the components, and the team assumed that two superpositions are mutually exclusive if their vectors are perpendicular (orthogonal) to one another.
The researchers used a computer algorithm to search for such quantum solutions of Euler’s “36 officers” problem. They started from a classical configuration that had only a few repetitions in the rows and columns and tried to improve it by adding in superposition. They found that a full quantum solution to the problem exists for a particular set of superposition states.
A superposition between two quantum objects often implies that they are entangled: their properties are interdependent and correlated. If, say, one quantum officer is found (on inspection) to be a colonel, the other with which it is entangled might have to be a lieutenant. The quantum solution requires a complicated set of entanglements between officers, reminiscent of the entanglements created between quantum bits (qubits) in quantum computing.
The researchers realized that their solution is closely related to a problem in quantum information processing involving “absolutely maximally entangled” (AME) states, in which the correlation between any pair of entangled qubits in the group is as strong as it can possibly be. Such states are relevant to quantum error correction, where errors in a quantum computation must be identified and corrected without actually reading out the states of the qubits. AME states are also important in quantum teleportation, where the quantum state of one particle in an entangled pair is recreated in the other particle.
Qubits have two possible readout states, 0 and 1, but quantum objects can, in principle, also have three (qutrits) or more states. Theorists have derived mathematical expressions for AME states for different-sized groups of quantum objects, but an AME state for four six-state objects (so-called quhex objects, like quantum dice) has proven curiously elusive. Rather and colleagues found that their quantum solution to the Euler problem shows how to entangle four quantum dice to also produce this so-called AME(4,6) solution. The lack of an AME(4,6) state had been puzzling to theorists, but the solution required an approach that had not been previously considered. The result shows a new design principle for creating states with entangled particles, an essential element of error-correcting codes, says team member Arul Lakshminarayan of the IITM.
Finding the AME(4,6) state solves “a problem that has been investigated by several researchers within the last 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 significant. “The argument looks plausible to me, and if the result is correct, I think it is very important, with implications for quantum error correction.” But he admits that it’s not easy to understand intuitively why the six-state case turns out to be so special, both for Euler’s problem and for the AME states.
–Philip Ball
Philip Ball is a freelance science writer in London. His latest book is How Life Works (Picador, 2024).
References
- S. A. Rather et al., “Thirty-six entangled officers of Euler: Quantum solution to a classically impossible problem,” Phys. Rev. Lett. 128, 080507 (2022).