论文标题
一种用于健壮拟合的混合量子古典算法
A Hybrid Quantum-Classical Algorithm for Robust Fitting
论文作者
论文摘要
将几何模型拟合到异常值污染的数据非常棘手。许多计算机视觉系统依赖于随机采样启发式方法来解决鲁棒拟合，这不能提供最佳保证和错误范围。因此，开发新的方法可以弥合昂贵的精确解决方案和不提供质量保证的快速启发式方法之间的差距。在本文中，我们提出了一种用于稳健拟合的杂化量子古典算法。我们的核心贡献是一种新颖的鲁棒拟合公式，可以解决一系列整数程序，并使用全局解决方案或误差界限终止。组合子问题可容纳量子退火器，这有助于有效拧紧绑定。虽然我们对量子计算的使用并不能超越可靠拟合的基本棘手性，但通过提供误差界限，我们的算法是对随机启发式方法的实际改进。此外，我们的工作代表了计算机视觉中量子计算的具体应用。我们提出了使用实际量子计算机（D波优势）和通过仿真获得的结果。源代码：https：//github.com/dadung/hqc-robust-fitting
Fitting geometric models onto outlier contaminated data is provably intractable. Many computer vision systems rely on random sampling heuristics to solve robust fitting, which do not provide optimality guarantees and error bounds. It is therefore critical to develop novel approaches that can bridge the gap between exact solutions that are costly, and fast heuristics that offer no quality assurances. In this paper, we propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs and terminates with a global solution or an error bound. The combinatorial subproblems are amenable to a quantum annealer, which helps to tighten the bound efficiently. While our usage of quantum computing does not surmount the fundamental intractability of robust fitting, by providing error bounds our algorithm is a practical improvement over randomised heuristics. Moreover, our work represents a concrete application of quantum computing in computer vision. We present results obtained using an actual quantum computer (D-Wave Advantage) and via simulation. Source code: https://github.com/dadung/HQC-robust-fitting
