Centuries-old 'impossible' math problem cracked using the strange physics of Schrödinger's cat

A math problem developed 243 years ago can be solved only by using quantum entanglement, new research finds. 

The mathematics problem is a bit like Sudoku on steroids. It's called Euler's officer problem, after Leonhard Euler, the mathematician who first proposed it in 1779. Here's the puzzle: You're commanding an army with six regiments. Each regiment contains six different officers of six different ranks. Can you arrange them in a 6-by-6 square without repeating a rank or regiment in any given row or column? 

Euler couldn't find such an arrangement, and later computations proved that there was no solution. In fact, a paper published in 1960 in the Canadian Journal of Mathematics used the newfound power of computers to show that 6 was the one number over 2 where no such arrangement existed. 

Now, though, researchers have found a new solution to Euler's problem. As Quanta Magazine's Daniel Garisto reported, a new study posted to the preprint database arXiv finds that you can arrange six regiments of six officers of six different ranks in a grid without repeating any rank or regiment more than once in any row or column … if the officers are in a state of quantum entanglement. 

The paper, which has been submitted for peer review at the journal Physical Review Letters, takes advantage of the fact that quantum objects can be in multiple possible states until they are measured. (Quantum entanglement was famously demonstrated by the Schrödinger's cat thought experiment, in which a cat is trapped in a box with radioactive poison; the cat is both dead and alive until you open the box.) 

In Euler's classic problem, each officer has a static regiment and rank. They might be a first lieutenant in the Red Regiment, for example, or a captain in the Blue Regiment. (Colors are sometimes used in visualizing the grids, to make it easier to identify the regiments.) 

But a quantum officer might occupy more than one regiment or rank at once. A single officer could be either a Red Regiment first lieutenant or a Blue Regiment captain; a Green Regiment major or Purple Regiment colonel. (Or, theoretically, any other combination.) 

The key to solving Euler's problem with this identity switcheroo is that the officers on the grid can be in a state of quantum entanglement. In entanglement, the state of one object informs the state of another. If Officer No. 1 is, in fact, a Red Regiment first lieutenant, Officer No. 2 must be a major in the Green Regiment, and vice versa.

Using brute-force computer power, the authors of the new paper, led by Adam Burchardt, a postdoctoral researcher at Jagiellonian University in Poland, proved that filling the grid with quantum officers made the solution possible. Surprisingly, the entanglement has its own pattern, study co-author Suhail Rather, a physicist at the Indian Institute of Technology Madras, told Quanta Magazine. Officers are only entangled with officers of ranks one step below or above them, while regiments are also only entangled with adjacent regiments. 

The results could have real impacts on quantum data storage, according to Quanta Magazine. Entangled states can be used in quantum computing to ensure that data is safe even in the case of an error — a process called quantum error correction. By entangling 36 quantum officers in a state of interdependent relationships, the researchers found what is called an absolutely maximally entangled state. Such states can be important for resilient data storage in quantum computing. 

You can read all about the impossible problem's solution in Quanta Magazine.

Originally published on Live Science.