Robust Fitting on a Gate Quantum Computer
This work addresses robust fitting, a fundamental problem in computer vision, by enabling quantum computing solutions, though it is incremental as it builds on prior quantum methods.
The paper tackles the problem of robust fitting on gate quantum computers by proposing a quantum circuit for the ℓ∞ feasibility test in the 1D case, enabling the first demonstration of quantum robust fitting on a real quantum computer (IonQ Aria) and extending it to higher-dimensional models with experimental validation on benchmark datasets.
Gate quantum computers generate significant interest due to their potential to solve certain difficult problems such as prime factorization in polynomial time. Computer vision researchers have long been attracted to the power of quantum computers. Robust fitting, which is fundamentally important to many computer vision pipelines, has recently been shown to be amenable to gate quantum computing. The previous proposed solution was to compute Boolean influence as a measure of outlyingness using the Bernstein-Vazirani quantum circuit. However, the method assumed a quantum implementation of an $\ell_\infty$ feasibility test, which has not been demonstrated. In this paper, we take a big stride towards quantum robust fitting: we propose a quantum circuit to solve the $\ell_\infty$ feasibility test in the 1D case, which allows to demonstrate for the first time quantum robust fitting on a real gate quantum computer, the IonQ Aria. We also show how 1D Boolean influences can be accumulated to compute Boolean influences for higher-dimensional non-linear models, which we experimentally validate on real benchmark datasets.