里德堡模拟优化与 MIS

中性原子的"原生算法"藏在硬件约束里：单位盘图（unit disk graph）恰好就是里德堡阻塞的几何图，把原子摆成图的顶点、绝热扫过哈密顿量，基态里德堡位形就是最大独立集（MIS）问题的解——这是不经过线路分解、零开销的模拟计算；Aquila 已把它做成 256 比特的商用模拟能力，同时也给出诚实基准：混合算法在随机图系综上尚未稳定胜过经典贪婪算法。

物理图像

给定图 $G=(V,E)$，最大独立集（maximum independent set, MIS）是没有边相连的最大顶点子集；判定其大小是否超过给定整数是 NP 完全问题，连近似其大小都是 NP 难的。它出现在无线网络设计、地图标注等实际问题中 Pichler 2018。

里德堡阵列给出一条”几何即问题”的编码路线：单位盘图（UD graph）把顶点摆在二维平面上，两点距离小于单位长度即连边——而这正是阻塞几何（见里德堡阻塞）。把一个原子放在每个顶点上，“互为近邻的两个原子不能同时被激发到里德堡态”这一物理约束逐字就是独立集约束：最终测量哪些原子处于里德堡态，读出的就是独立集 Pichler 2018。

理论模型

从阻塞到 QUBO 型哈密顿量

对每个顶点/原子赋予自旋 $n_v=|1{⟩}_v⟨1|$（$|1⟩$ 即里德堡态），MIS 的代价函数是

$$H_P=-\Delta \sum _{v\in V}{n}_v+U\sum _{(v,w)\in E}{n}_v{n}_w,$$

这是二元变量上的二次型——即 QUBO（二次无约束二元优化）的标准形式：当 $U>\Delta >0$ 时每个自旋都倾向 $|1⟩$，但相连的一对会因 $U$ 受罚，基态恰为 MIS。完整里德堡哈密顿量再补上横向驱动与长程相互作用尾巴

$$H_{Ryd}=\sum _v({\Omega }_v{\sigma }_v^x-{\Delta }_v{n}_v)+\sum _{v<w}V(|{\vec{x}}_v-{\vec{x}}_w|)n_v{n}_w,V(x)=\frac{C_6}{x^6},$$

阻塞半径 $r_B=(C_6/((2\Omega {)}^2+{\Delta }^2){)}^{1/6}$ 起到”有效单位盘半径”的作用；相互作用工程细节见里德堡相互作用与 Förster 共振 Pichler 2018。

NP 难度保持。一个严格的担忧是：物理哈密顿量有 $1/R^6$ 尾巴，并不严格等于 UD-MIS。Pichler 等给出显式归约：任何最大度 3 的平面图可铺在网格上、沿每条边插入偶数个辅助顶点转化为 UD 图，辅以 $0.51C_6/r^6\lesssim {\Delta }_v\lesssim C_6/r^6$ 的失谐图样补偿角点/交汇处的相互作用尾巴——于是含长程尾的里德堡哈密顿量基态仍是 NP 完全问题的精确编码 Pichler 2018。

独立集子空间的投影

当阻塞远强于驱动（$U\gg |\Omega |,|\Delta |$）时，非独立集位形被能量惩罚推出动力学空间，演化被有效限制在独立集子空间 ${\mathcal{H}}_{IS}$ 内。在该子空间里 $H_P$ 中的对角部分只相当于每个自旋绕 $z$ 轴的独立转动，希尔伯特空间维数从 $2^N$ 骤减到独立集数：数值上先用经典算法（Bron–Kerbosch）枚举全部独立集、再把哈密顿量投影进去，可把绝热模拟推到 $N\sim 50$。这个技巧也解释了 MIS 平台的一个方法论优势——测量就是计算基读出，目标函数 $⟨H_P⟩$ 与”测到多大独立集”直接对应 Pichler 2018。

量子退火与 QAOA

标准退火路线从全 $|0⟩$（$\Delta <0,\Omega =0$）绝热演化到 MIS（$\Delta >0,\Omega =0$）：

$$\Omega (t)={\Omega }_0{\sin }^2(\pi t/T),\Delta (t)={\Delta }_0(2t/T-1).$$

经典难度的分布由顶点密度 $\rho$ 控制：低于渗流阈值 ${\rho }_c\approx 1.436$ 时图碎成有限团簇、问题多项式可解；密度 $\rho \sim 7$ 附近分支定界法在 $N\gtrsim 150$ 出现明确指数标度，$N\gtrsim 440$ 时单节点 24 小时 CPU 时间都找不到解。有趣的是非绝热短时间退火（$T=10/{\Omega }_0\ll T_{LZ}$）与浅层 QAOA（$p=3$ 约需 $10^2-10^3$ 次测量；深度 $p\lesssim 40$ 即可在 $N=32$ 的困难实例上达到 $O(1)$ 成功概率）都能以显著偏离绝热极限的方式逼近 MIS Pichler 2018。

资源粗估：以 $\Omega \sim 2\pi \times (10-100)\mathrm{MHz}$、单比特相干 $\tau \sim 200\mu s$ 计，相干模拟体积 $pN\gtrsim 10^4$，可检验的实例规模 $N\sim 10^2-10^3$ Pichler 2018。

超越单位盘图

UD 图之外的问题可用多体门 + Trotter 化时间演化逼近一般图结构：把目标顶点的邻居从 $|1⟩$ 选择性激发到另一里德堡态，再经 P 态做两步跃迁，即实现以邻居为控制的多比特受控转动——这类”奇偶相位”资源与奇偶相位门与原生多体门、多比特阻塞门同源 Pichler 2018。

方法与实现

Aquila：商用的模拟 FPQA。QuEra 的 Aquila 是接入云平台的”场可编程量子阵列”（FPQA），以模拟哈密顿量模式在最多 256 个 Rb-87 原子上执行用户定义的 $\Omega (t),\Delta (t),\varphi (t)$ 波形（设备能力的形式化模型见FPQA 计算模型）。出厂参数表：用户区域 $75\times 76\mu m^2$、最小位点间距 4 μm、$\Omega \le 15.8rad/\mu \mathrm{s}$（斜率 $\le 250rad/\mu {\mathrm{s}}^2$）、$|\Delta |\le 125rad/\mu \mathrm{s}$、单次演化时长 4 μs；位置系统误差 0.050 μm、热运动 0.200 μm、Rabi 非均匀性 2%；装载失败 0.7%、探测假阴/假阳各约 1%；$|70S⟩$ 相互作用 $V(8\mu m)\approx 20rad/\mu \mathrm{s}$（4 μm 处 1320，16 μm 处仅 0.32——阻塞边界清晰）；基–里德堡 qubit $T_2^{\ast }=5.8\mu s$、自旋回波 $T_2=11.4\mu s$ Wurtz 2023。

Aquila 上的 UD-MIS 教学实例。把 16×16 王图（King’s graph，连通性按国际象棋王步）做 30% 随机删点，得到 183 顶点、MIS 大小 60 的实例；格点间距 5 μm 给出单位盘半径 $R_{ud}\in (5\sqrt{2},10)\mu m$，对应阻塞失谐 $5.4<{\Delta }_b<43rad/\mu \mathrm{s}$。流程：线性绝热斜坡（$\Omega$ 升到 15 rad/μs，$\Delta$ 从 $-30$ 扫到可优化的终值 ${\Delta }_f$），测量后做两步经典后处理（贪心删去独立集违规、再贪心补满为极大独立集 mIS）。结果如实呈现了当前水平：单实例上经典贪婪基线平均 mIS 58.0，混合算法 57.5，但后者以约 4.5% 概率命中真正的 MIS（60）；在 50 个图的系综上平均性能比 $⟨PR⟩=0.974$——尚无系综优势，与 Science 上 Ebadi 等工作的结论一致（难度由第一激发态与 MIS 的简并比刻画）Wurtz 2023。

这一”量子—经典对照 + 后处理 + 系综基准”的流程本身就是模拟优化实验的标准方法学，与中性原子基准测试的评测思想一致；开源脉冲序列设计工具见Pulser 脉冲设计平台。

绝热协议的实测刻画。Aquila 白皮书用最简单的目标复现了退火方法的性能剖析：以一维 $Z_2$ 态为例，固定 $N=11$ 把基态保真度对总退火时间作图，看到典型的”两头堵”——短退火时间由有限速度的非绝热误差主导，长退火时间被噪声与退相干接管（里德堡态寿命与激光噪声），中间才有最优窗口；绝热制备的 $Z_2$ 态关联长度约 3.6 个格点、二维 checkerboard 约 5.7 个格点，给出了”当前设备能稳定制备多大的有序态”的直观标尺 Wurtz 2023。

模拟计算能力的定位。模拟模式不执行数字门，而以连续时间演化直接制备多体基态/扫描相图。它的优势是零线路开销与大规模纠缠，劣势是误差只能靠绝热质量与后处理控制——与数字容错路线（逻辑量子处理器、三比特门容错稳定子测量）构成能力互补 Wurtz 2023。

UD 图—原子阵列的 MIS 映射：图实例、阻塞半径与退火扫线 Ω(t), Δ(t)（图源：Pichler 2018 Fig. 1）

Aquila 上王图 MIS 实例的变分性能与混合/经典算法 mIS 分布（图源：Wurtz 2023 Fig. 6）

参数与量级

量	数值	来源
MIS 哈密顿量	$H_P=-\Delta \sum n_v+U{\sum }_{(v,w)}{n}_v{n}_w$（$U>\Delta >0$，QUBO 型）	Pichler 2018
阻塞/单位盘半径	$r_B=(C_6/((2\Omega {)}^2+{\Delta }^2){)}^{1/6}$	Pichler 2018
经典难度拐点	${\rho }_c\approx 1.436$；$\rho \sim 7$ 时 $N\gtrsim 150$ 指数、$N\gtrsim 440$ 超 24 h 无解	Pichler 2018
QAOA 资源	$p=3$ 约需 $10^2-10^3$ 次测量；$p\lesssim 40$ 达 $O(1)$ 成功率	Pichler 2018
近期能力估计	$\Omega \sim 2\pi \times (10-100)\mathrm{MHz}$，$\tau \sim 200\mu s$，体积 $pN>10^4$，$N\sim 10^2-10^3$	Pichler 2018
Aquila 规模/几何	256 qubit；区域 $75\times 76\mu m^2$；最小间距 4 μm	Wurtz 2023
Aquila 控制范围	$\Omega \le 15.8rad/\mu \mathrm{s}$，$|\Delta |\le 125rad/\mu \mathrm{s}$，演化 $\le 4\mu s$	Wurtz 2023
Aquila 相干与误差	$T_2^{\ast }=5.8\mu s$；位置误差 0.05/0.20 μm；探测误差约 1%	Wurtz 2023
MIS 实例结果	183 顶点王图：经典 mIS 58.0 vs 混合 57.5；系综 $⟨PR⟩=0.974$	Wurtz 2023

与其他概念的关系

• 整个映射的物理基础是里德堡阻塞：$C_6/r^6$ 相互作用与阻塞半径的定义见里德堡相互作用与 Förster 共振。
• 顶点摆放依赖任意几何的原子装配无缺陷阵列；承载它的光镊阵列与魔强度陷阱与FPQA 计算模型定义了模拟波形的可行域。
• “多体门 + Trotter 化推广到一般图”用到的原生资源是奇偶相位门与多比特阻塞门。
• 平台定位与商用能力总览见中性原子量子计算硬件全景；性能评测方法学见中性原子基准测试，开源工具链见Pulser 脉冲设计平台。
• 模拟优化与数字纠错路线的分工：深电路容错计算走逻辑量子处理器与三比特门容错稳定子测量的路线，而组合优化、量子相变探针与多体物理（量子二聚体、 scars 等）留在模拟侧。
• 长程相互作用尾巴的利用与补偿也与布局映射与长程交互利用中的编译问题相通。

参考文献

• H. Pichler, S.-T. Wang, L. Zhou, S. Choi, M. D. Lukin, “Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays”, 预印本 (2018). NA141 · arXiv:1808.10816（语料标注为预印本，未核实后续正式发表信息）
• J. Wurtz, A. Bylinskii, B. Braverman, J. Amato-Grill, S. H. Cantu, F. Huber, A. Lukin, F. Liu, P. Weinberg, J. Long, S.-T. Wang, N. Gemelke, A. Keesling, “Aquila: QuEra’s 256-qubit neutral-atom quantum computer”, 技术白皮书 (2023). NA148 · arXiv:2306.11727