A Quantum N-Queens Solver
A Quantum N-Queens Solver
复制标题
量子 N 皇后求解器
作者：
Valentin Torggler;Philipp Aumann;H. Ritsch;W. Lechner
N皇后问题是在N * N的棋盘上找到N个皇后的位置，使得没有皇后互相攻击。排除对角线n皇后问题是一种变化，其中皇后不能放置在沿对角线的一些预定义字段上。这种变化被证明是np完全的，并且已知用于生成当前经典算法难以处理的硬实例的参数体系。我们提出了一个特殊用途的量子模拟器，利用光学晶格中的原子和腔介导的远程相互作用实现了排除对角线n皇后补全问题。我们的实现没有嵌入的开销，允许直接探测近期设备中可能的量子优势以解决优化问题。
The N-queens problem is to find the position of N queens on an N by N chess board 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.
登录
查看更多内容
影响因子：
2.9
作者：
S. Caballero-Benitez;G. Mazzucchi;I. Mekhov
通讯作者：
S. Caballero-Benitez;G. Mazzucchi;I. Mekhov
影响因子：
6.4
作者：
Preskill, John
通讯作者：
Preskill, John
影响因子：
64.8
作者：
Bernien, Hannes;Schwartz, Sylvain;Lukin, Mikhail D.
通讯作者：
Lukin, Mikhail D.
影响因子：
56.9
作者：
M. Wolke;Julian Klinner;H. Keßler;A. Hemmerich
通讯作者：
M. Wolke;Julian Klinner;H. Keßler;A. Hemmerich