论文标题
使用Rydberg Atom阵列对最大独立集的量子优化
Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
论文作者
论文摘要
实现量子加速度的实际相关，计算困难问题是量子信息科学中的核心挑战。使用Rydberg Atom阵列在两个空间维度上最多具有289个QUBITS，我们通过实验研究量子算法，以解决最大的独立集问题。我们使用与Rydberg Blockade关联的硬件有效的编码，实现闭环优化来测试多种变异算法，然后将它们应用于系统地探索具有可编程连接性的一类图形。我们发现问题硬度由溶液退化和局部最小值的数量控制，并在实验中基准测试了量子算法对经典模拟退火的性能。在最难的图表上，我们观察到在深度电路态度中查找精确溶液并分析其起源时，会观察到超线性量子加速。
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find the problem hardness is controlled by the solution degeneracy and number of local minima, and experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.
