5 Jul 2019 Innsbruck - *
Physicists at the University of Innsbruck are proposing a new model that could demonstrate the supremacy of quantum computers over classical supercomputers in solving optimization problems. In a recent paper, they demonstrate that just a few quantum particles would be sufficient to solve the mathematically difficult N-queens problem in chess even for large chess boards.
*

The queen problem is a mathematical task, which already had the great mathematician Carl Friedrich Gauss occupied, but for which he surprisingly did not find the right solution. The challenge here is how to arrange eight queens on a classical chess board with 8 x 8 squares so that no two queens threaten each other.

Mathematically, it is relatively easy to determine that there are 92 different ways to arrange the queens. On a chess board with 25 x 25 squares there are already more than 2 billion possibilities. The calculation of this number alone took a total of 53 years of CPU time.

The task becomes even more difficult if some queens are already on the field and certain diagonals may not be occupied. Recently it has been shown that with these additional restrictions the problem with 21 queens can no longer be solved by classical mathematical algorithms in a reasonable time.

"I came across this topic by chance and thought that quantum physics really could play out its advantages here", stated Wolfgang Lechner from the Department of Theoretical Physics at the University of Innsbruck and the Institute of Quantum Optics and Quantum Information at the Austrian Academy of Sciences. Together with Helmut Ritsch and the PhD students Valentin Torggler and Philipp Aumann, Wolfgang Lechner developed a quantum chessboard on which the queens puzzle could be solved experimentally with the help of quantum physics.

"An optical lattice of laser beams into which individual atoms are placed can be used as a chessboard", explained Helmut Ritsch, who is also a member of the Department of Theoretical Physics in Innsbruck. "By adjusting the interaction between the atoms, we can make chess queens out of the atoms, who behave according to the chess rules, i.e. avoid each other in all directions of the game board." This repulsion of the particles is generated with the help of lasers, which are applied along the directions of motion. Via an optical resonator - two mirrors above and below the optical lattice - this interaction is further intensified and becomes thus effective over much greater distances.

"One could also play this game with correspondingly repulsive billiard balls", stated Helmut Ritsch. "But because there are so many possibilities, it would take a very, very long time. It is therefore crucial that the atoms are cooled down very strongly and that their quantum properties take effect. Because they then behave like waves and can test many possibilities at the same time. Then it quickly becomes apparent whether there is a valid solution according to chess rules for the given conditions."

The answer to the question whether there is a solution under the given restrictions can be read very easily from the light emitted by the resonator. But the specific arrangement of the atomic queens could only be determined by atomic microscopy, a method recently successfully applied by related experiments.

Simulations on classical computers strongly suggest that the experiment designed by the Innsbruck theorists would lead to a result much faster than any mathematical algorithm on a classical computer could.

"This would allow for the first time to clearly prove the supremacy of quantum computers for the calculation of certain optimization problems", summarized Wolfgang Lechner. "The control of a few dozen atoms is already standard practice in the laboratory, which is why the implementation of this idea might soon become reality."

The work was published in the journal*Quantum*and was financially supported by the Austrian Science Fund FWF, the Hauser-Raspe Foundation and the European Union.

Puzzling on a quantum chessboard ...

Simulating quantum systems with neural networks ...

Quantum - widening the net ...

Sigma-i and D-Wave announce largest-ever quantum Cloud-access contract ...

Rigetti Computing awarded as Technology Pioneer by World Economic Forum ...

Accenture awarded second U.S. patent for quantum computing ...

Generation and sampling of quantum states of light in a silicon chip ...

Spring 2019 edition of the e-IRG Magazine available ...

NEC server software enables advanced and secure login to websites in compliance with FIDO2 ...

'Tsunami' on a silicon chip: a world first for light waves ...

Atos and GENCI announce winners of Atos Joseph Fourier Award 2019 ...

Baidu named development partner on Intel Nervana Neural Network Processor for Training ...

Using artificial intelligence to better predict severe weather ...

Using machine learning models to better predict bladder cancer stages ...

A data-driven journey to the center of the earth ...

Researchers cast neural nets to simulate molecular motion ...

Theoretical physicists unveil one of the most ubiquitous and elusive concepts in chemistry ...

SDSC's Sherlock division debuts Innovation Accelerator Platforms ...