Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

Puzzling on a quantum chessboard

10.07.2019

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.


On a "quantum chessboard" the queens puzzle may be solved comparatively easily.

University of Innsbruck

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," says 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, Lechner developed a quantum chessboard on which the queens puzzle could be solved experimentally with the help of quantum physics.

From atoms to chess queens

"An optical lattice of laser beams into which individual atoms are placed can be used as a chessboard," explains 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," says 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.

Quantum supremacy on the horizon

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," summarizes 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.

Wissenschaftliche Ansprechpartner:

Wolfgang Lechner
Department of Theoretical Physics
University of Innsbruck
phone: +43 512 507 52232
email: Wolfgang.Lechner@uibk.ac.at
web: https://www.uibk.ac.at/th-physik/quantum-optimization/

Helmut Ritsch
Department of Theoretical Physics
University of Innsbruck
phone: +43 512 507 52213
email: Helmut.Ritsch@uibk.ac.at
web: https://www.uibk.ac.at/th-physik/cqed/

Originalpublikation:

A Quantum N-Queens Solver. Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner. Quantum 3, 149 (2019) https://doi.org/10.22331/q-2019-06-03-149

Dr. Christian Flatz | Universität Innsbruck

More articles from Physics and Astronomy:

nachricht Flying Laptop satellite mission extended by two years - Successfully in orbit since July 14, 2017
16.07.2019 | Universität Stuttgart

nachricht Robert Alfano team identifies new 'Majorana Photons'
16.07.2019 | City College of New York

All articles from Physics and Astronomy >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Megakaryocytes act as „bouncers“ restraining cell migration in the bone marrow

Scientists at the University Würzburg and University Hospital of Würzburg found that megakaryocytes act as “bouncers” and thus modulate bone marrow niche properties and cell migration dynamics. The study was published in July in the Journal “Haematologica”.

Hematopoiesis is the process of forming blood cells, which occurs predominantly in the bone marrow. The bone marrow produces all types of blood cells: red...

Im Focus: Artificial neural network resolves puzzles from condensed matter physics: Which is the perfect quantum theory?

For some phenomena in quantum many-body physics several competing theories exist. But which of them describes a quantum phenomenon best? A team of researchers from the Technical University of Munich (TUM) and Harvard University in the United States has now successfully deployed artificial neural networks for image analysis of quantum systems.

Is that a dog or a cat? Such a classification is a prime example of machine learning: artificial neural networks can be trained to analyze images by looking...

Im Focus: Extremely hard yet metallically conductive: Bayreuth researchers develop novel material with high-tech prospects

An international research group led by scientists from the University of Bayreuth has produced a previously unknown material: Rhenium nitride pernitride. Thanks to combining properties that were previously considered incompatible, it looks set to become highly attractive for technological applications. Indeed, it is a super-hard metallic conductor that can withstand extremely high pressures like a diamond. A process now developed in Bayreuth opens up the possibility of producing rhenium nitride pernitride and other technologically interesting materials in sufficiently large quantity for their properties characterisation. The new findings are presented in "Nature Communications".

The possibility of finding a compound that was metallically conductive, super-hard, and ultra-incompressible was long considered unlikely in science. It was...

Im Focus: Modelling leads to the optimum size for platinum fuel cell catalysts: Activity of fuel cell catalysts doubled

An interdisciplinary research team at the Technical University of Munich (TUM) has built platinum nanoparticles for catalysis in fuel cells: The new size-optimized catalysts are twice as good as the best process commercially available today.

Fuel cells may well replace batteries as the power source for electric cars. They consume hydrogen, a gas which could be produced for example using surplus...

Im Focus: The secret of mushroom colors

Mushrooms: Darker fruiting bodies in cold climates

The fly agaric with its red hat is perhaps the most evocative of the diverse and variously colored mushroom species. Hitherto, the purpose of these colors was...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

2nd International Conference on UV LED Technologies & Applications – ICULTA 2020 | Call for Abstracts

24.06.2019 | Event News

SEMANTiCS 2019 brings together industry leaders and data scientists in Karlsruhe

29.04.2019 | Event News

Revered mathematicians and computer scientists converge with 200 young researchers in Heidelberg!

17.04.2019 | Event News

 
Latest News

Flying Laptop satellite mission extended by two years - Successfully in orbit since July 14, 2017

16.07.2019 | Physics and Astronomy

New safer, inexpensive way to propel small satellites

16.07.2019 | Power and Electrical Engineering

UCI electrical engineering team develops 'beyond 5G' wireless transceiver

16.07.2019 | Information Technology

VideoLinks
Science & Research
Overview of more VideoLinks >>>