Physicists at the University of Innsbruck are proposing a new model that could demonstrate the supremacy of quantum computing over conventional supercomputers in solving optimization problems. In a recent paper, they show that only a few quantum particles would be sufficient to solve the mathematically difficult problem of N-queens in chess, even for large plateaus.
The problem of the queen is a mathematical task that already occupied the great mathematician Carl Friedrich Gauss, but for which he did not find the right solution. The challenge is to have eight queens on a classic board of 8 x 8 squares so they do not threaten. Mathematically, it is relatively easy to determine that there are 92 different ways of arranging queens. On a chessboard of 25 x 25 boxes, there are already more than 2 billion possibilities. Calculating this number alone has taken a total of 53 years of CPU time.
The task becomes even more difficult if some queens are already in the field and some diagonals may not be occupied. Recently, it has been shown that with these additional restrictions, the 21 queens problem could no longer be solved by conventional mathematical algorithms within a reasonable time. "I came across this subject by chance and I thought quantum physics could really exploit its benefits here," says Wolfgang Lechner, of the Department of Theoretical Physics at the University of Innsbruck and the University of Innsbruck. Institute of Quantum Optics and Quantum Information of the Austrian Academy of Sciences. With Helmut Ritsch and Ph.D. Students Valentin Torggler and Philipp Aumann of Lechner have developed a quantum chessboard on which the puzzle of the queens could be solved experimentally with the help of quantum physics.
From atoms to queens of chess
"An optical network of laser beams in which individual atoms are placed can be used as a chessboard," explains Helmut Ritsch, also a member of the Department of Theoretical Physics of Innsbruck. "By adjusting the interaction between atoms, we can create chess queens from atoms, which behave according to the rules of chess, that is, to say which avoid each other in every sense of the game board. " This repulsion of the particles is generated by means of lasers applied according to the directions of movement. Via an optical resonator (two mirrors above and below the optical network), this interaction is further intensified and thus becomes effective over much greater distances.
"We could also play this game with such repugnant billiard balls," says Ritsch. "But as there are so many possibilities, it would take a very, very long time, so it is crucial that the atoms be cooled very strongly and their quantum properties take effect because they behave like waves and can to test many possibilities At the same time, it quickly becomes clear that there is a valid solution according to the rules of the failures for the given conditions. "
Quantum supremacy at the horizon
The answer to the question of whether there is a solution within the given restrictions can be read very easily from the light emitted by the resonator. But the specific disposition of atomic queens could only be determined by atomic microscopy, a method recently successfully applied in related experiments.
The simulations on classical computers strongly suggest that the experiment designed by Innsbruck's theorists would result in a much faster result than any mathematical algorithm on a conventional computer. "This would allow for the first time to clearly prove the supremacy of quantum computers in the calculation of certain optimization problems", summarizes Wolfgang Lechner. "The control of a few tens of atoms is already a common practice in the laboratory, which is why the implementation of this idea could soon become a reality."
Quantum sensor for photons
Valentin Torggler et al., A quantum solver of N-Queens, Quantum (2019). DOI: 10.22331 / q-2019-06-03-149
Solve problems on a quantum chessboard (July 10, 2019)
recovered on July 10, 2019
This document is subject to copyright. Apart from any fair use for study or private research purposes, no
part may be reproduced without written permission. Content is provided for information only.