标题： 里德堡原子阵列的量子编译工具包及其对问题难度和量子加速的影响 显示英文标题

标题： Quantum Compilation Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups

摘要： 我们提出并实现了一个全面的量子编译工具包，用于基于里德堡原子阵列的量子硬件上求解最大独立集（MIS）问题。我们的端到端流水线涉及三个核心组件，以高效地将通用的MIS实例映射到具有单位圆连通性的里德堡阵列上，包括图简化模块、硬件兼容性检查模块和图嵌入模块。 第一个模块（简化器）提供了与硬件无关且确定性的简化逻辑，通过惰性团删除迭代地减小问题规模。我们发现现实世界中的网络通常可以在亚秒级的时间尺度上减少几个数量级，从而显著减少量子设备最终的负载。 此外，我们表明简化技术可能是寻找潜在量子加速的重要工具，因为它们能够识别出困难的问题实例。特别是对于里德堡本征的MIS实例，我们观察到了易-难-易转变的特征，并量化了表示困难问题开始出现的关键度。 第二个模块（兼容性检查器）实现了一个硬件兼容性检查器，快速判断给定的输入图是否可能与里德堡量子硬件施加的限制相兼容。 第三个模块（嵌入器）描述了高效的图嵌入例程，生成可控开销和优化辅助位放置的（近似）编码。 我们通过在亚马逊Braket上的QuEra Aquila设备上运行实验来展示我们的流水线。总体而言，我们的工作提供了一组工具，扩展了可以使用近期里德堡原子阵列解决的问题类别。 显示英文摘要

摘要： We propose and implement a comprehensive quantum compilation toolkit for solving the maximum independent set (MIS) problem on quantum hardware based on Rydberg atom arrays. Our end-to-end pipeline involves three core components to efficiently map generic MIS instances onto Rydberg arrays with unit-disk connectivity, with modules for graph reduction, hardware compatibility checks, and graph embedding. The first module (reducer) provides hardware-agnostic and deterministic reduction logic that iteratively reduces the problem size via lazy clique removals. We find that real-world networks can typically be reduced by orders of magnitude on sub-second time scales, thus significantly cutting down the eventual load for quantum devices. Moreover, we show that reduction techniques may be an important tool in the ongoing search for potential quantum speedups, given their ability to identify hard problem instances. In particular, for Rydberg-native MIS instances, we observe signatures of an easy-hard-easy transition and quantify a critical degree indicating the onset of a hard problem regime. The second module (compatibility checker) implements a hardware compatibility checker that quickly determines whether or not a given input graph may be compatible with the restrictions imposed by Rydberg quantum hardware. The third module (embedder) describes hardware-efficient graph embedding routines to generate (approximate) encodings with controllable overhead and optimized ancilla placements. We exemplify our pipeline with experiments run on the QuEra Aquila device available on Amazon Braket. In aggregate, our work provides a set of tools that extends the class of problems that can be tackled with near-term Rydberg atom arrays.