  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
