# Puzzling on a quantum chessboard

July 10, 2019The 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."

-end-

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.

Publication: 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

University of Innsbruck

**Related Quantum Computers Articles:**

Blanket of light may give better quantum computers

Researchers from DTU Physics describe in an article in Science, how--by simple means -- they have created a 'carpet' of thousands of quantum-mechanically entangled light pulses.

Researchers from DTU Physics describe in an article in Science, how--by simple means -- they have created a 'carpet' of thousands of quantum-mechanically entangled light pulses.

One step closer future to quantum computers

Physicists at Uppsala University in Sweden have identified how to distinguish between true and 'fake' Majorana states in one of the most commonly used experimental setups, by means of supercurrent measurements.

Physicists at Uppsala University in Sweden have identified how to distinguish between true and 'fake' Majorana states in one of the most commonly used experimental setups, by means of supercurrent measurements.

Dartmouth research advances noise cancelling for quantum computers

The characterization of complex noise in quantum computers is a critical step toward making the systems more precise.

The characterization of complex noise in quantum computers is a critical step toward making the systems more precise.

Spreading light over quantum computers

Scientists at Linköping University have shown how a quantum computer really works and have managed to simulate quantum computer properties in a classical computer.

Scientists at Linköping University have shown how a quantum computer really works and have managed to simulate quantum computer properties in a classical computer.

Newfound superconductor material could be the 'silicon of quantum computers'

Newly discovered properties in the compound uranium ditelluride show that it could prove highly resistant to one of the nemeses of quantum computer development -- the difficulty with making such a computer's memory storage switches, called qubits, function long enough to finish a computation before losing the delicate physical relationship that allows them to operate as a group.

Newly discovered properties in the compound uranium ditelluride show that it could prove highly resistant to one of the nemeses of quantum computer development -- the difficulty with making such a computer's memory storage switches, called qubits, function long enough to finish a computation before losing the delicate physical relationship that allows them to operate as a group.

Quantum computers to clarify the connection between the quantum and classical worlds

Los Alamos National Laboratory scientists have developed a new quantum computing algorithm that offers a clearer understanding of the quantum-to-classical transition, which could help model systems on the cusp of quantum and classical worlds, such as biological proteins, and also resolve questions about how quantum mechanics applies to large-scale objects.

Los Alamos National Laboratory scientists have developed a new quantum computing algorithm that offers a clearer understanding of the quantum-to-classical transition, which could help model systems on the cusp of quantum and classical worlds, such as biological proteins, and also resolve questions about how quantum mechanics applies to large-scale objects.

The best of both worlds: how to solve real problems on modern quantum computers

Researchers at the US Department of Energy's (DOE) Argonne National Laboratory and Los Alamos National Laboratory, along with researchers at Clemson University and Fujitsu Laboratories of America, have developed hybrid algorithms to run on size-limited quantum machines and have demonstrated them for practical applications.

Researchers at the US Department of Energy's (DOE) Argonne National Laboratory and Los Alamos National Laboratory, along with researchers at Clemson University and Fujitsu Laboratories of America, have developed hybrid algorithms to run on size-limited quantum machines and have demonstrated them for practical applications.

A new theory for trapping light particles aims to advance development of quantum computers

Researchers have developed a new protocol for ensuring the stability of data when photons are stored for extended periods of time.

Researchers have developed a new protocol for ensuring the stability of data when photons are stored for extended periods of time.

Improving quantum computers

For decades, experts have predicted that quantum computers will someday perform difficult tasks, such as simulating complex chemical systems, that can't be done by conventional computers.

For decades, experts have predicted that quantum computers will someday perform difficult tasks, such as simulating complex chemical systems, that can't be done by conventional computers.

A new hope of quantum computers for factorizations of RSA with a thousand-fold excess

Universal quantum computers are still in its infancy that cannot achieve practical applications (code-cracking) in near term.

Universal quantum computers are still in its infancy that cannot achieve practical applications (code-cracking) in near term.

## Best Science Podcasts 2019

We have hand picked the**best science podcasts**for 2019. Sit back and enjoy new science podcasts updated daily from your favorite science news services and scientists.

**Now Playing: TED Radio Hour**

**Rethinking Anger**

Anger is universal and complex: it can be quiet, festering, justified, vengeful, and destructive. This hour, TED speakers explore the many sides of anger, why we need it, and who's allowed to feel it. Guests include psychologists Ryan Martin and Russell Kolts, writer Soraya Chemaly, former talk radio host Lisa Fritsch, and business professor Dan Moshavi.

**Now Playing: Science for the People**

**#538 Nobels and Astrophysics**

This week we start with this year's physics Nobel Prize awarded to Jim Peebles, Michel Mayor, and Didier Queloz and finish with a discussion of the Nobel Prizes as a way to award and highlight important science. Are they still relevant? When science breakthroughs are built on the backs of hundreds -- and sometimes thousands -- of people's hard work, how do you pick just three to highlight? Join host Rachelle Saunders and astrophysicist, author, and science communicator Ethan Siegel for their chat about astrophysics and Nobel Prizes.