论文标题
使用3D原子嵌入具有界度的非本地图的MIS问题
Embedding the MIS problem for non-local graphs with bounded degree using 3D arrays of atoms
论文作者
论文摘要
在过去的几年中，已经提出了许多量子算法来解决硬组合问题。这些算法在复杂性理论中进行了深入研究，是许多工业应用的核心。特别是，最大独立集（MIS）是一个已知的NP硬性问题，可以在Rydberg原子阵列中自然编码。通过表示具有中性原子集合的图形可以利用Rydberg动力学来自然编码约束和误解的解决方案。但是，可以直接在此类设备上直接映射节点到原子的图形类别仅限于单位磁盘图。在这种情况下，可以通过经典的多项式时间近似方案（PTA）来利用图形的固有位置，以保证ε-值得注意的解决方案。在这项工作中，我们提出了确定性和多项式时间结构，将大型非本地图嵌入3D原子阵列中。这种构造是在量子计算机上解决组合任务的第一步，不存在经典的ε-approximation方案。
In the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. These algorithms, which have been studied in depth in complexity theory, are at the heart of many industrial applications. In particular, the Maximum Independent Set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays. By representing a graph with an ensemble of neutral atoms one can leverage Rydberg dynamics to naturally encode the constraints and the solution to MIS. However, the classes of graphs that can be directly mapped node-to-atom on such devices are limited to Unit-Disk graphs. In this setting, the inherent locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an ε-approximate solution. In this work, we present a deterministic and polynomial-time construction to embed a large family of non-local graphs in 3D atomic arrays. This construction is a first crucial step towards tackling combinatorial tasks on quantum computers for which no classical efficient ε-approximation scheme exists.
