Noise-Directed Adaptive Remapping for Integer Optimization: from qubits to (encoded) qudits

技术摘要：面向整数优化的噪声导向自适应重映射（NDAR）

问题陈述
本文探讨了在近期的量子硬件上优化离散整数域的挑战，特别是将噪声导向自适应重映射（NDAR）元算法从其最初的无约束二元优化领域扩展到更广泛的范围。虽然此前已证明 NDAR 通过利用设备噪声作为计算资源来提升二元问题的性能，但其在整数问题（定义域为 $\mathbb{Z}_d^n$）以及非二元编码（如 qudit 或基于 qubit 编码的整数）中的应用仍处于空白。核心难点在于，整数优化通常涉及硬约束（例如图着色问题中的有效着色），且不同的编码方案（二进制、独热编码、域壁编码、原生 qudit）与硬件噪声及规范变换（gauge transformations）的相互作用各不相同。作者研究了如何将 NDAR 推广到这些设置中，并确定了可行性、规范选择和电路可实现性的具体要求。

方法论
作者将 NDAR 框架推广到处理 $\mathbb{Z}_d^n$ 上的整数优化问题。该方法涉及针对高维系统调整后的四个关键组成部分：

1. 噪声吸引子识别： 该框架假设存在一个已知的由硬件噪声（例如振幅阻尼）驱动的经典“吸引子”状态。对于 qudit，作者对广义振幅阻尼通道进行了建模，表明在零温或有限温度下，系统会自然向低激发态（通常为 $|00\dots0\rangle$）弛豫，这与 qubit 中的全零吸引子类似。
2. 可行性与约束： 与无约束二元优化不同，整数问题通常包含硬约束（例如有效的颜色分配）。作者扩展了 NDAR，要求吸引子状态必须编码一个可行解。他们分析了各种编码方式，以确定 $|00\dots0\rangle$ 状态是否有效，以及可行状态集合是否在所选规范群下构成传递轨道（transitive orbit）。
3. 规范变换选择： 在二元优化中，位翻转操作可以将吸引子唯一地映射到任何目标字符串。但在 qudit（$d>2$）或编码 qubit 的情况下，这种一一对应关系会失效，从而产生一个指数级庞大的兼容规范变换族。作者提出选择特定的规范变换（例如，针对原生 qudit 的循环移位，或针对域壁编码的前缀翻转），这些变换在将吸引子映射到当前迭代中找到的最佳候选解的同时，能够保持量子电路（ansatz）的结构。
4. 自适应重映射循环： 该算法迭代运行量子优化器（如 QAOA），采样解，选择最佳可行候选解，并对代价哈密顿量（cost Hamiltonian）和约束进行规范变换。这使得噪声吸引子与高质量解对齐，从而有效地利用噪声在后续迭代中驱动系统向更好的解演化。

研究通过使用 Max-k-可着色子图问题 作为运行示例，在多种编码方案下评估了这些标准：

• 原生 Qudit 编码： 直接映射到 $d$ 级系统。
• 二进制编码： 将整数映射到 $\lceil \log_2 d \rceil$ 个 qubit。
• 独热编码（One-Hot Encoding）： 每个变量使用 $d$ 个 qubit（汉明重量为 1）。
• 01-Hot 编码： 包含全零状态的增强型独热编码。
• 域壁编码（Domain-Wall Encoding）： 使用 $d-1$ 个 qubit 表示每个变量，并具有特定的边界条件。

主要贡献

1. NDAR 的泛化： 本文提供了一个将 NDAR 应用于整数域和硬约束的统一框架，形式化了使算法保持有效的条件（特别是关于吸引子的可行性和高效规范变换的存在性）。
2. Qudit 中的规范自由度分析： 作者证明了原生 qudit 系统比 qubit 拥有显著更多的规范自由度（$(d-1)!^n$）。这种多余的自由度被视为一种设计杠杆，允许选择与特定硬件门集（例如循环移位对比任意置换）最兼容的规范变换，以最小化电路开销。
3. 编码对比分析： 通过 NDAR 的视角，本文对比了原生 qudit 编码与基于 qubit 的二进制及一元（独热、域壁）编码。主要发现包括：
   • 原生 Qudits： 提供最有利的属性组合：1 个 qudit 对应 1 个变量，有效字符串概率 $q=1$，无额外硬约束，且具有可行的 $|00\dots0\rangle$ 吸引子和 2-local 代价哈密顿量。
   • 二进制编码： 虽然空间效率高，但代价哈密顿量和相位算符需要更高的局部性（$2\lceil \log_2 d \rceil$-local）。
   • 一元编码： 虽然域壁和 01-hot 编码可以支持可行吸引子，但它们往往会对代价哈密顿量引入非平凡变换，或者由于噪声引起的泄漏导致吸引子不可行（在标准 one-hot 中）。
4. 硬件对齐： 该工作将 NDAR 的理论要求与新兴的超导腔 qudit 硬件联系起来，指出这些系统中的振幅阻尼噪声自然地与 NDAR 吸引子模型相契合。

结果

• 编码权衡： 文中的表 I 总结了原生 qudit 编码提供的“同类最佳”属性组合：每变量 1 qudit，有效字符串概率 $q=1$，无额外硬约束，具有可行的 $|00\dots0\rangle$ 吸引子，以及 2-local 代价哈密顿量。相比之下，基于 qubit 的编码通常需要额外的硬约束，具有 $q < 1$（由于噪声），或导致更高局部性的算符。
• 吸引子的可行性： 研究指出，对于标准 one-hot 编码，自然的噪声吸引子（$|00\dots0\rangle$）是无效的，这使得标准的 NDAR 在不经修改的情况下无法应用。相反，域壁和 01-hot 编码可以被构建为具有可行吸引子的形式，尽管它们可能会改变代价哈密顿量的局部性。
• 电路复杂度： 作者展示了虽然二进制编码具有空间效率，但如果选择不当，所需的规范变换可能会引入复杂的电路结构（例如需要多受控门）。原生 qudit 编码允许使用更简单的规范变换（如移位），从而保持 QAOA ansatz 的 2-local 结构。

意义与主张
本文声称，由 NDAR 引导的噪声考量为比较设备级编码选择提供了一个新的准则。文章认为，编码的选择不仅仅是资源计数（qubits vs. qudits）的问题，它从根本上影响了算法利用噪声的能力。

作者断言：

1. 原生 qudit 实现的 NDAR 相比于同等的 qubit 编码具有明显的优势，特别是在噪声诱导动力学如何与解空间相互作用方面。
2. Qudit 系统中的**规范多样性（gauge multiplicity）**是一个特性而非缺陷，它允许根据特定的硬件约束定制变换。
3. 该框架在实验上是相关的，适用于新兴的超导腔 qudit 设备（例如 SQMS Center 的设备），其中噪声特性（振幅阻尼）和门操作能力（CSUM, ECD）与 NDAR 的要求高度契合。

论文最后概述了在超导 qudit 设备中实现 NDAR 的方向，强调需要高保真度的两 qudit 纠缠门和误差抑制技术，以充分利用 NDAR 方法。它将这项工作定位为利用日益增长的非 qubit 量子处理器执行实际优化任务的必要步骤。