Optimized QUBO formulation methods for quantum computing

这是一份关于论文《Optimized QUBO formulation methods for quantum computing》（量子计算的优化 QUBO 公式化方法）的详细技术总结。

1. 研究背景与问题 (Problem)

核心挑战：
噪声中等规模量子（NISQ）设备（如量子退火器）在处理组合优化问题时，受到可用量子比特数量和连接性的严格限制。许多 NP 难问题需要转化为二次无约束二进制优化（QUBO）形式才能在量子设备上求解。

现有方法的局限性：
将带约束的优化问题转化为 QUBO 形式通常需要使用**松弛变量（slack variables）**来将不等式约束转化为等式约束。

• 变量膨胀： 标准方法（Standard Method）通常根据约束的数值范围线性或对数地增加松弛变量的数量。这导致 QUBO 问题中的总变量数（逻辑变量 + 松弛变量）急剧增加，往往超过 NISQ 设备的承载能力。
• 连接性要求高： 更多的变量意味着更复杂的变量间连接，而量子硬件的拓扑结构（如 Pegasus 或 Zephyr 拓扑）有限，需要大量的“链（chains）”来映射变量，进一步消耗资源并降低求解质量。
• 近似与迭代： 现有的替代方案（如 ADMM 或增广拉格朗日法）通常需要求解预处理的 QUBO 问题或近似原始约束，增加了计算复杂度或牺牲了精度。

研究目标：
开发一种新的方法，能够显著减少将约束优化问题转化为 QUBO 形式所需的松弛变量数量，从而在现有的 NISQ 设备上求解更大规模、更复杂的优化问题，而无需近似原始问题。

2. 方法论 (Methodology)

作者提出了两种相互独立但可结合使用的核心技术：迭代二次多项式法（Iterative Quadratic Polynomial, IQP）和主 - 卫星法（Master-Satellite, MS）。

A. 迭代二次多项式法 (IQP Method)

• 核心思想： 不再使用标准的“平方惩罚项 + 松弛变量”形式（即 $-(IC(x) + S(s))^2$），而是直接构建一个通用的二次多项式 $P(x, s)$，使其在满足约束时取值为 0，在违反约束时取值为 $\le -1$。
• 迭代过程：
  1. 首先尝试不使用任何松弛变量，求解线性方程组以确定多项式系数。
  2. 如果无解，则逐步增加松弛变量的数量，直到找到满足条件的多项式。
  3. 利用松弛变量提供的额外自由度，使得多项式能够更灵活地满足约束条件。
• 优势： 对于定义在少量二进制变量上的约束（特别是非线性或非整数参数约束），IQP 法往往能用极少的松弛变量甚至零松弛变量实现约束编码。此外，生成的多项式通常是稀疏的（许多系数为 0），降低了量子比特间的连接需求。

B. 主 - 卫星法 (Master-Satellite, MS Method)

• 核心思想： 针对共享同一组二进制变量的多个约束，利用它们之间的依赖关系。
  • 主约束（Master Constraint）： 对所有可能的变量组合进行严格编码（必须满足）。
  • 卫星约束（Satellite Constraint）： 仅对已经满足主约束的变量组合进行编码。
• 机制：
  • 对于违反主约束的组合，卫星约束的惩罚项可以产生“意外激励”（正值），但这没关系，因为主约束的惩罚项会被放大（通过相对乘数 $\lambda_{MC}$），确保即使有意外激励，违反主约束的总能量仍为负（被惩罚）。
  • 由于卫星约束不需要覆盖所有 $2^M$ 种组合（只需覆盖满足主约束的子集），其所需的松弛变量数量大幅减少。
• 串联扩展： 对于三个或更多共享变量的约束，可以采用串联方式（C1 是 C2 的主，C1+C2 是 C3 的主），进一步减少子约束的数量。

C. 局部约束优化问题 (Locally-Constrained Problems)

• 作者定义了一类特别适合上述方法的问题：约束是逐节点定义的，仅依赖于与该节点相连的边（弧）。
• 在此类问题中，可以将每个节点的约束分组，应用 IQP 和 MS 方法，从而在整个问题规模上实现巨大的变量缩减。

3. 案例研究：最大利润平衡结算 (MPBS)

为了验证方法的有效性，作者将其应用于一个源自金融领域的 NP 难问题：最大利润平衡结算（Max-Profit Balance Settlement, MPBS）。

• 问题描述： 在用户网络中，选择最大价值的应收款子集进行自动结算，需满足两个约束：
  1. CAP/FLOOR： 结算后每个用户的账户余额必须在预设的上限（CAP）和下限（FLOOR）之间。
  2. IN/OUT： 如果用户作为债务人发起支付，必须同时作为债权人接收至少一笔支付（防止单向流动）。
• 标准方法对比：
  • 标准方法中，CAP/FLOOR 约束所需的松弛变量数量取决于 CAP 与 FLOOR 的差值（$\lceil \log_2(1 + CAP - FL) \rceil$）。在真实金融场景中，这个差值可能很大（$10^5 \sim 10^6$），导致每个节点需要 16+ 个松弛变量。
  • IN/OUT 约束的标准方法也依赖于节点的入度和出度，导致大量松弛变量。
• IQPMS 方法应用：
  • 将 IN/OUT 设为主约束，CAP/FLOOR 设为卫星约束。
  • 利用 IQP 方法，对于节点度数（弧数）$N(u) \le 5$ 的情况，IN/OUT 约束无需松弛变量，CAP/FLOOR 约束也仅需 0-2 个松弛变量（甚至为 0）。
  • 结果： 相比标准方法，松弛变量减少了约 90%。

4. 实验结果 (Results)

作者在 D-Wave 的两款量子退火器（Advantage_system4.1 和 Advantage2_prototype1.1）上对生成的 MPBS 实例进行了测试。

• 变量与量子比特节省：

  • 标准方法每增加一条边（Arc）需要约 4.88 个 QUBO 变量，而 IQPMS 方法仅需 1.30 个。
  • 在量子嵌入层面，标准方法每边消耗约 10.5 个物理量子比特，而 IQPMS 方法仅需约 2 个。
  • 松弛变量总数减少了 82.5% 到 95.6%。

• 求解成功率（Success Rate）：

  • 随着问题规模（边数 N）的增加，标准方法的求解成功率急剧下降。
  • IQPMS 方法的成功率显著更高，且随规模下降较慢。
  • 增益倍数： 使用 IQPMS 方法的成功次数是标准方法的 7 倍到 184 倍（取决于实例大小和使用的退火器）。例如，在最大实例上，Advantage2 退火器的成功率提升了 184 倍。

• 硬件对比：

  • 新一代原型机 Advantage2（Zephyr 拓扑，连接度更高）在两种方法下均优于 Advantage_system4.1，但 IQPMS 方法在 Advantage2 上展现出了巨大的潜力，能够处理更大规模的问题。

5. 主要贡献与意义 (Key Contributions & Significance)

1. 范式转变： 提出了一种不依赖近似、不依赖预处理 QUBO 求解的全新约束编码范式。通过直接构造二次多项式和利用约束间的层级关系，从根本上减少了资源需求。
2. 大幅降低资源门槛： 将松弛变量减少了约 90%，使得原本因变量过多而无法在现有 NISQ 设备上运行的金融优化问题（如 MPBS）变得可行。
3. 提升求解质量： 实验证明，更少的变量和更稀疏的连接直接转化为量子退火器更高的最优解发现率。
4. 通用性与扩展性： 该方法不仅适用于线性整数约束，也适用于非线性和非整数参数约束。它特别适用于“局部约束”类问题，这类问题在物流、金融和供应链网络中非常普遍。
5. 实际验证： 通过与真实金融数据集（UniCredit 银行数据）生成的实例结合，并在真实的 D-Wave 硬件上进行验证，证明了该方法在现实世界应用中的巨大潜力。

总结：
这项工作通过引入 IQP 和 MS 方法，解决了量子优化中“变量爆炸”的关键瓶颈。它不仅大幅提升了现有量子硬件的求解能力，还为未来在 NISQ 时代解决大规模、高复杂度的现实世界组合优化问题提供了切实可行的技术路径。