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 EUROCON - International Conference on Computer as a Tool (EUROCON)

On the Design and Characterization of Set Packing Problem on Quantum Annealers

M. Vénere, Giuseppe Sorrentino, Beatrice Branchini, Davide Conficconi, Elisabetta Di Nitto, Donatella Sciuto, Marco Domenico Santambrogio

Published Jul 6, 2023• 3 citations
Publisher

Abstract

The beginning of the quantum era has increased the hype around computationally demanding problems and, particularly, NP-complete problems. One of the most famous is the Set Packing, which has several applications in different management contexts. This work presents a solver for Set Packing Problem on quantum annealers exploiting the QUBO model. We introduce a general format to express instances of the Set Packing Problem that enables an automatic characterization, lowering the barriers to adopting quantum annealers. Finally, we compare the performance of two quantum annealer on the Set Packing, namely D-Wave 2000Q and Advantage, highlighting their pros and cons. As key evaluation indicators, this work uses spatial features, such as the number of qubits and maximum chain length, and the execution time required for a reliable problem resolution and its breakdown. In particular, we can scale the solutions to 60 and 150 subsets on 2000Q and Advantage, respectively, with 0 chain breaks. Moreover, our analysis illustrates that 2000Q has lower mean energy required but higher execution times on the same problem complexity.

DOI
10.1109/eurocon56442.2023.10199096

Related papers

Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems

Dennis Willsch, Madita Willsch, Carlos D. Gonzalez Calaza +4 more

Abstract We benchmark the quantum processing units of the largest quantum annealers to date, the $$5000+$$ 5000 + qubit quantum annealer Advantage and its 2000+ qubit predecessor D-Wave 2000Q, using tail assignment and exact cover problems from aircraft scheduling scenarios. The benchmark set contains small, intermediate, and large problems with both sparsely connected and almost fully connected instances. We find that Advantage outperforms D-Wave 2000Q for almost all problems, with a notable increase in success rate and problem size. In particular, Advantage is also able to solve the largest problems with 120 logical qubits that D-Wave 2000Q cannot solve anymore. Furthermore, problems that can still be solved by D-Wave 2000Q are solved faster by Advantage. We find, however, that D-Wave 2000Q can achieve better success rates for sparsely connected problems that do not require the many new couplers present on Advantage, so improving the connectivity of a quantum annealer does not per se improve its performance.

arXiv:2105.02208•Quantum Information Processing•Apr 1, 2022•114 citations

Efficient Combinatorial Optimization Using Quantum Annealing

Hristo N. Djidjev, Guillaume Chapuis, Georg Hahn +1 more

The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.

arXiv:1801.08653•Jan 26, 2018•27 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•7 citations

Using Machine Learning for Quantum Annealing Accuracy Prediction

Aaron Barbosa, Elijah Pelofske, Georg Hahn +1 more

Quantum annealers, such as the device built by D-Wave Systems, Inc., offer a way to compute solutions of NP-hard problems that can be expressed in Ising or quadratic unconstrained binary optimization (QUBO) form. Although such solutions are typically of very high quality, problem instances are usually not solved to optimality due to imperfections of the current generations quantum annealers. In this contribution, we aim to understand some of the factors contributing to the hardness of a problem instance, and to use machine learning models to predict the accuracy of the D-Wave 2000Q annealer for solving specific problems. We focus on the maximum clique problem, a classic NP-hard problem with important applications in network analysis, bioinformatics, and computational chemistry. By training a machine learning classification model on basic problem characteristics such as the number of edges in the graph, or annealing parameters, such as the D-Wave’s chain strength, we are able to rank certain features in the order of their contribution to the solution hardness, and present a simple decision tree which allows to predict whether a problem will be solvable to optimality with the D-Wave 2000Q. We extend these results by training a machine learning regression model that predicts the clique size found by D-Wave.

arXiv:2106.00065•Algorithms•Jun 21, 2021•2 citations

Testing quantum and simulated annealers on the drone delivery packing problem

Sara Tarquini, Daniele Dragoni, Matteo Vandelli +1 more

Using drones to perform human-related tasks can play a key role in various fields, such as defense, disaster response, agriculture, healthcare, and many others. The drone delivery packing problem (DDPP) arises in the context of logistics in response to an increasing demand in the delivery process, along with the necessity of lowering human intervention. The DDPP is usually formulated as a combinatorial optimization (CO) problem, aiming to minimize drone usage with specific battery constraints while ensuring time-consistent deliveries with fixed locations and energy budget. In this work, we propose two alternative formulations of the DDPP as a quadratic unconstrained binary optimization (QUBO) problem to test the performance of classical and quantum annealing (QA) approaches. We perform extensive experiments showing the advantages as well as the limitations of quantum annealers for this optimization problem, as compared to simulated annealing (SA) and classical state-of-the-art commercial tools for global optimization.

arXiv:2406.08430•Quantum Machine Intelligence•Feb 16, 2026•2 citations

Quantum annealing for combinatorial optimization: a benchmarking study

Seongmin Kim, Sang-Woo Ahn, In‐Saeng Suh +3 more

Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.

arXiv:2504.06201•npj Quantum Information•May 16, 2025•46 citations
The beginning of the quantum era has increased the hype around computationally demanding problems and, particularly, NP-complete problems. One of the most famous is the Set Packing, which has several applications in different management contexts. This work presents a solver for Set Packing Problem on quantum annealers exploiting the QUBO model. We introduce a general format to express instances of the Set Packing Problem that enables an automatic characterization, lowering the barriers to adopting quantum annealers. Finally, we compare the performance of two quantum annealer on the Set Packing, namely D-Wave 2000Q and Advantage, highlighting their pros and cons. As key evaluation indicators, this work uses spatial features, such as the number of qubits and maximum chain length, and the execution time required for a reliable problem resolution and its breakdown. In particular, we can scale the solutions to 60 and 150 subsets on 2000Q and Advantage, respectively, with 0 chain breaks. Moreover, our analysis illustrates that 2000Q has lower mean energy required but higher execution times on the same problem complexity.
Abstract We benchmark the quantum processing units of the largest quantum annealers to date, the 5000+5000+5000+ 5000 + qubit quantum annealer Advantage and its 2000+ qubit predecessor D-Wave 2000Q, using tail assignment and exact cover problems from aircraft scheduling scenarios. The benchmark set contains small, intermediate, and large problems with both sparsely connected and almost fully connected instances. We find that Advantage outperforms D-Wave 2000Q for almost all problems, with a notable increase in success rate and problem size. In particular, Advantage is also able to solve the largest problems with 120 logical qubits that D-Wave 2000Q cannot solve anymore. Furthermore, problems that can still be solved by D-Wave 2000Q are solved faster by Advantage. We find, however, that D-Wave 2000Q can achieve better success rates for sparsely connected problems that do not require the many new couplers present on Advantage, so improving the connectivity of a quantum annealer does not per se improve its performance.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
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 annealers, such as the device built by D-Wave Systems, Inc., offer a way to compute solutions of NP-hard problems that can be expressed in Ising or quadratic unconstrained binary optimization (QUBO) form. Although such solutions are typically of very high quality, problem instances are usually not solved to optimality due to imperfections of the current generations quantum annealers. In this contribution, we aim to understand some of the factors contributing to the hardness of a problem instance, and to use machine learning models to predict the accuracy of the D-Wave 2000Q annealer for solving specific problems. We focus on the maximum clique problem, a classic NP-hard problem with important applications in network analysis, bioinformatics, and computational chemistry. By training a machine learning classification model on basic problem characteristics such as the number of edges in the graph, or annealing parameters, such as the D-Wave’s chain strength, we are able to rank certain features in the order of their contribution to the solution hardness, and present a simple decision tree which allows to predict whether a problem will be solvable to optimality with the D-Wave 2000Q. We extend these results by training a machine learning regression model that predicts the clique size found by D-Wave.
Using drones to perform human-related tasks can play a key role in various fields, such as defense, disaster response, agriculture, healthcare, and many others. The drone delivery packing problem (DDPP) arises in the context of logistics in response to an increasing demand in the delivery process, along with the necessity of lowering human intervention. The DDPP is usually formulated as a combinatorial optimization (CO) problem, aiming to minimize drone usage with specific battery constraints while ensuring time-consistent deliveries with fixed locations and energy budget. In this work, we propose two alternative formulations of the DDPP as a quadratic unconstrained binary optimization (QUBO) problem to test the performance of classical and quantum annealing (QA) approaches. We perform extensive experiments showing the advantages as well as the limitations of quantum annealers for this optimization problem, as compared to simulated annealing (SA) and classical state-of-the-art commercial tools for global optimization.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.