Nav: Home

Puzzling on a quantum chessboard

July 10, 2019

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."
-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:

Hot qubits break one of the biggest constraints to practical quantum computers
A proof-of-concept published today in Nature promises warmer, cheaper and more robust quantum computing.
Future quantum computers may pose threat to today's most-secure communications
Quantum computers that are exponentially faster than any of our current classical computers and are capable of code-breaking applications could be available in 12 to 15 years, posing major risks to the security of current communications systems, according to a new RAND Corporation report.
Novel error-correction scheme developed for quantum computers
Experimental quantum computers are plagued with errors. Here Dr Arne Grimsmo from the University of Sydney and colleagues from RMIT and the University of Queensland offer a novel method to reduce errors in a scheme applicable across different types of quantum hardware.
FEFU scientists developed method to build up functional elements of quantum computers
Scientists from Far Eastern Federal University (FEFU, Vladivostok, Russia), together with colleagues from FEB RAS, China, Hong Kong, and Australia, manufactured ultra-compact bright sources based on IR-emitting mercury telluride (HgTe) quantum dots (QDs), the future functional elements of quantum computers and advanced sensors.
ORNL researchers advance performance benchmark for quantum computers
Researchers at the Department of Energy's Oak Ridge National Laboratory (ORNL) have developed a quantum chemistry simulation benchmark to evaluate the performance of quantum devices and guide the development of applications for future quantum computers.
Quantum computers learn to mark their own work
A new test to check if a quantum computer is giving correct answers to questions beyond the scope of traditional computing could help the first quantum computer that can outperform a classical computer to be realised.
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.
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.
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.
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.
More Quantum Computers News and Quantum Computers Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

Listen Again: Reinvention
Change is hard, but it's also an opportunity to discover and reimagine what you thought you knew. From our economy, to music, to even ourselves–this hour TED speakers explore the power of reinvention. Guests include OK Go lead singer Damian Kulash Jr., former college gymnastics coach Valorie Kondos Field, Stockton Mayor Michael Tubbs, and entrepreneur Nick Hanauer.
Now Playing: Science for the People

#562 Superbug to Bedside
By now we're all good and scared about antibiotic resistance, one of the many things coming to get us all. But there's good news, sort of. News antibiotics are coming out! How do they get tested? What does that kind of a trial look like and how does it happen? Host Bethany Brookeshire talks with Matt McCarthy, author of "Superbugs: The Race to Stop an Epidemic", about the ins and outs of testing a new antibiotic in the hospital.
Now Playing: Radiolab

Dispatch 6: Strange Times
Covid has disrupted the most basic routines of our days and nights. But in the middle of a conversation about how to fight the virus, we find a place impervious to the stalled plans and frenetic demands of the outside world. It's a very different kind of front line, where urgent work means moving slow, and time is marked out in tiny pre-planned steps. Then, on a walk through the woods, we consider how the tempo of our lives affects our minds and discover how the beats of biology shape our bodies. This episode was produced with help from Molly Webster and Tracie Hunte. Support Radiolab today at Radiolab.org/donate.