如果你一直关注量子计算的发展，你可能知道我们正处于 “NISQ” 时代 (含噪中型量子) 。虽然通用、容错的量子计算机尚在未来，但我们目前可以获得量子退火机 (比如 D-Wave 的那些) 。这些机器是专门设计的硬件，用于寻找系统的最低能量状态，这使它们成为组合优化的潜在强大工具。

然而，这里有一个问题。现代量子退火机实际上只讲一种语言: QUBO (二次无约束二值优化) 。

如果你的问题能完美契合 QUBO 形式，那很好！但许多现实世界的问题，特别是计算机视觉中的问题——比如对齐 3D 形状或匹配图结构——都很复杂。它们通常涉及非二次目标函数或复杂的约束 (比如要求矩阵必须是有效的旋转矩阵) 。传统上，这意味着这些问题对量子退火机来说是禁区。

在这篇文章中，我们将深入探讨 QuCOOP , 这是锡根大学和马普信息学研究所的研究人员提出的一个框架。QuCOOP (用于复合及二值参数化优化问题的量子框架) 提出了一种巧妙的迭代方法，以弥合复杂的非二次计算机视觉问题与当今受限于 QUBO 的硬件之间的鸿沟。

QuCOOP 框架与标准方法的对比概览。(a) 部分展示了迭代线性化策略。(b) 和 (c) 部分展示了在点集配准和网格对齐中的应用。

问题所在: QUBO 瓶颈

要理解 QuCOOP 的创新之处，我们首先需要理解它解决的局限性。绝热量子计算 (AQC) 利用量子力学 (特别是隧道效应和叠加态) 来探索优化景观，并比经典方法更好地逃离局部极小值。

然而，硬件通常只接受这种特定形式的问题:

标准的 QUBO 公式。

这里，\(x\) 是一个二值向量 (0 和 1) ，\(Q\) 是定义变量间关系的矩阵，目标是最小化该函数。

当我们审视计算机视觉问题时，问题就出现了。假设你想对齐两个 3D 点云。你需要找到一个旋转矩阵和一个置换矩阵。这些矩阵有严格的约束 (正交性，行和为 1) ，并且通常以非二次方式相互作用。你不能简单地将这些直接输入到 D-Wave 机器中。

解决方案: 复合优化

QuCOOP 的作者们通过将一般问题构建为复合优化问题来解决这一难题。他们不试图一次性将整个复杂问题强行塞入单个 QUBO，而是将目标函数 \(f\) 视为另一个内部函数 \(g(x)\) 的函数。

数学上，他们的目标是求解:

复合优化问题公式。

其中:

  • \(x\) 是我们的二值参数向量 (与量子机器兼容) 。
  • \(g(x)\) 将这些二值参数映射到复杂的各个可行集 (比如一组旋转矩阵) 。
  • \(f\) 是我们要最小化的目标函数。

QuCOOP 算法

QuCOOP 的核心洞见是迭代线性化 。 该框架不是一次性求解困难的复合函数，而是创建一系列本身就是 QUBO 的局部近似。

具体步骤逻辑如下:

  1. 当前状态: 假设我们对解有一个当前猜测 \(x^t\)。
  2. 线性化: 我们在 \(x^t\) 附近使用一阶泰勒展开来近似内部函数 \(g(x)\)。
  3. 二次模型: 因为外部函数 \(f\) 是二次的 (能量最小化问题的常见特征) ，将 \(g(x)\) 的线性近似代入其中会产生关于 \(x\) 的二次函数。
  4. 生成 QUBO: 这个局部二次模型就是一个 QUBO！量子退火机现在可以求解它来找到下一个最佳步骤 \(x^{t+1}\)。

每一步构建的局部模型 \(f^t\) 如下所示:

使用泰勒展开的局部模型定义。

该算法迭代求解这些局部 QUBO。它就像是针对离散变量的梯度下降，利用量子计算机在局部景观中找到最佳的“一步”。

完整的迭代更新规则总结为以下方程:

QuCOOP 迭代更新规则。

为了使其具体化，该框架推导出了量子退火机在每次迭代中需要编程的具体矩阵 \(Q^t\) 和向量 \(c^t\):

局部 QUBO 矩阵和偏置向量的显式公式。

应用 1: 图匹配和 QAP

最困难的组合问题之一是二次分配问题 (QAP) 。 本质上，这是在两个图之间匹配节点以最小化结构差异的问题。

目标通常看起来像是最小化两个邻接矩阵 \(A\) 和 \(B\) 在矩阵 \(P\) 置换下的差异:

标准图匹配目标函数。

这里的约束是 \(P\) 必须是一个置换矩阵 (由 0 和 1 组成的矩阵，其中每一行和每一列的和恰好为 1) 。

置换的二值参数化

量子退火机使用的是比特，而不是矩阵。我们如何用二值变量表示置换矩阵？

QuCOOP 使用了一种巧妙的分解方法。任何置换都可以由一系列“交换” (对换) 构建而成。研究人员将置换矩阵 \(P\) 参数化为 2-循环 (交换) 的乘积，其中每次交换由一个二值变量 \(x_i\) 开启或关闭。

使用二值变量对置换矩阵进行参数化。

通过优化这些二值变量 \(x\)，算法构建出最优的置换矩阵。为了确保结果保持为有效的置换，他们在 QUBO 中添加了一个惩罚项来惩罚无效的情况。

由此产生的量子退火机局部子问题变为:

图匹配的 QUBO 公式。

应用 2: 点集配准

也许 QuCOOP 最令人印象深刻的应用是无对应关系的点集配准 。 这是一个经典的视觉问题: 你有两团点云，你想旋转并重新排列其中一个，使其与另一个对齐。

大多数以前的量子方法假设你已经知道哪个点与哪个点匹配 (已知对应关系) 。QuCOOP 同时求解旋转 (\(R\)) 和置换 (\(P\))。

目标函数结合了寻找最佳旋转和最佳匹配:

联合旋转和置换优化的目标函数。

这是一个复合问题，变量被分为旋转参数和置换参数。研究人员对两者都进行了线性化。旋转矩阵使用斜对称矩阵的指数映射 (李代数中的标准做法) 进行参数化，然后离散化为比特。

由此产生的量子退火机 QUBO 矩阵是一个分块矩阵，处理旋转变量与置换变量之间的相互作用:

点集配准的分块矩阵 QUBO。

左上块处理置换约束 (\(\alpha I\))，右下块处理旋转约束 (\(\beta I\))，非对角块 (\(\mathbf{X} \otimes \mathbf{Y}\)) 处理耦合——即旋转点如何影响匹配成本。

实验结果

研究人员在经典模拟器 (模拟退火 - SA) 和真实的量子硬件 (D-Wave) 上都测试了 QuCOOP。

1. 二次分配问题 (QAP)

他们将 QuCOOP 与经典启发式算法 (FAQ, 2-OPT) 以及一种称为 Q-Match 的专用量子方法进行了比较。他们使用了 QAPLIB 基准，这是此类问题的标准库。

结果具有统计学意义。如下图所示，QuCOOP (蓝色菱形) 在不同问题规模 (\(n\)) 下始终实现了最低的能量误差 (y 轴，对数刻度) 。

QAPLIB 上的基准测试结果显示 QuCOOP 具有更优的能量误差表现。

虽然运行时间 (下图) 略高于最快的启发式算法，但精度的回报是巨大的。

2. 形状匹配

他们将该方法应用于 FAUST 数据集，该数据集涉及映射不同姿态的人体高分辨率网格。这是一个巨大的 QAP 实例。

定性结果表明，QuCOOP 成功处理了复杂的变形，准确地将参考形状的点匹配到目标形状。

FAUST 数据集上的定性结果显示网格对齐成功。

在定量精度 (测地线误差) 方面，QuCOOP 的表现略优于之前的最先进量子方法 Q-Match，证明了通用框架与专用求解器一样能干。

形状匹配的能量下降和测地线误差的定量图表。

3. 点集配准 (“不可能”的任务)

这个实验突出了 QuCOOP 的多功能性。任务是在不知道点之间对应关系的情况下配准 2D 和 3D 点集——这是以前的量子方法无法处理的任务。

下面的视觉结果展示了对齐过程。从“初始”的混乱状态，QuCOOP 将蓝色十字 (模板) 与橄榄色方块 (参考) 对齐。

2D 和 3D 点集配准的视觉结果。

值得注意的是该方法在旋转角度方面的鲁棒性。随着对齐形状所需的旋转增加 (接近 180 度) ，问题变得更难。下图将 QuCOOP 与 CPD (相干点漂移，一种标准的经典算法) 进行了比较。QuCOOP 保持了竞争力，尽管两者在极端旋转下都很吃力 (这是局部优化的已知难点) 。

显示配准误差与旋转角度关系的图表。

真实量子硬件性能

终极测试是在物理 D-Wave 量子退火机上运行此算法。研究人员使用了 D-Wave Advantage 系统。

对于 QAP , D-Wave 机器成功找到了问题规模最大达 \(n=12\) 的有效置换矩阵。

QAP 的 D-Wave 硬件结果，显示在较小 n 值下找到了有效置换。

对于点集配准 , 硬件在无对应关系的情况下成功配准了最大达 \(n=5\) 的点集。

点集配准的 D-Wave 硬件结果。

为什么规模这么小？当前的量子退火机连通性有限。逻辑变量 (这些问题所需要的) 的全连接图必须“嵌入”到量子比特的稀疏物理网格上。这种嵌入使得所需的物理量子比特数量爆炸式增长。随着硬件连通性的改善，这些规模自然会扩大。

结论

QuCOOP 代表了量子计算机视觉向前迈出的重要一步。它打破了“QUBO 屏障”，允许研究人员使用量子退火机解决复合、受约束和非二次问题。

通过使用迭代方法——线性化旋转和置换的复杂几何结构，并将局部 QUBO 模型输入量子求解器——QuCOOP 在图匹配上取得了最先进的结果，并实现了以前量子算法无法企及的点集配准任务。

虽然目前的硬件限制了物理上可解决的问题规模，但像 QuCOOP 这样的框架正在奠定算法基础。随着量子硬件的成熟，我们现在已经准备好了软件工具，以一种根本上全新的方式来处理复杂的视觉问题。