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:2312.16118 · International Conference on 3D Vision (3DV)

Quantum-Hybrid Stereo Matching With Nonlinear Regularization and Spatial Pyramids

Cameron Braunstein, Eddy Ilg, Vladislav Golyanik

Published Mar 18, 2024• 3 citations
arXivHTMLPDF

Abstract

Quantum visual computing is advancing rapidly. This paper presents a new formulation for stereo matching with nonlinear regularizers and spatial pyramids on quantum annealers as a maximum a posteriori inference problem that minimizes the energy of a Markov Random Field. Our approach is hybrid (i.e., quantum-classical) and is compatible with modern D-Wave quantum annealers, i.e., it includes a quadratic unconstrained binary optimization (QUBO) objective. Previous quantum annealing techniques for stereo matching are limited to using linear regularizers, and thus, they do not exploit the fundamental advantages of the quantum computing paradigm in solving combinatorial optimization problems. In contrast, our method utilizes the full potential of quantum annealing for stereo matching, as nonlinear regularizers create optimization problems which are $\mathcal{N}\mathcal{P}$-hard. On the Middlebury benchmark, we achieve an improved root mean squared accuracy over the previous state of the art in quantum stereo matching of $2 \%$ and $22.5 \%$ when using different solvers.

DOI
10.1109/3dv62453.2024.00121

Related papers

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•6 citations

An Improved Quantum Solution for the Stereo Matching Problem

Shahrokh Heidari, Mitchell Rogers, Patrice Jean Delmas

As the most computationally intensive part of a stereo vision system, stereo matching has been the focus of intense research activities for the last four decades. We present the first attempts to compare a quantum stereo matching solution with state-of-the-art approaches on the Middlebury stereo datasets. We first looked at quantum annealing computation as a way to interact with the D-Wave quantum computer and then improved the quantum solution to the stereo matching problem found in the literature. Using a line-by-line approach, we traded accuracy off for the qubits availability in the QPU (Quantum Processor Unit). Our findings show that it is possible to obtain results from real-sized images despite the scarcity of physical qubits in the quantum hardware. While the current quantum solution solves a class P stereo matching problem, its real advantage over classical stereo matching algorithms will arise with NP-hard problems which will be the focus of our future research.

International Conference on Image and Vision Computing New Zealand (IVCNZ)•Dec 9, 2021•4 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•0 citations

A QUBO Formulation of the Stereo Matching Problem for D-Wave Quantum Annealers

William Cruz-Santos, Salvador Elías Venegas-Andraca, Marco O. Lanzagorta

In this paper, we propose a methodology to solve the stereo matching problem through quantum annealing optimization. Our proposal takes advantage of the existing Min-Cut/Max-Flow network formulation of computer vision problems. Based on this network formulation, we construct a quadratic pseudo-Boolean function and then optimize it through the use of the D-Wave quantum annealing technology. Experimental validation using two kinds of stereo pair of images, random dot stereograms and gray-scale, shows that our methodology is effective.

Entropy•Oct 12, 2018•21 citations

Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization

Alp Yurtsever, Tolga Birdal, Vladislav Golyanik

We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linearly-constrained, binary optimization problems on quantum annealers (QA). The computational premise of quantum computers has cultivated the re-design of various existing vision problems into quantum-friendly forms. Experimental QA realizations can solve a particular non-convex problem known as the quadratic unconstrained binary optimization (QUBO). Yet a naive-QUBO cannot take into account the restrictions on the parameters. To introduce additional structure in the parameter space, researchers have crafted ad-hoc solutions incorporating (linear) constraints in the form of regularizers. However, this comes at the expense of a hyper-parameter, balancing the impact of regularization. To date, a true constrained solver of quadratic binary optimization (QBO) problems has lacked. Q-FW first reformulates constrained-QBO as a copositive program (CP), then employs Frank-Wolfe iterations to solve CP while satisfying linear (in)equality constraints. This procedure unrolls the original constrained-QBO into a set of unconstrained QUBOs all of which are solved, in a sequel, on a QA. We use D-Wave Advantage QA to conduct synthetic and real experiments on two important computer vision problems, graph matching and permutation synchronization, which demonstrate that our approach is effective in alleviating the need for an explicit regularization coefficient.

arXiv:2203.12633•Mar 23, 2022•1 citation

Solving Combinatorial Optimization Problems in Computer Vision via Quantum Annealing

Marcel Seelbach Benkner

Since the ability of quantum computing to speed up certain, specific computations has a solid theoretical underpinning, it is a natural question to ask if problems in computer vision also benefit from it. This doctoral thesis is in particular concerned with the question if the recently emerging optimization method of quantum annealing is useful for solving combinatorial optimization problems that arise in computer vision. The computer vision problem that is mainly investigated here is the problem of shape matching. The task of shape matching is to obtain the correspondences of two objects in a scene that are described with point clouds. Most often, one is concerned with finding the correspondences for a person who is recorded in 3D two times but with a different pose. The reason why this computer vision problem was picked as an interesting candidate for an application of quantum annealing is because it can be formulated as a difficult combinatorial optimization problem with a quadratic objective. This is close to the type of optimization problem that recent quantum annealing devices try to solve. The biggest difference is that in quantum annealing one a priori has unconstrained problems so that one cannot include equality constraints in the optimization. In the first work of this thesis, multiple methods are presented to overcome this difference and for really small shape matching problems experiments with simulated quantum annealing and with quantum annealing on D-Wave quantum computers were presented. In the second work of this thesis an iterative method was developed so that it was even possible to solve shape matching problems with over 500 vertices. Finally, a third publication looked at problems where one needs to find the correspondences between multiple shapes. Besides applications of quantum annealing for shape matching, this thesis also contains work on solving the motion segmentation problem with quantum annealing and work about integrating a quantum annealer in a neural network to solve computer vision problems. The integration of the quantum annealer in a neural network can also be viewed as the task to learn an appropriate formulation of a computer vision problem in a way that is solvable with a current quantum annealer. Finally, we also present work about an iterative method for compensating limited connectivity in quantum annealing devices. This work has no particular computer vision application in mind, but investigates the performance of the different approaches on Max-Cut problems. The thesis is structured in a cumulative way, so that the individual publications are presented separately. On a broader picture, the works are motivated by the following questions: What could be the impact of quantum annealing on computer vision and how could computer vision algorithms that use quantum annealing look like? And from another perspective: How would the field of computer vision be changed if there were massive advances in building quadratic, unconstrained, binary optimization problem solvers with or even without utilizing quantum computing?

•Jan 1, 2025•0 citations
Quantum visual computing is advancing rapidly. This paper presents a new formulation for stereo matching with nonlinear regularizers and spatial pyramids on quantum annealers as a maximum a posteriori inference problem that minimizes the energy of a Markov Random Field. Our approach is hybrid (i.e., quantum-classical) and is compatible with modern D-Wave quantum annealers, i.e., it includes a quadratic unconstrained binary optimization (QUBO) objective. Previous quantum annealing techniques for stereo matching are limited to using linear regularizers, and thus, they do not exploit the fundamental advantages of the quantum computing paradigm in solving combinatorial optimization problems. In contrast, our method utilizes the full potential of quantum annealing for stereo matching, as nonlinear regularizers create optimization problems which are NP\mathcal{N}\mathcal{P}NP-hard. On the Middlebury benchmark, we achieve an improved root mean squared accuracy over the previous state of the art in quantum stereo matching of 2%2 \%2% and 22.5%22.5 \%22.5% when using different solvers.
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.
As the most computationally intensive part of a stereo vision system, stereo matching has been the focus of intense research activities for the last four decades. We present the first attempts to compare a quantum stereo matching solution with state-of-the-art approaches on the Middlebury stereo datasets. We first looked at quantum annealing computation as a way to interact with the D-Wave quantum computer and then improved the quantum solution to the stereo matching problem found in the literature. Using a line-by-line approach, we traded accuracy off for the qubits availability in the QPU (Quantum Processor Unit). Our findings show that it is possible to obtain results from real-sized images despite the scarcity of physical qubits in the quantum hardware. While the current quantum solution solves a class P stereo matching problem, its real advantage over classical stereo matching algorithms will arise with NP-hard problems which will be the focus of our future research.
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 this paper, we propose a methodology to solve the stereo matching problem through quantum annealing optimization. Our proposal takes advantage of the existing Min-Cut/Max-Flow network formulation of computer vision problems. Based on this network formulation, we construct a quadratic pseudo-Boolean function and then optimize it through the use of the D-Wave quantum annealing technology. Experimental validation using two kinds of stereo pair of images, random dot stereograms and gray-scale, shows that our methodology is effective.
We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linearly-constrained, binary optimization problems on quantum annealers (QA). The computational premise of quantum computers has cultivated the re-design of various existing vision problems into quantum-friendly forms. Experimental QA realizations can solve a particular non-convex problem known as the quadratic unconstrained binary optimization (QUBO). Yet a naive-QUBO cannot take into account the restrictions on the parameters. To introduce additional structure in the parameter space, researchers have crafted ad-hoc solutions incorporating (linear) constraints in the form of regularizers. However, this comes at the expense of a hyper-parameter, balancing the impact of regularization. To date, a true constrained solver of quadratic binary optimization (QBO) problems has lacked. Q-FW first reformulates constrained-QBO as a copositive program (CP), then employs Frank-Wolfe iterations to solve CP while satisfying linear (in)equality constraints. This procedure unrolls the original constrained-QBO into a set of unconstrained QUBOs all of which are solved, in a sequel, on a QA. We use D-Wave Advantage QA to conduct synthetic and real experiments on two important computer vision problems, graph matching and permutation synchronization, which demonstrate that our approach is effective in alleviating the need for an explicit regularization coefficient.
Since the ability of quantum computing to speed up certain, specific computations has a solid theoretical underpinning, it is a natural question to ask if problems in computer vision also benefit from it. This doctoral thesis is in particular concerned with the question if the recently emerging optimization method of quantum annealing is useful for solving combinatorial optimization problems that arise in computer vision. The computer vision problem that is mainly investigated here is the problem of shape matching. The task of shape matching is to obtain the correspondences of two objects in a scene that are described with point clouds. Most often, one is concerned with finding the correspondences for a person who is recorded in 3D two times but with a different pose. The reason why this computer vision problem was picked as an interesting candidate for an application of quantum annealing is because it can be formulated as a difficult combinatorial optimization problem with a quadratic objective. This is close to the type of optimization problem that recent quantum annealing devices try to solve. The biggest difference is that in quantum annealing one a priori has unconstrained problems so that one cannot include equality constraints in the optimization. In the first work of this thesis, multiple methods are presented to overcome this difference and for really small shape matching problems experiments with simulated quantum annealing and with quantum annealing on D-Wave quantum computers were presented. In the second work of this thesis an iterative method was developed so that it was even possible to solve shape matching problems with over 500 vertices. Finally, a third publication looked at problems where one needs to find the correspondences between multiple shapes. Besides applications of quantum annealing for shape matching, this thesis also contains work on solving the motion segmentation problem with quantum annealing and work about integrating a quantum annealer in a neural network to solve computer vision problems. The integration of the quantum annealer in a neural network can also be viewed as the task to learn an appropriate formulation of a computer vision problem in a way that is solvable with a current quantum annealer. Finally, we also present work about an iterative method for compensating limited connectivity in quantum annealing devices. This work has no particular computer vision application in mind, but investigates the performance of the different approaches on Max-Cut problems. The thesis is structured in a cumulative way, so that the individual publications are presented separately. On a broader picture, the works are motivated by the following questions: What could be the impact of quantum annealing on computer vision and how could computer vision algorithms that use quantum annealing look like? And from another perspective: How would the field of computer vision be changed if there were massive advances in building quadratic, unconstrained, binary optimization problem solvers with or even without utilizing quantum computing?