Resource-Efficient Quantum Optimization via Higher-Order Encoding

本文证明了高阶无约束二进制优化（HUBO）为组合优化问题提供了一种比传统 QUBO 公式显著更具资源效率的替代方案，在大幅减少量子比特和 CNOT 门数量的同时，还提供了一个开源库以促进其在近期量子设备上的应用。

要点

想象一下你正在试图解决一个巨大且复杂的谜题。在量子计算的世界里，这个谜题被称为组合优化问题（Combinatorial Optimization Problem）。这就像是试图找出为飞机分配机场登机口、为地图涂色以确保相邻国家颜色不同，或者调度工厂生产线以节省最多成本的最优方案。

长期以来，科学家们一直尝试使用一种特定的方法来解决这些谜题，这种方法被称为 QUBO（二次无约束二进制优化）。你可以把 QUBO 想象成一种非常严格、僵化的将你的谜题翻译成量子计算机能理解的语言的方式。

旧方法的缺陷 (QUBO)

该论文指出，QUBO 方法就像是试图通过强迫每一件物品都装进各自独立的、过大的盒子里来打包行李。

• 太多的盒子（Qubits/量子比特）： 如果一个变量可以有 10 种不同的取值（比如 10 个不同的机场登机口），QUBO 会强迫你使用 10 个独立的“盒子”（量子比特）来表示这一个选择。
• 太多的胶水（惩罚项）： 为了确保计算机不会同时选择两个盒子（这会导致错误），你必须添加沉重的“胶水”，即惩罚项。这种胶水会让指令（量子电路）变得极其冗长且复杂。
• 结果： 量子计算机会被压垮。它需要太多的部件（量子比特）和执行太多的复杂动作（门）才能解决一个本并不大的问题。

新方案：HUBO

该论文引入了一种更聪明的方法，称为 HUBO（高阶无约束二进制优化）。

你可以把 HUBO 想象成使用压缩袋来打包同样的行李。与其给每件物品一个巨大的盒子，不如使用一种紧凑的二进制编码（类似于数字压缩包）来表示这些选择。

• 更少的盒子： 如果有 10 个选项，HUBO 不需要 10 个盒子。它只需要大约 4 个盒子（因为 $2^4 = 16$，足以覆盖 10 个选项）。它能更高效地利用计算机天然的“二进制”语言。
• 没有额外的胶水： 因为编码方式非常聪明，计算机能够自然地理解它一次只能选择一个值。你不需要添加那些沉重、昂贵的惩罚项来防止出错。
• 结果： 指令变得更短，量子计算机也需要更少的部件来完成工作。

他们实际做了什么

研究人员不仅停留在理论层面，还通过三种真实的谜题类型测试了它：

1. 登机口分配 (GAP)： 为飞机分配机场登机口，以最小化乘客步行时间。
2. 图着色 (MkCS)： 为地图涂色，确保相邻区域颜色不同。
3. 整数规划 (IP)： 一个用于资源优化的通用数学问题。

他们使用一种流行的量子算法——QAOA，将旧的“QUBO”方法与他们的新型“HUBO”方法进行了对比。

结果：巨大的胜利

研究结果非常显著。通过切换到 HUBO：

• 所需的部件更少： 他们需要显著更少的量子比特（量子计算机的基本构建模块）。
• 大幅减少的动作次数： 最重要的发现是在“CNOT 门”（量子计算机必须执行的一种特定类型的动作）的数量上。HUBO 方法在所有测试中将这些动作的数量减少了至少 89.6%。在某些情况下，减少幅度接近 100%。
• 更好的解决方案： 不仅运行成本更低，而且即使在给予两种方法相同运行时间的情况下，HUBO 方法也比 QUBO 方法找到了更好的答案。

核心结论

论文得出结论，对于我们现有的（以及即将到来的）量子计算机来说，旧的 QUBO 方法过于笨重且浪费。新的 HUBO 方法是一种更“轻量级”的替代方案，更适合当前的硬件。

为了让其他人也能使用这项技术，作者还发布了一个免费的开源软件工具（一个名为 PyHUBO 的 Python 库），它可以自动将这些复杂的题目转化为高效的 HUBO 格式，以便其他科学家和工程师能立即开始使用这种节省资源的方法。

简而言之： 他们找到了一种缩减求解复杂谜题的量子指令的方法，这使得我们在当今的量子计算机上真正解决现实世界问题的可能性大大增加。

技术摘要

技术摘要：通过高阶编码实现资源高效的量子优化

问题陈述
组合优化问题（COPs）是涵盖从物流到计算生物学等诸多领域的中心问题，但这些问题通常是 NP-hard 的，这使得随着问题规模的增长，它们对于经典求解器而言在计算上是难以处理的。量子算法，特别是量子近似优化算法（QAOA），为应对这些挑战提供了一条潜在途径。然而，目前的量子方法经常受到二次无约束二进制优化（QUBO）形式化表达中资源需求的限制。标准的 QUBO 编码（如 One-Hot 编码）所需的量子比特数量与变量数量 ($n$) 和每个变量的可能取值数量 ($m$) 呈线性关系，即 $n \times m$ 个量子比特。此外，在 QUBO 中强制执行约束通常需要庞大的惩罚项，这会增加电路深度和双比特 CNOT 门的计数，使得许多实际问题在近期的量子硬件上变得难以实现。

方法论
作者提出了一个利用高阶无约束二进制优化（HUBO）来缓解这些资源约束的系统性框架。该方法包含三个主要组成部分：

1. 二进制编码与 One-Hot 编码： 不同于 One-Hot 编码（其中每个变量-取值对都是一个独立的量子比特），作者采用了二进制编码。在此，每个变量 $i$ 由一个紧凑的二进制寄存器表示，其长度为 $d = \lceil \log_2(m) \rceil$ 位。这使得量子比特需求从 $n \times m$ 降低到了 $n \times \lceil \log_2(m) \rceil$。
2. HUBO 哈密顿量构建： 作者证明了这种二进制编码自然地导致了包含高阶相互作用项（最高达 $2 \times d$ 阶）的 HUBO 哈密顿量。与 QUBO 需要通过惩罚项来强制执行“One-Hot”约束（即一个变量只能取一个值）不同，二进制编码本身就天然符合单值分配。约束（例如 $s_i \neq s_j$）可以直接整合进哈密顿量中，或通过不需要扩展变量空间的惩罚项来实现。
3. 电路编译： 虽然高阶项在形式上意味着多量子比特相互作用，但作者展示了这些项可以完全被编译为标准的单比特和双比特门。他们利用基于格雷码（Gray-code）的电路合成方法（遵循 Welch 等人的研究）来实现代价算符 $e^{-i\gamma \hat{H}_C}$。这种方法通过利用为一项生成的奇偶校验态来辅助构建其他项，从而最大限度地减少冗余操作，确保渐近 CNOT 门计数按 $O(n^2 m^2)$ 缩放，这与 QUBO 相当，但在实践中具有显著更低的常数因子。

作者还引入了 PyHUBO，这是一个开源 Python 库，用于自动构建 HUBO 哈密顿量并利用 Walsh-Hadamard 变换计算其系数，确保数值复杂度随问题规模呈多项式级缩放。

核心贡献

• 系统性框架： 一种将组合优化问题映射到使用二进制编码的 HUBO 哈密顿量的通用方法，适用于具有 One-Hot 或相关约束的问题。
• 资源缩减： 证明了 HUBO 形式化表达显著降低了量子比特数量，并且至关重要的是，降低了执行 QAOA 所需的总 CNOT 门数量。
• 软件工具： 发布了 PyHUBO，以促进 HUBO 模型在量子社区中的应用。
• 基准测试： 在三个截然不同的 COP 类（门分配问题 GAP、最大 k-可着色子图 MkCS 以及整数规划 IP）中进行了全面的评估。

结果
作者在选定的三个问题类上使用 QUBO 和 HUBO 编码对 QAOA 进行了基准测试。结果表明 HUBO 在资源方面具有显著优势：

• 量子比特效率： HUBO 将量子比特需求从 $O(nm)$降低到$O(n \log m)$。
• 门计数减少： 对于所有测试实例，HUBO 将总 CNOT 门计数至少降低了 89.6%。在特定案例中（如整数规划基准测试），降幅高达 97.1%。
• 解的质量： 对于固定层数的 QAOA，HUBO-QAOA 始终比 QUBO-QAOA 获得更好的近似比（更接近最优解）。例如，在 GAP 基准测试中，HUBO 实现的平均目标值为 12.1 分钟，而 QUBO 为 15.8 分钟。
• 收敛性： HUBO-QAOA 以显著更少的总门数达到了目标近似比。在 IP 基准测试中，HUBO 在 1 层时就达到了 0.60 的目标比，而 QUBO 则需要 10 层，导致 QUBO 消耗了 31.6 倍的 CNOT 门和 24.5 倍的 RZ 门。
• 可扩展性： HUBO 的资源优势随着问题规模的增大而持续存在甚至增强；当 QUBO-QAOA 因过高的资源需求而变得在计算上不可行时，HUBO 仍能保持可行性。

意义
本文认为，HUBO 形式化表达为近期设备的量子优化提供了一种切实可行的替代方案。与“高阶相互作用会增加硬件需求”的直觉相反，作者展示了消除惩罚项和压缩变量表示反而能带来电路复杂度的净减少。通过显著降低量子比特和 CNOT 的需求，HUBO 编码有助于缓解目前限制量子算法应用于现实工业问题的资源瓶颈。作者总结道，随着量子技术的进步和问题规模的扩大，这种资源高效的方法变得愈发重要，从而使工业界和研究领域的应用变得更加可行。