具有置换矩阵约束的绝热量子图匹配

最近，功能量子计算机可供研究界使用。它们使研究人员能够研究量子计算在各种计算机视觉任务中的应用。最近的一项研究着眼于组合图匹配，这是视觉计算的一个基本问题。

研究人员展示了如何通过量子退火有效解决小问题实例的二次分配问题，即 NP 难题，这是匹配问题的重要组成部分。它为 3D 计算机视觉中的多种问题类型开辟了道路。

在模拟和真正的绝热量子计算机上进行了数值验证。结果表明，所提出的方法有效地提高了求解具有置换矩阵约束的组合优化问题的成功率。

3D 形状和图像上的匹配问题具有挑战性，因为它们经常被表述为具有置换矩阵约束的组合二次分配问题 (QAP)，这是 NP 难的。在这项工作中，我们解决了新兴量子计算技术的此类问题，并提出了几种 QAP 的重新表述，作为适合在量子硬件上高效执行的无约束问题。我们研究了在可以映射到量子硬件的二次无约束二元优化问题中注入置换矩阵约束的几种方法。我们专注于获得足够的光谱间隙，这进一步增加了在单次运行中测量最优解和有效置换矩阵的概率。我们在量子计算机 D-Wave 2000Q(2^11 量子位，绝热)上进行实验。尽管观察到模拟绝热量子计算与在真实量子硬件上执行之间存在差异，但我们对置换矩阵约束的重新表述提高了数值计算相对于我们实验中其他惩罚方法的鲁棒性。所提出的算法有可能在未来的量子计算架构上扩展到更高维度，这为解决 3D 计算机视觉和图形中的匹配问题开辟了多个新方向。