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. 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 (3×3, 4×4, and so on, assuming the appropriate number of officers) except for 2×2 and Euler’s case of 6×6. In 1900, the impossibility of a 6×6 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 6×6 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. (APS Physics)
The paper has been published in Physical Review Letters.
