IN 1779, THE Swiss mathematician Leonhard Euler posed a puzzle that has since become famous: Six army regiments each have six officers of six different ranks. Can the 36 officers be arranged in a 6-by-6 square so that no row or column repeats a rank or regiment?
The
puzzle is easily solved when there are five ranks and five regiments, or seven
ranks and seven regiments. But after searching in vain for a solution for the
case of 36 officers, Euler concluded that “such an arrangement is impossible,
though we can’t give a rigorous demonstration of this.” More than a century
later, the French mathematician Gaston Tarry proved that, indeed, there was no
way to arrange Euler’s 36 officers in a 6-by-6 square without repetition. In
1960, mathematicians used computers to prove that solutions exist for any number of regiments
and rank greater than two, except, curiously, six.
A five-by-five grid can be filled with chess pieces of five different ranks and five different colors such that no row or column repeats a rank or color.
ILLUSTRATION: SAMUEL VELASCO/QUANTA MAGAZINE
Similar
puzzles have entranced people for more than 2,000 years. Cultures around the
world have made “magic squares,” arrays of numbers that add to the same sum
along each row and column, and “Latin squares” filled with symbols that each
appear once per row and column. These squares have been used in art and urban
planning, and just for fun. One popular Latin square—Sudoku—has subsquares that
also lack repeating symbols. Euler’s 36 officers puzzle asks for an “orthogonal
Latin square,” in which two sets of properties, such as ranks and regiments,
both satisfy the rules of the Latin square simultaneously.
But
whereas Euler thought no such 6-by-6 square exists, recently the game has
changed. In a
paper posted online and submitted to Physical Review Letters,
a group of quantum physicists in India and Poland demonstrates that it is
possible to arrange 36 officers in a way that fulfills Euler’s criteria—so long
as the officers can have a quantum mixture of ranks and regiments. The result
is the latest in a line of work developing quantum versions of magic square and
Latin square puzzles, which is not just fun and games but has applications for
quantum communication and quantum computing.
“I think their paper is very beautiful,” said Gemma De las Cuevas, a quantum physicist at the University of Innsbruck who was not involved with the work. “There’s a lot of quantum magic in there. And not only that, but you can feel throughout the paper their love for the problem.”
The
new era of quantum puzzling began in 2016 when Jamie Vicary of
the University of Cambridge and his student Ben Musto had the idea that the
entries appearing in Latin squares could be made quantum.
In
quantum mechanics, objects such as electrons can be in a “superposition” of
multiple possible states: here and there, for example, or magnetically oriented
both up and down. (Quantum objects stay in this limbo until they are measured,
at which point they settle on one state.) Entries of quantum Latin squares are
also quantum states that can be in quantum superpositions. Mathematically, a
quantum state is represented by a vector, which has a length and direction,
like an arrow. A superposition is an arrow formed by combining multiple
vectors. Analogous to the requirement that symbols along each row and column of
a Latin square not repeat, the quantum states along each row or column of a
quantum Latin square must correspond to vectors that are perpendicular to one
another.
Quantum
Latin squares were quickly adopted by a community of theoretical physicists and
mathematicians interested in their unusual properties. Last year, the French
mathematical physicists Ion Nechita and Jordi Pillet created a quantum version
of Sudoku—SudoQ.
Instead of using the integers 0 through 9, in SudoQ the rows, columns, and
subsquares each have nine perpendicular vectors.
These
advances led Adam Burchardt, a postdoctoral researcher at Jagiellonian
University in Poland, and his colleagues to reexamine Euler’s old puzzle about
the 36 officers. What if, they wondered, Euler’s officers were made quantum?
In
the classical version of the problem, each entry is an officer with a
well-defined rank and regiment. It’s helpful to conceive of the 36 officers as
colorful chess pieces, whose rank can be king, queen, rook, bishop,
knight, or pawn, and whose regiment is represented by red, orange, yellow,
green, blue, or purple. But in the quantum version, officers are formed from
superpositions of ranks and regiments. An officer could be a superposition of a
red king and an orange queen, for instance.
Critically,
the quantum states that compose these officers have a special relationship
called entanglement, which involves a correlation between different entities.
If a red king is entangled with an orange queen, for instance, then even if the
king and queen are both in superpositions of multiple regiments, observing that
the king is red tells you immediately that the queen is orange. It’s because of
the peculiar nature of entanglement that officers along each line can all be
perpendicular.
The
theory seemed to work, but to prove it, the authors had to construct a 6-by-6
array filled with quantum officers. A vast number of possible configurations
and entanglements meant they had to rely on computer help. The researchers
plugged in a classical near-solution (an arrangement of 36 classical officers
with only a few repeats of ranks and regiments in a row or column) and applied
an algorithm that tweaked the arrangement toward a true quantum solution. The
algorithm works a little like solving a Rubik’s Cube with brute force, where
you fix the first row, then the first column, second column, and so on. When
they repeated the algorithm over and over, the puzzle array cycled closer and
closer to being a true solution. Eventually, the researchers reached a point
where they could see the pattern and fill in the few remaining entries by hand. Euler was, in a sense,
proved wrong—though he couldn’t have known, in the 18th century, about the
possibility of quantum officers.
“They close the book on this problem, which is already very nice,” said Nechita. “It’s a very beautiful result, and I like the way they obtain it.”
One
surprising feature of their solution, according to coauthor Suhail Rather, a
physicist at the Indian Institute of Technology Madras in Chennai, was that
officer ranks are entangled only with adjacent ranks (kings with queens, rooks
with bishops, knights with pawns) and regiments with adjacent regiments.
Another surprise was the coefficients that appear in the entries of the quantum
Latin square. These coefficients are numbers that tell you, essentially, how
much weight to give different terms in a superposition. Curiously, the ratio of
the coefficients that the algorithm landed on was Φ, or 1.618…, the famous
golden ratio.
The
solution is also what’s known as an “absolutely maximally entangled state”
(AME), an arrangement of quantum objects that are thought to be important for a
number of applications, including quantum error-correction—ways of redundantly
storing information in quantum computers so that it survives even if there’s
data corruption. In an AME, correlations between measurements of quantum
objects are as strong as they can be: If Alice and Bob have entangled coins,
and Alice tosses her coin and gets heads, she knows for sure that Bob has
tails and vice versa. Two coins can be maximally entangled, and so can three,
but not four: If Carol and Dave join the coin toss, Alice can never be sure
what Bob gets.
The
new research proves, however, that if you have a set of four entangled dice,
rather than coins, these can be maximally entangled. The arrangement of the
six-sided dice is equivalent to the 6-by-6 quantum Latin square. Because of the
golden ratio’s presence in their solution, the researchers have dubbed this a “golden
AME.”
“I think it’s highly nontrivial,” said De las Cuevas. “Not only that it exists, but they provide the state explicitly and analyze it.”
Researchers have previously devised other AMEs by starting with classical error-correcting codes and finding analogous, quantum versions. But the newfound golden AME is different, with no classical cryptographic analog. Burchardt suspects it could be the first of a new class of quantum error-correcting codes. Then again, it might be equally interesting if the golden AME remains unique.