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

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)

Solving NP-hard Problems with Quantum Annealing

Jehn‐Ruey Jiang, Chun-Wei Chu

Published Oct 28, 2022• 3 citations
Publisher

Abstract

Quadratic unconstrained binary optimization (QUBO) formulas of quantum annealing (QA) algorithms are classified into four categories. QA algorithms using different QUBO formulas solve specific NP-hard problems as examples of the classification. The NP-hard problems solved are the subset sum, the vertex cover, the graph coloring, and the traveling salesperson problems. The QA algorithms are compared with their classical counterparts in terms of the quality of the solution and the time to the solution. Based on the comparison results, observations and suggestions are given for each QUBO formula category, so that proper actions can be adopted to improve the performance of QA algorithms. Compared with classical algorithms, QA algorithms are competitive in the current noisy intermediate-scale quantum (NISQ) era and beyond.

DOI
10.1109/ecice55674.2022.10042862

Related papers

Classifying and Benchmarking Quantum Annealing Algorithms Based on Quadratic Unconstrained Binary Optimization for Solving NP-Hard Problems

Jehn‐Ruey Jiang, Chun-Wei Chu

Quantum annealing has the potential to outperform classical transistor-based computer technologies in tackling intricate combinatorial optimization problems. However, ongoing scientific debates cast doubts on whether quantum annealing devices (or quantum annealers) can genuinely provide better problem-solving capabilities than classical computers. The question of whether quantum annealing algorithms (QAAs) running on quantum annealers have computational advantages over classical algorithms (CAs) running on classical computers still remains unclear. This paper aims to clarify the question by classifying and benchmarking QAAs that utilize quadratic unconstrained binary optimization (QUBO) formulas to solve NP-hard problems. It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. The classification is based on the following two criteria: (i) Does the number of QUBO variables scale linearly with the problem input size? (ii) Does the QUBO formula have both the constraint term and the optimization term? QAAs are implemented and run on a D-Wave quantum annealer for benchmarking. They are benchmarked against related classical algorithms (CAs) running on classical computers in terms of the quality of the solution and the time to the solution. The benchmarking results reveal which classes of QUBO formulas are likely to provide advantages to QAAs over CAs. Furthermore, based on the benchmarking results, observations and suggestions are given for each class of QUBO formulas, facilitating the adoption of appropriate actions to improve the performance of QAAs.

IEEE Access•Jan 1, 2023•46 citations

Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis

David Biesner, Thore Gerlach, Christian Bauckhage +2 more

Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in many real applications.We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We outline how this algorithm can be applied by adiabatic quantum computers (quantum annealers) and specialized hardware (field programmable gate arrays) for digital annealing and run experiments on quantum annealing hardware.

arXiv:2211.02653•International Conference on Machine Learning and Applications•Dec 1, 2022•7 citations

Quantum Annealing for Multiobjective Query Optimization

Immanuel Trummer

Given a query plan, the goal of multiobjective query optimization [1] is to optimally map each operator in a plan to an implementation. Operator implementations differ by quality metrics such as cost and latency. In this context, query optimization becomes a multiobjective optimization problem. The optimal solution depends on user preferences and minimizes, for instance, a weighted sum over different cost metrics. We show how to transform instances of multiobjective query optimization, an NP-hard problem [1], into equivalent Quadratic Unconstrained Binary Optimization (QUBO) formulas that can be solved efficiently on quantum annealers.

Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data)•May 31, 2026•0 citations

Solving the Traveling Salesman Problem on the D-Wave Quantum Computer

Siddharth Jain

The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.

Frontiers in Physics•Nov 12, 2021•50 citations

Asymptotic Analysis of Problem Formulations for Quantum Annealers

Julio Auto, Fred Shi

Quantum annealing is a promising technique to solve NP-hard problems more efficiently than state-of-the-art classical computing algorithms. Current generation quantum annealers require users to formulate problems following specific models: either as an Ising Hamiltonian, or as a quadratic unconstrained binary optimization (QUBO) polynomial. In this paper, we show that a problem may be formulated in multiple, fundamentally different ways using these models, and that the choice of problem formulation drastically impacts the scope of problem instances that the quantum annealer is able to solve. Using Boolean satisfiability (SAT) solving as an example, we investigate which characteristics of problem formulation are determinant in solution viability. Drawing inspiration from classical algorithmic asymptotic analysis, we establish a framework for measuring the complexity of any given formulation using the QUBO or Ising models, which we argue can be useful for practitioners to evaluate and compare the different ways one may tackle a problem using quantum annealers.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•0 citations

An introduction to quantum annealing and review of QUBO models for Vehicle Routing Problem

Michał Jaroszczuk

Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.

IEEE International Symposium on Computational Intelligence and Informatics (CINTI)•Nov 18, 2025•1 citation
Quadratic unconstrained binary optimization (QUBO) formulas of quantum annealing (QA) algorithms are classified into four categories. QA algorithms using different QUBO formulas solve specific NP-hard problems as examples of the classification. The NP-hard problems solved are the subset sum, the vertex cover, the graph coloring, and the traveling salesperson problems. The QA algorithms are compared with their classical counterparts in terms of the quality of the solution and the time to the solution. Based on the comparison results, observations and suggestions are given for each QUBO formula category, so that proper actions can be adopted to improve the performance of QA algorithms. Compared with classical algorithms, QA algorithms are competitive in the current noisy intermediate-scale quantum (NISQ) era and beyond.
Quantum annealing has the potential to outperform classical transistor-based computer technologies in tackling intricate combinatorial optimization problems. However, ongoing scientific debates cast doubts on whether quantum annealing devices (or quantum annealers) can genuinely provide better problem-solving capabilities than classical computers. The question of whether quantum annealing algorithms (QAAs) running on quantum annealers have computational advantages over classical algorithms (CAs) running on classical computers still remains unclear. This paper aims to clarify the question by classifying and benchmarking QAAs that utilize quadratic unconstrained binary optimization (QUBO) formulas to solve NP-hard problems. It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. The classification is based on the following two criteria: (i) Does the number of QUBO variables scale linearly with the problem input size? (ii) Does the QUBO formula have both the constraint term and the optimization term? QAAs are implemented and run on a D-Wave quantum annealer for benchmarking. They are benchmarked against related classical algorithms (CAs) running on classical computers in terms of the quality of the solution and the time to the solution. The benchmarking results reveal which classes of QUBO formulas are likely to provide advantages to QAAs over CAs. Furthermore, based on the benchmarking results, observations and suggestions are given for each class of QUBO formulas, facilitating the adoption of appropriate actions to improve the performance of QAAs.
Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in many real applications.We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We outline how this algorithm can be applied by adiabatic quantum computers (quantum annealers) and specialized hardware (field programmable gate arrays) for digital annealing and run experiments on quantum annealing hardware.
Given a query plan, the goal of multiobjective query optimization [1] is to optimally map each operator in a plan to an implementation. Operator implementations differ by quality metrics such as cost and latency. In this context, query optimization becomes a multiobjective optimization problem. The optimal solution depends on user preferences and minimizes, for instance, a weighted sum over different cost metrics. We show how to transform instances of multiobjective query optimization, an NP-hard problem [1], into equivalent Quadratic Unconstrained Binary Optimization (QUBO) formulas that can be solved efficiently on quantum annealers.
The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.
Quantum annealing is a promising technique to solve NP-hard problems more efficiently than state-of-the-art classical computing algorithms. Current generation quantum annealers require users to formulate problems following specific models: either as an Ising Hamiltonian, or as a quadratic unconstrained binary optimization (QUBO) polynomial. In this paper, we show that a problem may be formulated in multiple, fundamentally different ways using these models, and that the choice of problem formulation drastically impacts the scope of problem instances that the quantum annealer is able to solve. Using Boolean satisfiability (SAT) solving as an example, we investigate which characteristics of problem formulation are determinant in solution viability. Drawing inspiration from classical algorithmic asymptotic analysis, we establish a framework for measuring the complexity of any given formulation using the QUBO or Ising models, which we argue can be useful for practitioners to evaluate and compare the different ways one may tackle a problem using quantum annealers.
Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.