A hybrid quantum-classical algorithm for robust fitting

Author Identifier

David Suter

https://orcid.org/0000-0001-6306-3023

Document Type

Conference Proceeding

Publication Title

Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

Volume

2022-June

First Page

417

Last Page

427

Publisher

IEEE

School

School of Science / Centre for Artificial Intelligence and Machine Learning (CAIML)

RAS ID

54187

Funders

Australian Research Council

Grant Number

ARC Numbers : DP200101675, DP200103448

Comments

Doan, A. D., Sasdelli, M., Suter, D., & Chin, T. J. (2022). A hybrid quantum-classical algorithm for robust fitting. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 417-427. https://doi.org/10.1109/CVPR52688.2022.00051

An open access version of this paper is provided by the Computer Vision Foundation.

Abstract

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 11 Source code: https://github.com/dadung/HQC-robust-fitting.

DOI

10.1109/CVPR52688.2022.00051

Access Rights

free_to_read

Share

 
COinS