The N-queens problem is to find the position of N queens on an N by N chessboard such that no queens attack each other. The excluded diagonals N-queens problem is a variation where queens cannot be placed on some predefined fields along diagonals. This variation is proven NP-complete and the parameter regime to generate hard instances that are intractable with current classical algorithms is known.
We propose a special purpose quantum simulator that implements the excluded diagonals N-queens completion problem using atoms in an optical lattice and cavity-mediated long-range interactions. Our implementation has no overhead from the embedding allowing to directly probe for a possible quantum advantage in near term devices for optimization problems.
Read the full article here.
A Quantum N-Queens Solver
V. Torggler, P. Aumann, H. Ritsch, W. Lechner
Quantum 3, 149 (2019).
Popular media also covered the question and results of the paper!
Read them here (in German):
- Quantencomputer könnte kniffliges Schachproblem lösen,
derStandard.at (10. Juli 2019) - Das "Damenproblem" auf dem Quantenschachbrett,
science.orf.at (10. Juli 2019) - Schachaufgabe soll Quanten-Überlegenheit demonstrieren,
Spektrum (10. Juli 2019) - Das schachmathematische Damenproblem zeigt Überlegenheit des Quantencomputers, Innovation Origins (12. Juli 2019)
