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.

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.

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/

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

**Further reports about:**
> Puzzling
> QUANTUM
> classical computer
> individual atoms
> laser beams
> mathematical algorithms
> optical lattice
> optical resonator
> quantum computers
> quantum properties

A cavity leads to a strong interaction between light and matter

21.10.2019 | Universität Basel

A new stable form of plutonium discovered at the ESRF

21.10.2019 | European Synchrotron Radiation Facility

A very special kind of light is emitted by tungsten diselenide layers. The reason for this has been unclear. Now an explanation has been found at TU Wien (Vienna)

It is an exotic phenomenon that nobody was able to explain for years: when energy is supplied to a thin layer of the material tungsten diselenide, it begins to...

Researchers at Ludwig-Maximilians-Universitaet (LMU) in Munich have explored the initial consequences of the interaction of light with molecules on the surface of nanoscopic aerosols.

The nanocosmos is constantly in motion. All natural processes are ultimately determined by the interplay between radiation and matter. Light strikes particles...

Particles that are mere nanometers in size are at the forefront of scientific research today. They come in many different shapes: rods, spheres, cubes, vesicles, S-shaped worms and even donut-like rings. What makes them worthy of scientific study is that, being so tiny, they exhibit quantum mechanical properties not possible with larger objects.

Researchers at the Center for Nanoscale Materials (CNM), a U.S. Department of Energy (DOE) Office of Science User Facility located at DOE's Argonne National...

A new research project at the TH Mittelhessen focusses on the development of a novel light weight design concept for leisure boats and yachts. Professor Stephan Marzi from the THM Institute of Mechanics and Materials collaborates with Krake Catamarane, which is a shipyard located in Apolda, Thuringia.

The project is set up in an international cooperation with Professor Anders Biel from Karlstad University in Sweden and the Swedish company Lamera from...

Superconductivity has fascinated scientists for many years since it offers the potential to revolutionize current technologies. Materials only become superconductors - meaning that electrons can travel in them with no resistance - at very low temperatures. These days, this unique zero resistance superconductivity is commonly found in a number of technologies, such as magnetic resonance imaging (MRI).

Future technologies, however, will harness the total synchrony of electronic behavior in superconductors - a property called the phase. There is currently a...

Anzeige

Anzeige

Event News

International Symposium on Functional Materials for Electrolysis, Fuel Cells and Metal-Air Batteries

02.10.2019 | Event News

NEXUS 2020: Relationships Between Architecture and Mathematics

02.10.2019 | Event News

Optical Technologies: International Symposium „Future Optics“ in Hannover

19.09.2019 | Event News

Latest News

Fraunhofer LBF and BAM develop faster procedure for flame-retardant plastics

21.10.2019 | Materials Sciences

21.10.2019 | Materials Sciences

Benefit and risk: Meta-analysis draws a heterogeneous picture of drug-coated balloon angioplasty

21.10.2019 | Medical Engineering

VideoLinks

Science & Research

Science & Research

NASA | A Year in the Life of Earth's CO2

NASA Computer Model Provides a New Portrait of Carbon Dioxide

Black Holes Come to the Big Screen

The new movie "Interstellar" explores a longstanding fascination, but UA astrophysicists are using cutting-edge technology to go one better.

NASA's Swift Mission Observes Mega Flares from a Mini Star

NASA's Swift satellite detected the strongest, hottest, and longest-lasting sequence of stellar flares ever seen from a nearby red dwarf star.

NASA | Global Hawks Soar into Storms

NASA's airborne Hurricane and Severe Storm Sentinel or HS3 mission, will revisit the Atlantic Ocean for the third year in a row.

Baffin Island - Disappearing ice caps

Giff Miller, geologist and paleoclima-tologist, is walking the margins of melting glaciers on Baffin Island, Nunavut, Canada.

The Infrasound Network and how it works

The CTBTO uses infrasound stations to monitor the Earth mainly for atmospheric explosions.