作者: Kapil Goswami, Peter Schmelcher, Rick Mukherjee

1. 核心物理图象

• 这篇论文的核心物理图象是：把整数规划问题中的每一个整数变量，直接映射到一个多能级量子系统（qudit）上，而不是像传统做法那样用多个二能级量子比特（qubit）拼凑出一个整数。 这样一来，一个包含 n 个变量、每个变量取 d 个值的优化问题，就天然地对应到 n 个 d 维 qudit 构成的希尔伯特空间上，问题的整数结构被“原样”搬进了量子硬件。

• 整个算法分两个阶段：先“筛出可行解”，再“挑出最优解”。第一阶段用一组辅助 qubit 记录每个约束是否被满足，再通过类似 Grover 的振幅放大，把 qudit 寄存器“压缩”到所有约束都满足的可行子空间里；第二阶段把目标函数的值编码成量子相位，用量子相位估计（QPE）读出，再通过一个受控旋转把“目标函数越大、测量概率越高”的偏置注入到末态振幅中。最终测量 qudit 寄存器，就有最大概率得到最优整数解。

• 核心贡献是：在保持 qudit 编码资源效率的同时，第一次给出了可扩展到多个 qudit、多个约束的完整门级量子电路，并证明了相对经典暴力搜索存在平方级加速（时间复杂度从 O(d^n) 降到约 O((√d)^n) 量级，忽略多项式因子和重复次数）。

2. 关键术语解释

• Qudit（多能级量子系统）：一个 d 维的量子系统，可以取 |0⟩ 到 |d−1⟩ 共 d 个基态。本文用它直接编码一个取 d 个整数值的决策变量，从而避免“一个整数用多个 qubit 二进制展开”带来的资源浪费。整篇论文的“资源效率”优势就来自这里。

• 蒸馏函数（distillation function）：定义为 f_i(C_i, h_i) = 2^{⌊C_i/h_i⌋}。它的作用是：如果第 i 个约束 C_i < h_i 被满足，则 f_i = 1（奇数）；否则 f_i 是偶数。把这个函数的值以模 2 方式“异或”到第 i 个辅助 qubit 上，就能把“该约束是否满足”这一信息从 qudit 寄存器转移到 qubit 寄存器，从而把可行解与不可行解纠缠到不同的 qubit 状态上。它是实现“约束筛选”的关键数学工具。

• 相位-振幅编码（phase-amplitude encoding）与 QPE：先用相位算子 Ô_c 把目标函数 C(y) 写成 qudit 态的相位 e^{i2πC(y)/C_ub}，再用量子相位估计把这个相位“读”到一组 qubit 上；最后通过一个受控旋转，把相位信息转换成辅助 qubit 的振幅偏置。效果是：目标函数值越大的可行解，其在最终测量中的振幅越大，因此最优解以最高概率被观测到。

3. 主要贡献 (Key Contributions)

• 从“单 qudit 玩具模型”到“多 qudit 可扩展电路”的跨越：此前基于 qudit 的整数规划工作（Ref. [1]）只能处理单个 qudit 的小问题，缺乏扩展性。本文给出了完整的、可作用于 n 个 qudit 与 m 个约束 qubit 的门级量子电路，使 qudit 编码真正具备解决一般整数规划问题的能力。

• 明确的量子加速与复杂度刻画：对含 n 个变量（每个取 d 值）、m 个约束、精度 ϵ_QPE、重复 r_P 次的一般有界多项式整数规划，算法时间复杂度为 O(r_P · (m·n²·log d + d^{n/2}/√N_ys + n·ϵ_QPE^{-1}))，其中 N_ys 是可行解个数。相比经典暴力搜索的 O(d^n)，在多项式重复与精度要求下实现了约 d^{n/2} 的平方级加速。作者称这是目前一般有界多项式整数规划（包括非凸非线性情形）已知最好的解析标度。

• 构造性证明最优解具有最大测量概率：在理想操作与精确代价编码下，算法末态中目标函数值最大的可行解振幅最大，因此一次测量即可以最高概率得到最优解；并给出了 QPE 精度有限时成功概率的上下界，以及达到目标成功概率 P 所需重复次数的显式公式。

• 算例展示对非凸非线性问题的处理能力：用 5 个三值变量、4 个非凸约束（含二次、三次项）的数值实例，完整模拟了电路运行，展示了约束放大与代价优化两个阶段的概率分布，并与分支定界、CP-SAT 等经典方法做了复杂度对比。

4. 研究方法 (Methodology)

• 编码层面：用 n 个 d 维 qudit 承载 n 个整数变量，用 m 个 qubit 作为“约束满足标志位”。初始化时对 qudit 施加 d 维 Hadamard 门，制备所有整数赋值的均匀叠加。

• 约束筛选阶段：对每个约束构造一个 1-稀疏的置换型幺正算子 Û_{f_i}，它本质上是一个“以约束布尔函数为控制”的 NOT 门，把满足约束的 qudit 态与 |1⟩ 纠缠、不满足的与 |0⟩ 纠缠。随后用多 qubit Grover 算子（相位翻转 Ô_m + 扩散算子 D̂_m）对 |1⟩^{⊗m} 做振幅放大，再测量 qubit 寄存器，使 qudit 寄存器坍缩到可行子空间。这正是“蒸馏函数”术语发挥作用的地方。

• 代价优化阶段：丢弃约束 qubit，引入 l 个 QPE qubit 和 1 个辅助 qubit。构造相位算子 Ô_c，利用 Ô_c|y⟩ = e^{i2π(1+C(y))/C_ub}|y⟩ 把目标函数写入相位（线性与非线性多项式项均可通过 q̂ 算子的张量积实现）。接着做 QPE 与逆 QFT，把相位信息存入 l 个 qubit；最后用受控旋转 R̂ 把“代价越大、|0⟩ 振幅越大”的偏置注入辅助 qubit，测量辅助 qubit 为 |0⟩ 即接受该样本。这就是“相位-振幅编码 + QPE”流程。

• 复杂度与成功概率分析：逐步骤统计单/多 qubit 与单/多 qudit 门数，汇总得到总时间复杂度；并推导出 QPE 相位误差 δ_QPE 下最优解与近优解可分辨的条件 C(y*_s) − C(y†_s) > ϵ_QPE·C_ub + 2C_ub·δ_QPE，以及重复次数 r ≥ ⌈log(1−P)/log(1−p)⌉。

5. 实验结果与结论 (Results and Conclusion)

• 关键结论：作者对一个含 5 个三值变量、4 个非凸约束的非线性整数规划实例做了数值模拟。结果显示：约束放大后，qubit 寄存器以高概率落在 |1111⟩（对应可行域），qudit 寄存器坍缩到 6 个可行解；代价优化后，最优解 |29⟩ ≡ |01002⟩（C = 4）的测量概率在所有可行解中最高。理想编码下，辅助 qubit 为 |0⟩ 的联合概率约 0.734，条件成功概率约 0.218，达到 P = 0.99 约需 27 次尝试。

• 与经典方法对比：在该非凸例子上，分支定界需 358 个节点，暴力搜索需 3^5 = 243 次计算，而本文量子算法的时间复杂度标度在问题规模增大后优于经典精确算法（如 Lenstra、Reis–Rothvoss 等），并且能处理经典精确算法通常无法保证最优的非凸非线性情形。不过对线性凸问题，部分经典近似算法（如 LP+rounding）在特定条件下仍具竞争力。

• 对领域的意义：这项工作把 qudit 编码从“资源效率优势”推进到“可扩展 + 可证明加速”的层面，为在囚禁离子、光子、超导 transmon、中性原子/Rydberg 等已具备 qudit 门能力的平台上实现整数规划提供了具体的电路蓝图。

• 开放问题与未来方向：作者明确指出，蒸馏函数幺正算子的门级合成、实验噪声（尤其是约束算子误差导致可行域泄漏）对算法鲁棒性的影响尚未系统研究；含三角函数、对数、有理多项式的代价函数能否纳入框架仍需探索；量子-经典混合后处理也可能进一步提升效率。此外，论文对硬件平台（包括中性原子/Rydberg 体系）的讨论主要停留在“qudit 可由原子内态或 Rydberg-dressed 态实现”的层面，尚无针对具体平台的误差预算。

6. 论文标签 (Tags)

量子算法, 量子信息, 中性原子, 里德堡原子, 编译与优化

📄 点击此处展开/折叠原文 PDF

原文链接： Qudit-based scalable quantum algorithm for solving the integer programming problem