Science

A quantum solution to a 243-year-old maths problem

Entangled dice: The existence of a quantum solution to the 36 officers problem implies that 4 unbiased dice can be prepared so that observing any two of them can be used to perfectly predict the other two.

A famous problem that has perplexed mathematicians since 1779 has been settled, but with a quantum twist, by a collaboration of six Indian and Polish researchers, two of whom are from Indian Institute of Technology (IIT) Madras. The researchers have solved using matrix methods, the quantum equivalent of the classical problem. This could potentially be used in quantum secret sharing protocols – which will be useful when quantum computers come into play; parallel teleportation, which is a way to transferring information across distances; and even perhaps may come in useful in solving the problem of quantum gravity.

Long-lived puzzles

Numerical puzzles often appear simple when phrased but can occupy mathematicians for hundreds of years. The 36 officers puzzle was first posed by Swiss mathematician Leonhard Euler.

The puzzle can be described as follows:

There are six regiments, each containing six officers of six different ranks. The question is, can you place the 36 officers in a square arrangement with six rows and six columns such that no row or column repeats an officer’s rank or regiment?

This puzzle was guessed to be unsolvable by Euler in 1779 and proven to be so by the French amateur mathematician G. Tarry in 1901.

Euler was able to show that when you have odd number of rows and columns, as for example, 25 officers belonging to five regiments of five ranks each, the solution was easy to find. For the case of four officers, to be arranged in a two by two matrix, it was easily seen that no possible solution could be found. Euler himself believed solutions do not exist for those even numbers, n, which took the form n = 2+ 4k , for k taking values 1,2,3, etc. This was reinforced when Tarry showed that the case of n=6, the original problem of 36 officers had no solution. But two Indians, R.C. Bose and S.S. Shrikhande constructed solutions for n = 22, earning themselves the description “Euler spoilers”. Later these two mathematicians along with E. T. Parker proved that solutions exist for all n except for two and six.

Squares such as this are often encountered in Sudoku and other magic squares of size n. Euler’s 36 officers problem (for which n=6) and generalisations of it to other values of n = 2,3, etc are examples of Orthogonal Latin Squares (OLS). In this case, OLS solutions exist for all values of n except 2 and 6.

A quantum solution

Now Tarry had explicitly shown that n = 6 (36 officers puzzle) has no solution. But suppose the officers were not classical objects but were quantum entities, would this still be true? This is what physicists who joined the group of problem solvers started asking.

Classically, this problem cannot be solved, but what if the officers were quantum entities?

Here, it is necessary to understand “quantum entanglement”.

To get an idea, take 2 boxes, one in Chennai and other in Shopian, one containing a red (R) cube and other a blue (B) one. We think of the state as RB or BR depending on if the Chennai box contains a red or blue cube. A quantum entangled state, is a weird “superposition” of these two which physicists represent by RB+BR. The strange thing about this state is that opening the Chennai box can randomly reveal it to contain a blue or red cube and the nature of entanglement is to ensure that the other distant box contains a cube of the opposite colour. Repeating the experiment with an identical set of boxes, can result in the reverse colours immediately. This leads to what is popularly known as ``spooky action at a distance”, and maximal entanglement leads to perfect correlation.

Another famous example is that of Schrodinger’s cat. A locker with a cat and a vial of poison, the state of the broken vial and a dead cat is superposed with an unbroken vial and a live cat in one entangled quantum state. Only when the locker is opened, the state collapses randomly into a state where the cat is dead or alive, and the vial of poison, broken or whole. The unopened locker is in a quantum state where dead and alive coexist uneasily!

Officers entangled

In the case of quantum officers, the state may similarly exist in a superposition of officer states. One of the things the researchers have shown is that there is a connection between the classical OLS solutions, whenever it exists, and the nature of the quantum state associated with it. It can be used to construct what are called Absolutely Maximally Entangled (AME) states. These are states in which any subset of the entities is maximally correlated with the others in the sense of the red and blue cubes above.

In the case Euler’s problem, starting from the quantum equivalent of what is nearly an OLS solution, the researchers run an algorithm that tunes it and tries to approach the perfect AME state which will be the quantum OLS in the forbidden dimension n=6. “Given that we were studying a 36-dimensional matrix, which contained 1,296 entries, it was like looking for a needle in a haystack,” says Arul Lakshminarayan from IIT Madras, who led the study along with Karol Zyczkowski of Jagiellonian University, Krakow, Poland. It is an interesting fact that JU, Krakow counts among its alumni, the legendary Copernicus. “When we found the state, there were some people who lost money, for they were betting that such a state does not exist,” he quips. Four other researchers who were involved in the work include Suhail Ahmad Rather from India and Adam Burchardt, Wojciech Bruzda and Grzegorz Rajchel-Mieldzioc from Poland.

“When we ran the algorithm, we realized that we should not start from the neighbourhood of the approximate solution but somewhat away from it,” says Suhail Ahmad Rather, who is a PhD student in his fourth year at IIT Madras and one of the first authors of the paper which has been accepted for publication in Physical Review Letters. “There is an art involved in it,” says Prof. Lakshminarayan. “One should imagine a complex landscape of valleys, passes and peaks in 1296 dimensions. We wanted to reach the peak, but were seemingly getting stuck in shallow valleys, but more importantly we did not even know if there was a peak”

An amusing twist to the story comes in when you consider the three amplitudes a, b and c, that made up the solution. The three form a Pythagorean triad, that is, a2 + b2 = c2. Further the ratio b/a was the golden mean (approximately equal to 1.618) which is seen in many natural and constructed patterns. Is there then something more to the story? Is this, as Prof. Lakshminarayan feels, the tip of an iceberg?