Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution

Mar 14, 2022 | Location Clayton Ladue

Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution

A surprising new solution to Leonhard Euler’s famous “36 officers puzzle” offers a novel way of encoding quantum information.


January 10, 2022

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 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.

In a five-by-five grid, chess pieces of five different ranks and five different colors are arranged such that no row or column repeats a rank or color.

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.

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 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.

Locations near
me
Ashburn 0.93 mi
43330 Junction Plaza
#160
Ashburn, VA 20147
Sterling 4.07 mi
44 Pidgeon Hill Drive
#100
Sterling, VA 20165
Leesburg 5.69 mi
521 E Market St
#B
Leesburg, VA 20176
Herndon 7.66 mi
2465 Centreville Road
#J2
Herndon, VA 20171
Stone Ridge 7.88 mi
42020 Village Center Plaza
#100
Stone Ridge, VA 20105
Reston 8.62 mi
1424 North Point Village Center
Reston, VA 20194
Purcellville 12.72 mi
1020 E Main St
Ste L
Purcellville, VA 20132
North Potomac 13.58 mi
12150 Darnestown Rd
Gaithersburg, MD 20878
Centreville 14.52 mi
5959 Centreville Crest Ln
Centreville, VA 20121
Fairfax 14.67 mi
11891 Grand Commons Ave
Fairfax, VA 22030
Potomac 14.98 mi
10232 River Road
#B
Potomac, MD 20854
Germantown MD 15.03 mi
12800 Middlebrook Road
Germantown, MD 20874
Tysons 15.45 mi
328 Maple Ave E
#A
Vienna, VA 22180
Haymarket 17.87 mi
15125 Washington St
Haymarket, VA 20169
Rockville 18.19 mi
20 Courthouse Square
#106
Rockville, MD 20850
Mclean 18.23 mi
1320 Old Chain Bridge Road
Suite #190
McLean, VA 22101
Gaithersburg 18.71 mi
9132 Rothbury Drive
Gaithersburg, MD 20886
North Bethesda 20.42 mi
5268 Nicholson Ln
#N
Kensington, MD 20895
Falls Church 20.59 mi
6674 Arlington Blvd
Falls Church, VA 22042
Manassas 20.65 mi
9722 Liberia Ave
Manassas, VA 20110
Bristow 20.71 mi
12705 Braemar Village Pz
Bristow, VA 20136
Burke 20.82 mi
9411 Old Burke Lake Rd
#C
Burke, VA 22015
Bethesda 21.3 mi
4918 Fairmont Ave
Bethesda, MD 20814
Annandale 21.64 mi
7000 Columbia Pike
Annandale, VA 22003
Damascus 22.77 mi
9815 Main St
Damascus, MD 20872
Arlington, VA 23.29 mi
4801 1st St N
Arlington, VA 22203
Cathedral Heights 23.51 mi
3706 Macomb St NW
Washington, D.C., DC 20016
Olney 23.96 mi
18157 Village Center Dr
Olney, MD 20832
Downtown Silver Spring 24.94 mi
1133 East West Highway
Silver Spring, MD 20910
Lorton 25.06 mi
9027 Silverbrook Rd
#A
Fairfax Station, VA 22039
West Washington 25.69 mi

Washington, DC 20009
Alexandria City 25.7 mi
4605 Duke Street
Alexandria, VA 22304
Lake Ridge 26.5 mi
12473 Dillingham Square
Lake Ridge, VA 22192
Frederick North 26.7 mi
905 W. 7th Street
Frederick, MD 21701
Northern Silver Spring 26.75 mi
732 Cloverly Street
Silver Spring, MD 20905
Alexandria 27.17 mi
6483 Old Beulah Street
Alexandria, VA 22315
Warrenton 27.42 mi
512 Fletcher Drive
Warrenton, VA 20186
Mount Airy 28.24 mi
411 E Ridgeville Blvd
Mt Airy, MD 21771
Capitol Hill DC 28.48 mi
621 Pennsylvania Ave SE
1st-floor unit
Washington, DC 20003
Dale City 28.99 mi
5512 Staples Mill Plaza
Dale City, VA 22193
Mount Vernon 29.66 mi
7696 H Richmond Hwy
Alexandria, VA 22306
Beltsville 30.89 mi
10914 Baltimore Ave
#B
Beltsville, MD 20705
Clarksville 31.56 mi
12250 Clarksville Pike
#D
Clarksville, MD 21029
Laurel 35.02 mi
10095 Washington Blvd N
#136
Laurel, MD 20723
Woodmore 35.27 mi
9101 Woodmore Centre Drive
Lanham, MD 20706
Glenn Dale 35.83 mi
10559 Greenbelt Rd
Lanham, MD 20706
Sykesville 36.57 mi
1207 Liberty Rd.
#D-104
Sykesville, MD 21784
Ellicott City 37.11 mi
3290 Pine Orchard Lane
#B
Ellicott City, MD 21042
Winchester 37.62 mi
2512 S Pleasant Valley Rd
Winchester, VA 22601
Columbia 38.19 mi
8827 Centre Park Drive
#F
Columbia, MD 21045
Stafford 39.58 mi
263 Garrisonville Road
#104
Stafford, VA 22554
Bowie 41.26 mi
15231 Hall Rd
Bowie, MD 20721
Waldorf 42.24 mi
3022 Festival Way
Waldorf, MD 20601
Crofton 42.6 mi
1153 Route 3 North
#120
Crofton, MD 21054
Owings Mills 44.15 mi
9433 Common Brook Rd #100
Owings Mills, MD 21117
Pikesville 46.84 mi
1433 Reisterstown Rd
Pikesville, MD 21208
Dunkirk 49.92 mi
10735 Town Center Blvd
#7
Dunkirk, MD 20754
Severna Park 50.52 mi
558 Ritchie Highway
#D
Severna Park, MD 21146
Roland Park 50.62 mi
600 Wyndhurst Ave
Baltimore, MD 21210
Annapolis 50.75 mi
2341 N Forest Drive
Annapolis, MD 21401
Chancellor 52.23 mi
4300 Plank Rd.
#210
Fredericksburg, VA 22407
Perry Hall 59.13 mi
4136 E Joppa Rd
#J
Nottingham, MD 21236
Bel Air 69.23 mi
516 Baltimore Pike
Bel Air, MD 21014