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

Solving Optimization Problems Using Adiabatic Quantum Computing

Liu, Kai

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

The commercial D-Waves quantum annealer has given rise to plenty of interests due to the reported quantum speedup against classical annealing. In order to make use of this new technology, a problem must be formulated into a form of quadratic unconstrained binary optimization (QUBO) or Ising model. This thesis reports on case studies using a D-Wave quantum annealer to solve several optimization problems and providing results validation using classical exact approaches. In our thesis, we briefly introduce several classical techniques designed for QUBO problems and implement two exact approaches. With the proper tools, a D-Wave 2X computer consisted of 1098 active qubits is then evaluated for the Degree-Constrained Minimum Spanning Tree and the Steiner Tree problems, establishing their QUBO formulations are suitable for adiabatic quantum computers. Motivated by the remarkable performance, two more optimization problems are studied—the Bounded-Depth Steiner Tree problem and the Chromatic Sum problem. We propose a new formulation for each problem. The numbers of qubits (dimension of QUBO matrices) required by our formulations are O(|V|3) and O(|V|2) respectively, where |V| represents the number of vertices.

Related papers

Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer

Kai Liu, Michael J. Dinneen

We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.

IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)•Dec 1, 2019•5 citations

Quantum optimization algorithm for solving elliptic boundary value problems on D-Wave quantum annealing device

Rebecca Conley, Deokkyu Choi, Gregory Medwig +4 more

The quantum annealing devices, which encode the solution to a computational problem in the ground state of a quantum Hamiltonian, are implemented in D-Wave systems with more than 2,000 qubits. However, quantum annealing can solve only a classical combinatorial optimization problem such as an Ising model, or equivalently, a quadratic unconstrained binary optimization (QUBO) problem. In this paper, we formulate the QUBO model to solve elliptic problems with Dirichlet and Neumann boundary conditions using the finite element method. In this formulation, we develop the objective function of quadratic binary variables represented by qubits and the system finds the binary string combination minimizing the objective function globally. Based on the QUBO formulation, we introduce an iterative algorithm to solve the elliptic problems. We discuss the validation of the modeling on the D-Wave quantum annealing system.

Quantum Computing, Communication, and Simulation•Mar 8, 2023•8 citations

Formulating graph covering problems for adiabatic quantum computers

Michael J. Dinneen, Richard Hua

We provide efficient quadratic unconstrained binary optimization (QUBO) formulations for the Dominating Set and Edge Cover combinatorial problems suitable for adiabatic quantum computers, which are viewed as a real-world enhanced model of simulated annealing (e.g. a type of genetic algorithm with quantum tunneling). The number of qubits (dimension of QUBO matrices) required to solve these set cover problems are O(n + n lg n) and O(m + n lg n) respectively, where n is the number of vertices and m is the number of edges. We also extend our formulations for the Minimum Vertex-Weighted Dominating Set problem and the Minimum Edge-Weighted Edge Cover problem. Experimental results for the Dominating Set and Edge Cover problems using a D-Wave Systems quantum computer with 1098 active qubit-coupled processors are also provided for a selection of known common graphs.

Australasian Computer Science Week Multiconference (ACSW)•Dec 20, 2016•16 citations

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•17 citations

Comparing Quantum Annealer and Metaheuristic Methods to Solve the Steiner Tree Problem

Darren M. Chitty, James Charles, Alberto Moraglio +1 more

Quantum computers are early-stage technology, but are progressing rapidly. Here, we compare metaheuristics with a quantum annealer (QA), a quantum computer tailored to solve combinatorial optimisation problems formulated as a Quadratic Unconstrained Binary Optimisation (QUBO) problem. Formulating non-trivial optimisation problems as QUBOs is a challenge, so it is to ensure that the direct comparison of classical and quantum search algorithms is conducted fairly. This paper illustrates the use of a streamlined methodology to derive a QUBO for a classical optimisation problem – the Steiner tree problem – and provides comprehensive experiments comparing D-WAVE pure QA and hybrid QA with classical methods including Simulated Annealing and Genetic Algorithms. We find that the pure QA suffers from considerable qubit noise but the hybrid QA is on a par with traditional methods.

Lecture notes in computer science•Nov 15, 2025•0 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•32 citations
The commercial D-Waves quantum annealer has given rise to plenty of interests due to the reported quantum speedup against classical annealing. In order to make use of this new technology, a problem must be formulated into a form of quadratic unconstrained binary optimization (QUBO) or Ising model. This thesis reports on case studies using a D-Wave quantum annealer to solve several optimization problems and providing results validation using classical exact approaches. In our thesis, we briefly introduce several classical techniques designed for QUBO problems and implement two exact approaches. With the proper tools, a D-Wave 2X computer consisted of 1098 active qubits is then evaluated for the Degree-Constrained Minimum Spanning Tree and the Steiner Tree problems, establishing their QUBO formulations are suitable for adiabatic quantum computers. Motivated by the remarkable performance, two more optimization problems are studied—the Bounded-Depth Steiner Tree problem and the Chromatic Sum problem. We propose a new formulation for each problem. The numbers of qubits (dimension of QUBO matrices) required by our formulations are O(|V|3) and O(|V|2) respectively, where |V| represents the number of vertices.
We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.
The quantum annealing devices, which encode the solution to a computational problem in the ground state of a quantum Hamiltonian, are implemented in D-Wave systems with more than 2,000 qubits. However, quantum annealing can solve only a classical combinatorial optimization problem such as an Ising model, or equivalently, a quadratic unconstrained binary optimization (QUBO) problem. In this paper, we formulate the QUBO model to solve elliptic problems with Dirichlet and Neumann boundary conditions using the finite element method. In this formulation, we develop the objective function of quadratic binary variables represented by qubits and the system finds the binary string combination minimizing the objective function globally. Based on the QUBO formulation, we introduce an iterative algorithm to solve the elliptic problems. We discuss the validation of the modeling on the D-Wave quantum annealing system.
We provide efficient quadratic unconstrained binary optimization (QUBO) formulations for the Dominating Set and Edge Cover combinatorial problems suitable for adiabatic quantum computers, which are viewed as a real-world enhanced model of simulated annealing (e.g. a type of genetic algorithm with quantum tunneling). The number of qubits (dimension of QUBO matrices) required to solve these set cover problems are O(n + n lg n) and O(m + n lg n) respectively, where n is the number of vertices and m is the number of edges. We also extend our formulations for the Minimum Vertex-Weighted Dominating Set problem and the Minimum Edge-Weighted Edge Cover problem. Experimental results for the Dominating Set and Edge Cover problems using a D-Wave Systems quantum computer with 1098 active qubit-coupled processors are also provided for a selection of known common graphs.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Quantum computers are early-stage technology, but are progressing rapidly. Here, we compare metaheuristics with a quantum annealer (QA), a quantum computer tailored to solve combinatorial optimisation problems formulated as a Quadratic Unconstrained Binary Optimisation (QUBO) problem. Formulating non-trivial optimisation problems as QUBOs is a challenge, so it is to ensure that the direct comparison of classical and quantum search algorithms is conducted fairly. This paper illustrates the use of a streamlined methodology to derive a QUBO for a classical optimisation problem – the Steiner tree problem – and provides comprehensive experiments comparing D-WAVE pure QA and hybrid QA with classical methods including Simulated Annealing and Genetic Algorithms. We find that the pure QA suffers from considerable qubit noise but the hybrid QA is on a par with traditional methods.
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.