(Phys.org) 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. “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.”
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.