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

Entropy

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

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

Published Oct 12, 2018• 21 citations
Publisher

Abstract

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.

DOI
10.3390/e20100786

Related papers

Quantum-Hybrid Stereo Matching With Nonlinear Regularization and Spatial Pyramids

Cameron Braunstein, Eddy Ilg, Vladislav Golyanik

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.

arXiv:2312.16118•International Conference on 3D Vision (3DV)•Mar 18, 2024•3 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•6 citations

A QUBO Formulation of Minimum Multicut Problem Instances in Trees for D-Wave Quantum Annealers

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

Quantum annealing algorithms were introduced to solve combinatorial optimization problems by taking advantage of quantum fluctuations to escape local minima in complex energy landscapes typical of NP - hard problems. In this work, we propose using quantum annealing for the theory of cuts, a field of paramount importance in theoretical computer science. We have proposed a method to formulate the Minimum Multicut Problem into the QUBO representation, and the technical difficulties faced when embedding and submitting a problem to the quantum annealer processor. We show two constructions of the quadratic unconstrained binary optimization functions for the Minimum Multicut Problem and we review several tradeoffs between the two mappings and provide numerical scaling analysis results from several classical approaches. Furthermore, we discuss some of the expected challenges and tradeoffs in the implementation of our mapping in the current generation of D-Wave machines.

Scientific Reports•Nov 20, 2019•29 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

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

Enhanced QUBO Formulations for The Flow Shop Scheduling Problem

Yousra Farhani, Malak Saiem, Taha Arbaoui +1 more

In recent years, the Flow shop Scheduling Problem (FSP) has gained significant attention, prompting researchers to develop various methods, from conventional to hybrid optimization algorithms. Driven by the rapid growth of quantum computing capabilities, quantum approaches applied to optimization problems have attracted an increasing research effort. This work attempts to solve the permutation flow shop scheduling problem using quantum annealing by formulating the problem as a Quadratic Unconstrained Binary Optimization model (QUBO). Two QUBO formulations tailored to address the FSP are used. The first formulation is based on the position-based modelling while the second is based on five approximations of FSP as a Traveling Salesman Problem (TSP). The QUBO formulations are tested, using D-Wave's quantum annealers, on the well-known Taillard FSP benchmark and compared against each other. Results show that the proposed position-based QUBO reaches better solutions than the TSP-based QUBOs. This work is an attempt to highlight the increasing effectiveness of quantum annealers in addressing complex optimization problems and their limitations compared to conventional classical methods.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2024•4 citations
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.
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.
Quantum annealing algorithms were introduced to solve combinatorial optimization problems by taking advantage of quantum fluctuations to escape local minima in complex energy landscapes typical of NP - hard problems. In this work, we propose using quantum annealing for the theory of cuts, a field of paramount importance in theoretical computer science. We have proposed a method to formulate the Minimum Multicut Problem into the QUBO representation, and the technical difficulties faced when embedding and submitting a problem to the quantum annealer processor. We show two constructions of the quadratic unconstrained binary optimization functions for the Minimum Multicut Problem and we review several tradeoffs between the two mappings and provide numerical scaling analysis results from several classical approaches. Furthermore, we discuss some of the expected challenges and tradeoffs in the implementation of our mapping in the current generation of D-Wave machines.
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.
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?
In recent years, the Flow shop Scheduling Problem (FSP) has gained significant attention, prompting researchers to develop various methods, from conventional to hybrid optimization algorithms. Driven by the rapid growth of quantum computing capabilities, quantum approaches applied to optimization problems have attracted an increasing research effort. This work attempts to solve the permutation flow shop scheduling problem using quantum annealing by formulating the problem as a Quadratic Unconstrained Binary Optimization model (QUBO). Two QUBO formulations tailored to address the FSP are used. The first formulation is based on the position-based modelling while the second is based on five approximations of FSP as a Traveling Salesman Problem (TSP). The QUBO formulations are tested, using D-Wave's quantum annealers, on the well-known Taillard FSP benchmark and compared against each other. Results show that the proposed position-based QUBO reaches better solutions than the TSP-based QUBOs. This work is an attempt to highlight the increasing effectiveness of quantum annealers in addressing complex optimization problems and their limitations compared to conventional classical methods.