A classically intractable problem that asks for a 6-by-6 arrangement of military officers can be solved, so long as the officers are quantum.
n 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 ranks greater than two, except, curiously, six.
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.
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.
Samuel Velasco/Quanta Magazine
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 then-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 the 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.
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 the 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’s 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 analogue. 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.
Correction: January 10, 2022
This article originally identified Suhail Rather as a mathematician, when in fact he is a physicist.
Editor’s note: The author of this article is related to an editor at Physical Review Letters, where the quantum Latin squares paper has been submitted for publication. The two have not discussed the paper.
Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution
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.
https://www.thespaceacademy.org/2022/01/eulers-243-year-old-impossible-puzzle.html?fbclid=IwAR0Ghyc2-0f_g6i8Q7iDacDicKA2ScXfRWDQ8vt-fLyHMl57yX0ME0Q8WF4