Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2201.10110 · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings

A Hybrid Quantum-Classical Algorithm for Robust Fitting

Anh-Dzung Doan, Michele Sasdelli, David Suter, Tat-Jun Chin

Published Jun 1, 2022• 32 citations
arXivHTMLPDF

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

DOI
10.1109/cvpr52688.2022.00051

Related papers

Outlier-Robust Multi-Model Fitting on Quantum Annealers

Saurabh Pandey, Luca Magri, Federica Arrigoni +1 more

Multi-model fitting (MMF) presents a significant challenge in Computer Vision, particularly due to its combinatorial nature. While recent advancements in quantum computing offer promise for addressing NP-hard problems, existing quantum-based approaches for model fitting are either limited to a single model or consider multi-model scenarios within outlier-free datasets. This paper introduces a novel approach, the robust quantum multi-model fitting (R-QuMF) algorithm, designed to handle outliers effectively. Our method leverages the intrinsic capabilities of quantum hardware to tackle combinatorial challenges inherent in MMF tasks, and it does not require prior knowledge of the exact number of models, thereby enhancing its practical applicability. By formulating the problem as a maximum set coverage task for adiabatic quantum computers (AQC), R-QuMF outperforms existing quantum techniques, demonstrating superior performance across various synthetic and real-world 3D datasets. Our findings underscore the potential of quantum computing in addressing the complexities of MMF, especially in real-world scenarios with noisy and outlier-prone data11Project page: https://4dqv.mpi-inf.mpg.de/RQMMF/.

IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)•Jun 11, 2025•1 citation

Quantum Multi-Model Fitting

Matteo Farina, Luca Magri, Willi Menapace +3 more

Geometric model fitting is a challenging but fundamental computer vision problem. Recently, quantum optimization has been shown to enhance robust fitting for the case of a single model, while leaving the question of multi-model fitting open. In response to this challenge, this paper shows that the latter case can significantly benefit from quantum hardware and proposes the first quantum approach to multimodel fitting (MMF). We formulate MMF as a problem that can be efficiently sampled by modern adiabatic quantum computers without the relaxation of the objective function. We also propose an iterative and decomposed version of our method, which supports real-world-sized problems. The experimental evaluation demonstrates promising results on a variety of datasets. The source code is available at: https://github.com/FarinaMatteo/qmmf.

arXiv:2303.15444•IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings•Jun 1, 2023•14 citations

Quantum Annealing for Computer Vision Minimization Problems

Shahrokh Heidari, Michael J. Dinneen, Patrice Jean Delmas

Computer Vision (CV) labelling algorithms play a pivotal role in the domain of low-level vision. For decades, it has been known that these problems can be elegantly formulated as discrete energy minimization problems derived from probabilistic graphical models (such as Markov Random Fields). Despite recent advances in inference algorithms (such as graph-cut and message-passing algorithms), the resulting energy minimization problems are generally viewed as intractable. The emergence of quantum computations, which offer the potential for faster solutions to certain problems than classical methods, has led to an increased interest in utilizing quantum properties to overcome intractable problems. Recently, there has also been a growing interest in Quantum Computer Vision (QCV), with the hope of providing a credible alternative or assistant to deep learning solutions in the field. This study investigates a new Quantum Annealing based inference algorithm for CV discrete energy minimization problems. Our contribution is focused on Stereo Matching as a significant CV labeling problem. As a proof of concept, we also use a hybrid quantum-classical solver provided by D-Wave System to compare our results with the best classical inference algorithms in the literature.

arXiv:2312.12848•Dec 20, 2023•1 citation

Quantum Robustness Verification: A Hybrid Quantum-Classical Neural Network Certification Algorithm

Nicola Franco, Tom Wollschläger, Nicholas Gao +2 more

In recent years, quantum computers and algorithms have made significant progress indicating the prospective importance of quantum computing (QC). Especially combinatorial optimization has gained a lot of attention as an application field for near-term quantum computers, both by using gate-based QC via the Quantum Approximate Optimization Algorithm and by quantum annealing using the Ising model. However, demonstrating an advantage over classical methods in real-world applications remains an active area of research. In this work, we investigate the robustness verification of ReLU networks, which involves solving many-variable mixed-integer programs (MIPs), as a practical application. Classically, complete verification techniques struggle with large networks as the combinatorial space grows exponentially, implying that realistic networks are difficult to be verified by classical methods. To alleviate this issue, we propose to use QC for neural network verification and introduce a hybrid quantum procedure to compute provable certificates. By applying Benders decomposition, we split the MIP into a quadratic unconstrained binary optimization and a linear program which are solved by quantum and classical computers, respectively. We further improve existing hybrid methods based on the Benders decomposition by reducing the overall number of iterations and placing a limit on the maximum number of qubits required. We show that, in a simulated environment, our certificate is sound, and provides bounds on the minimum number of qubits necessary to approximate the problem. Finally, we evaluate our method within simulations and on quantum hardware.

arXiv:2205.00900•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•29 citations

Quantum Annealing for Computer Vision minimization problems

Shahrokh Heidari, Michael J. Dinneen, Patrice Jean Delmas

Computer Vision (CV) labeling problems play a pivotal role in low-level vision. For decades, it has been known that these problems can be elegantly formulated as discrete energy-minimization problems derived from probabilistic graphical models such as Markov Random Fields (MRFs). Despite recent advances in MRF inference algorithms (such as graph-cut and message-passing methods), the resulting energy-minimization problems are generally viewed as intractable. The emergence of quantum computations, which offer the potential for faster solutions to certain problems than classical methods, has led to an increased interest in utilizing quantum properties to overcome intractable problems. Recently, there has also been a growing interest in Quantum Computer Vision (QCV), hoping to provide a credible alternative/assistant to deep learning solutions. This study investigates a new Quantum Annealing-based inference algorithm for CV discrete energy minimization problems. Our contribution is focused on Stereo Matching as a significant CV labeling problem. As a proof of concept, we also use a hybrid quantum–classical solver provided by D-Wave System to compare our results with the best classical inference algorithms in the literature. Our results show that Quantum Annealing can yield promising results for Stereo Matching problems, with improved accuracy on certain stereo images and competitive performance on others.

Future Generation Computer Systems•May 24, 2024•7 citations

Hybrid Quantum-Classical Algorithms for Quantum Computing Applications in Computational Physics

Julian Schuhmacher

Computational methods are central to modern physics, yet many problems, especially those involving Quantum Many-Body Systems (QMBSs), remain challenging at scale. The core difficulty of simulating QMBSs is the exponential growth of the solution space with system size. This renders exact treatments intractable and pushes approximate methods to their limits when tackling two- and higher-dimensional systems and long-time dynamics. Quantum computers offer a quantum-native platform for representing and manipulating such systems. Recent algorithmic and technological advancements have enabled experiments on quantum processors in the quantum utility regime, a scale at which exact classical reproduction is no longer feasible. This represents the first step towards realizing quantum advantage, where quantum computers solve specific, practically relevant problems more efficiently than any classical approach. While advancing towards the goal of quantum advantage, useful computations on quantum processors are expected to be realised through hybrid quantum-classical algorithms, which combine quantum experiments and classical computational resources. A prominent example are variational quantum algorithms, where a Parametrized Quantum Circuit (PQC) prepares a trial quantum state whose parameters are iteratively updated by a classical optimisation routine to minimize a target cost function (e.g., the energy of a target Hamiltonian). However, the optimisation of such PQCs is affected by trainability issues, such as barren plateaus in the parameter landscape, which can render the optimisation increasingly difficult for larger system sizes. This motivates the development of novel hybrid approaches overcoming the limits of PQCs. In this thesis, we introduce a new class of approaches based on hybrid Tensor Networks (TNs). A hybrid TN is obtained by integrating quantum states prepared on a quantum processor within TNs -- one of the state-of-the-art approaches for simulating quantum systems. We first show how hybrid TNs can be used for ground-state searches within a variational setting. Then, we further extend the framework to non-variational hybrid TN ansätze for which the quantum tensors are prepared via quantum annealing and subsequently post-processed by classical TNs. In the context of quantum machine learning, which also relies on PQCs, we further investigate heuristic best practices that mitigate the same exponential concentration effects in kernel-based models for anomaly detection. Another class of hybrid algorithms are quantum error-mitigation workflows, where classical post-processing is used to reconstruct expectation values from noise-affected circuit executions. Such methods generally feature a trade-off between the bias and the variance: the price to pay for mitigating noise in a bias-free fashion is that the number of measurements usually grows exponentially with the depth of the circuit in order to achieve a fixed accuracy. In this thesis, we develop a low-resource error-mitigation strategy that reduces the measurement overhead in practical digital Hamiltonian-simulation workflows. We apply this method to Trotterized dynamics in a lattice-gauge-theory model, enabling the extraction of expectation values with improved accuracy at time-scales that allow the observation of post-collision scattering dynamics.

•Jan 1, 2026•0 citations
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 simulation11Source code: https://github.com/dadung/HQC-robust-fitting.
Multi-model fitting (MMF) presents a significant challenge in Computer Vision, particularly due to its combinatorial nature. While recent advancements in quantum computing offer promise for addressing NP-hard problems, existing quantum-based approaches for model fitting are either limited to a single model or consider multi-model scenarios within outlier-free datasets. This paper introduces a novel approach, the robust quantum multi-model fitting (R-QuMF) algorithm, designed to handle outliers effectively. Our method leverages the intrinsic capabilities of quantum hardware to tackle combinatorial challenges inherent in MMF tasks, and it does not require prior knowledge of the exact number of models, thereby enhancing its practical applicability. By formulating the problem as a maximum set coverage task for adiabatic quantum computers (AQC), R-QuMF outperforms existing quantum techniques, demonstrating superior performance across various synthetic and real-world 3D datasets. Our findings underscore the potential of quantum computing in addressing the complexities of MMF, especially in real-world scenarios with noisy and outlier-prone data11Project page: https://4dqv.mpi-inf.mpg.de/RQMMF/.
Geometric model fitting is a challenging but fundamental computer vision problem. Recently, quantum optimization has been shown to enhance robust fitting for the case of a single model, while leaving the question of multi-model fitting open. In response to this challenge, this paper shows that the latter case can significantly benefit from quantum hardware and proposes the first quantum approach to multimodel fitting (MMF). We formulate MMF as a problem that can be efficiently sampled by modern adiabatic quantum computers without the relaxation of the objective function. We also propose an iterative and decomposed version of our method, which supports real-world-sized problems. The experimental evaluation demonstrates promising results on a variety of datasets. The source code is available at: https://github.com/FarinaMatteo/qmmf.
Computer Vision (CV) labelling algorithms play a pivotal role in the domain of low-level vision. For decades, it has been known that these problems can be elegantly formulated as discrete energy minimization problems derived from probabilistic graphical models (such as Markov Random Fields). Despite recent advances in inference algorithms (such as graph-cut and message-passing algorithms), the resulting energy minimization problems are generally viewed as intractable. The emergence of quantum computations, which offer the potential for faster solutions to certain problems than classical methods, has led to an increased interest in utilizing quantum properties to overcome intractable problems. Recently, there has also been a growing interest in Quantum Computer Vision (QCV), with the hope of providing a credible alternative or assistant to deep learning solutions in the field. This study investigates a new Quantum Annealing based inference algorithm for CV discrete energy minimization problems. Our contribution is focused on Stereo Matching as a significant CV labeling problem. As a proof of concept, we also use a hybrid quantum-classical solver provided by D-Wave System to compare our results with the best classical inference algorithms in the literature.
In recent years, quantum computers and algorithms have made significant progress indicating the prospective importance of quantum computing (QC). Especially combinatorial optimization has gained a lot of attention as an application field for near-term quantum computers, both by using gate-based QC via the Quantum Approximate Optimization Algorithm and by quantum annealing using the Ising model. However, demonstrating an advantage over classical methods in real-world applications remains an active area of research. In this work, we investigate the robustness verification of ReLU networks, which involves solving many-variable mixed-integer programs (MIPs), as a practical application. Classically, complete verification techniques struggle with large networks as the combinatorial space grows exponentially, implying that realistic networks are difficult to be verified by classical methods. To alleviate this issue, we propose to use QC for neural network verification and introduce a hybrid quantum procedure to compute provable certificates. By applying Benders decomposition, we split the MIP into a quadratic unconstrained binary optimization and a linear program which are solved by quantum and classical computers, respectively. We further improve existing hybrid methods based on the Benders decomposition by reducing the overall number of iterations and placing a limit on the maximum number of qubits required. We show that, in a simulated environment, our certificate is sound, and provides bounds on the minimum number of qubits necessary to approximate the problem. Finally, we evaluate our method within simulations and on quantum hardware.
Computer Vision (CV) labeling problems play a pivotal role in low-level vision. For decades, it has been known that these problems can be elegantly formulated as discrete energy-minimization problems derived from probabilistic graphical models such as Markov Random Fields (MRFs). Despite recent advances in MRF inference algorithms (such as graph-cut and message-passing methods), the resulting energy-minimization problems are generally viewed as intractable. The emergence of quantum computations, which offer the potential for faster solutions to certain problems than classical methods, has led to an increased interest in utilizing quantum properties to overcome intractable problems. Recently, there has also been a growing interest in Quantum Computer Vision (QCV), hoping to provide a credible alternative/assistant to deep learning solutions. This study investigates a new Quantum Annealing-based inference algorithm for CV discrete energy minimization problems. Our contribution is focused on Stereo Matching as a significant CV labeling problem. As a proof of concept, we also use a hybrid quantum–classical solver provided by D-Wave System to compare our results with the best classical inference algorithms in the literature. Our results show that Quantum Annealing can yield promising results for Stereo Matching problems, with improved accuracy on certain stereo images and competitive performance on others.
Computational methods are central to modern physics, yet many problems, especially those involving Quantum Many-Body Systems (QMBSs), remain challenging at scale. The core difficulty of simulating QMBSs is the exponential growth of the solution space with system size. This renders exact treatments intractable and pushes approximate methods to their limits when tackling two- and higher-dimensional systems and long-time dynamics. Quantum computers offer a quantum-native platform for representing and manipulating such systems. Recent algorithmic and technological advancements have enabled experiments on quantum processors in the quantum utility regime, a scale at which exact classical reproduction is no longer feasible. This represents the first step towards realizing quantum advantage, where quantum computers solve specific, practically relevant problems more efficiently than any classical approach. While advancing towards the goal of quantum advantage, useful computations on quantum processors are expected to be realised through hybrid quantum-classical algorithms, which combine quantum experiments and classical computational resources. A prominent example are variational quantum algorithms, where a Parametrized Quantum Circuit (PQC) prepares a trial quantum state whose parameters are iteratively updated by a classical optimisation routine to minimize a target cost function (e.g., the energy of a target Hamiltonian). However, the optimisation of such PQCs is affected by trainability issues, such as barren plateaus in the parameter landscape, which can render the optimisation increasingly difficult for larger system sizes. This motivates the development of novel hybrid approaches overcoming the limits of PQCs. In this thesis, we introduce a new class of approaches based on hybrid Tensor Networks (TNs). A hybrid TN is obtained by integrating quantum states prepared on a quantum processor within TNs -- one of the state-of-the-art approaches for simulating quantum systems. We first show how hybrid TNs can be used for ground-state searches within a variational setting. Then, we further extend the framework to non-variational hybrid TN ansätze for which the quantum tensors are prepared via quantum annealing and subsequently post-processed by classical TNs. In the context of quantum machine learning, which also relies on PQCs, we further investigate heuristic best practices that mitigate the same exponential concentration effects in kernel-based models for anomaly detection. Another class of hybrid algorithms are quantum error-mitigation workflows, where classical post-processing is used to reconstruct expectation values from noise-affected circuit executions. Such methods generally feature a trade-off between the bias and the variance: the price to pay for mitigating noise in a bias-free fashion is that the number of measurements usually grows exponentially with the depth of the circuit in order to achieve a fixed accuracy. In this thesis, we develop a low-resource error-mitigation strategy that reduces the measurement overhead in practical digital Hamiltonian-simulation workflows. We apply this method to Trotterized dynamics in a lattice-gauge-theory model, enabling the extraction of expectation values with improved accuracy at time-scales that allow the observation of post-collision scattering dynamics.