# A Hybrid Quantum-Classical Algorithm for Robust Fitting

arXiv: https://arxiv.org/abs/2201.10110 · HTML: https://mlsanity.com/paper/2201.10110/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 76 references that are in the map.
- First posted on arXiv 25 Jan 2022.

## Builds on (most cited first, 26 of 26)

- [DSAC - Differentiable RANSAC for Camera Localization](https://mlsanity.com/paper/1611.05705/) (2016)
- [MAGSAC++, a fast, reliable and accurate robust estimator](https://mlsanity.com/paper/1912.05909/) (2019)
- [Graph-Cut RANSAC](https://mlsanity.com/paper/1706.00984/) (2017)
- [Quantum Variational Autoencoder](https://mlsanity.com/paper/1802.05779/) (2018)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [A practical heuristic for finding graph minors](https://mlsanity.com/paper/1406.2741/) (2014)
- [Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications](https://mlsanity.com/paper/2007.15109/) (2020)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [A Quantum Computational Approach to Correspondence Problems on Point Sets](https://mlsanity.com/paper/1912.12296/) (2019)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [Quantum-soft QUBO Suppression for Accurate Object Detection](https://mlsanity.com/paper/2007.13992/) (2020)
- [Image classification using quantum inference on the D-Wave 2X](https://mlsanity.com/paper/1905.13215/) (2019)
- [Quantum Robust Fitting](https://mlsanity.com/paper/2006.06986/) (2020)
- [Deep Reinforcement Learning for Efficient Measurement of Quantum Devices](https://mlsanity.com/paper/2009.14825/) (2020)
- [Quantum Annealing Formulation for Binary Neural Networks](https://mlsanity.com/paper/2107.02751/) (2021)
- [Fast clique minor generation in Chimera qubit connectivity graphs](https://mlsanity.com/paper/1507.04774/) (2015)
- [Consensus Maximization Tree Search Revisited](https://mlsanity.com/paper/1908.02021/) (2019)
- [Deterministic consensus maximization with biconvex programming](https://mlsanity.com/paper/1807.09436/) (2018)
- [Defining Quantum Neural Networks via Quantum Time Evolution](https://mlsanity.com/paper/1905.10912/) (2019)
- [Image Processing in Quantum Computers](https://mlsanity.com/paper/1812.11042/) (2018)
- [Hypergraph Optimization for Multi-structural Geometric Model Fitting](https://mlsanity.com/paper/2002.05350/) (2020)
- [Unsupervised Learning for Robust Fitting:A Reinforcement Learning Approach](https://mlsanity.com/paper/2103.03501/) (2021)
- [Consensus Maximisation Using Influences of Monotone Boolean Functions](https://mlsanity.com/paper/2103.04200/) (2021)
- [Maximum Consensus Parameter Estimation by Reweighted ℓ1 Methods](https://mlsanity.com/paper/1803.08602/) (2018)
- [Monotone Boolean Functions, Feasibility/Infeasibility, LP-type problems and MaxCon](https://mlsanity.com/paper/2005.05490/) (2020)

## Built on by (most cited first, 16 of 16)

- [Quantum Vision Clustering](https://mlsanity.com/paper/2309.09907/) (2023)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Quantum Multi-Model Fitting](https://mlsanity.com/paper/2303.15444/) (2023)
- [CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes](https://mlsanity.com/paper/2303.16202/) (2023)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Quantum Annealing for Single Image Super-Resolution](https://mlsanity.com/paper/2304.08924/) (2023)
- [3D-QAE: Fully Quantum Auto-Encoding of 3D Point Clouds](https://mlsanity.com/paper/2311.05604/) (2023)
- [Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms](https://mlsanity.com/paper/2510.07317/) (2025)
- [QuAnt: Quantum Annealing with Learnt Couplings](https://mlsanity.com/paper/2210.08114/) (2022)
- [Quantum Annealing for Computer Vision Minimization Problems](https://mlsanity.com/paper/2312.12848/) (2023)
- [Quantum-Hybrid Stereo Matching With Nonlinear Regularization and Spatial Pyramids](https://mlsanity.com/paper/2312.16118/) (2023)
- [Latent Semantic Consensus For Deterministic Geometric Model Fitting](https://mlsanity.com/paper/2403.06444/) (2024)
- [Training Multilayer Perceptrons by Sampling with Quantum Annealers](https://mlsanity.com/paper/2303.12352/) (2023)
- [Outlier-Robust Multi-Model Fitting on Quantum Annealers](https://mlsanity.com/paper/2504.13836/) (2025)
- [Quantum Levenberg--Marquardt Algorithm for optimization in Bundle Adjustment](https://mlsanity.com/paper/2203.02311/) (2022)
- [Event-driven Robust Fitting on Neuromorphic Hardware](https://mlsanity.com/paper/2508.09466/) (2025)

## Abstract (arXiv)

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