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:2212.11132 · Quantum Information and Computation

Quantum annealing learning search implementations

Andrea Bonomi, Thomas De Min, Enrico Zardini, Enrico Blanzieri, Valter Cavecchia, Davide Pastorello

Published Feb 1, 2022• 3 citations
arXivHTMLPDF

Abstract

This paper presents the details and testing of two implementations (in C++ and Python) of the hybrid quantum-classical algorithm Quantum Annealing Learning Search (QALS) on a D-Wave quantum annealer. QALS was proposed in 2019 as a novel technique to solve general QUBO problems that cannot be directly represented into the hardware architecture of a D-Wave machine. Repeated calls to the quantum machine within a classical iterative structure and a related convergence proof originate a learning mechanism to find an encoding of a given problem into the quantum architecture. The present work considers the Number Partitioning Problem (NPP) and the Travelling Salesman Problem (TSP) for the testing of QALS. The results turn out to be quite unexpected, with QALS not being able to perform as well as the other considered methods, especially in NPP, where classical methods outperform quantum annealing in general. Nevertheless, looking at the TSP tests, QALS has fulfilled its primary goal, i.e., processing QUBO problems not directly mappable to the QPU topology.

DOI
10.26421/qic22.3-4-1

Related papers

Testing Classical and Hybrid Quantum Solvers for Special and Euclidean Traveling Salesman Problem Instances

Jedidiah T. Ramos, Cherry Lyn C. Sta. Romana

A classical algorithm is tested against D-Wave hybrid quantum annealers for special cases of the Traveling Salesman Problem where the weights of the edges in a graph form an arithmetic progression. The classical algorithm, Christofides, Nearest Neighbor, Simulated Annealing, Ant Colony Optimization, Genetic Algorithm, and D-Wave hybrid quantum annealers are also tested on the Euclidean Traveling Salesman Problem. D-Wave never outperformed the classical algorithm within its specified scope but outperformed all classical algorithms and heuristics for the Euclidean Traveling Salesman Problem before being overtaken at larger problem sizes.

International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence (ISMSI)•Apr 24, 2026•0 citations

Quantum Annealing implementation of TSP with soft constraint and performance comparison with the latest D-Wave’s resources.

Jaime Vallejo Benítez-Cano

The objective of this project is to check D-Wave’s evolution in one year based on previous research project [1] [2]. In order to evaluate this state-of-the-art, the three current D-Wave’s QPU topologies have been used for performance comparison. The aspects that have been studied are time performance, the correctness of results and stability of minor embedding into each type of quantum architecture. The problem that has been used as a test for this performance comparison has been the well-known Travelling Salesman Problem (TSP) with a soft constraint which is Sequential Ordering Problem (SOP). The different setups that have executed each approach are the following: - D-Wave’s Exact solver (using CPU exclusively). - Pure QPU implementation using D-Wave’s Dimod solver. - GPU adapted parallelization of Classical Brute-force algorithm with NVIDIA CUDA API. - D-Wave’s Hybrid solver (which combines QPU together with classical techniques). The results of this project reveal that current quantum resources have some limitations on their own. Using a pure QPU approach achieves no better results than current classical computation (CPU and GPU). However, its importance lies in the simultaneous usage of both quantum and classical resources to leverage the complexity burden and compensate for each other’s weaknesses. This is the quantum hybrid approach, which has proved to achieve nice results. These results took an execution time that is unfeasible for classical computing due to O(N!) complexity of Brute-force algorithms required to solve NP-hard problems like TSP. Regarding topologies, the use of a Zephyr prototype with many fewer qubits than Pegasus and Chimera devices has proven that Zephyr is a much better architecture due to the high connectivity of the qubits lattice that enables better minor-embedding, shorter execution times and more stability in the results obtained.

•Jul 15, 2022•0 citations

Efficient solution of the number partitioning problem on a quantum annealer: a hybrid quantum-classical decomposition approach

Zongji Li, Tobias Seidel, Dominik Leib +2 more

Abstract Current quantum computers can only solve optimization problems of a very limited size. For larger problems, decomposition methods are required in which the original problem is broken down into several smaller sub-problems. These are then solved on the quantum computer and their solutions are recombined into a final solution for the original problem. Often, these decomposition methods do not take the specific problem structure into account. In this paper, we present a tailored method using a divide-and-conquer strategy to solve the 2-way Number partitioning problem (NPP) with a large number of variables. The idea is to perform a specialized decomposition into smaller NPPs, which are solved on a quantum computer, and then recombine the results into another small auxiliary NPP. Solving this auxiliary problem yields an approximate solution of the original larger problem. We experimentally verify that our method allows to solve NPPs with over a thousand variables using the D-Wave Advantage quantum annealer (Advantage_system6.4).

arXiv:2312.08940•Journal of Heuristics•Apr 17, 2025•4 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

Accelerating NP-Hard Optimization via Quantum-Inspired Classical Algorithms

Mukesh Krishnan, Saravanan Dr

A primary challenge of computational science is solving NP-hard optimization problems since they are too complicated and cannot be effectively solved deterministically in large instances. Even though quantum computing can solve these problems with the help of its key properties quantum parallelism and tunneling, the modern hardware is yet not sufficiently developed. In this case, QICAs are considered as a new method in which the key aspects of quantum mechanics, such as superposition, entanglement, interference and tunneling are replicated in classical, non-quantum computers. It aims to attain rapid optimization of NP-hard problems through a hybrid approach that combines cartography-based exploration, variable state reduction with tensor networks as well as an inclusion of a variant-based approach inspired by QAOA. A number of standard problems are used to test the model, e.g., the Traveling Salesman Problem (TSP), the 0/1 Knapsack Problem and Max-Cut Problem. Genetic Algorithms, Simulated Annealing and Ant Colony Optimization trials all concur that QICA converges to superior solutions much faster and it can nonetheless handle bigger-sized problems. More precisely, the algorithm provides better approximation results as well as lesser computing power requirements, thus demonstrating the effectiveness of quantum-inspired methods in the case of classical systems. They establish the fact that QICAs have the potential to solve challenging optimization problems, particularly in the cases where quantum machines are absent or inaccessible. The way of solving the problem represented in the study is quite innovative and serves as a bridge between the theory of quantum and practical implementation in the optimization field.

International Innovative Research Journal of Engineering and Technology•Mar 30, 2025•0 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
This paper presents the details and testing of two implementations (in C++ and Python) of the hybrid quantum-classical algorithm Quantum Annealing Learning Search (QALS) on a D-Wave quantum annealer. QALS was proposed in 2019 as a novel technique to solve general QUBO problems that cannot be directly represented into the hardware architecture of a D-Wave machine. Repeated calls to the quantum machine within a classical iterative structure and a related convergence proof originate a learning mechanism to find an encoding of a given problem into the quantum architecture. The present work considers the Number Partitioning Problem (NPP) and the Travelling Salesman Problem (TSP) for the testing of QALS. The results turn out to be quite unexpected, with QALS not being able to perform as well as the other considered methods, especially in NPP, where classical methods outperform quantum annealing in general. Nevertheless, looking at the TSP tests, QALS has fulfilled its primary goal, i.e., processing QUBO problems not directly mappable to the QPU topology.
A classical algorithm is tested against D-Wave hybrid quantum annealers for special cases of the Traveling Salesman Problem where the weights of the edges in a graph form an arithmetic progression. The classical algorithm, Christofides, Nearest Neighbor, Simulated Annealing, Ant Colony Optimization, Genetic Algorithm, and D-Wave hybrid quantum annealers are also tested on the Euclidean Traveling Salesman Problem. D-Wave never outperformed the classical algorithm within its specified scope but outperformed all classical algorithms and heuristics for the Euclidean Traveling Salesman Problem before being overtaken at larger problem sizes.
The objective of this project is to check D-Wave’s evolution in one year based on previous research project [1] [2]. In order to evaluate this state-of-the-art, the three current D-Wave’s QPU topologies have been used for performance comparison. The aspects that have been studied are time performance, the correctness of results and stability of minor embedding into each type of quantum architecture. The problem that has been used as a test for this performance comparison has been the well-known Travelling Salesman Problem (TSP) with a soft constraint which is Sequential Ordering Problem (SOP). The different setups that have executed each approach are the following: - D-Wave’s Exact solver (using CPU exclusively). - Pure QPU implementation using D-Wave’s Dimod solver. - GPU adapted parallelization of Classical Brute-force algorithm with NVIDIA CUDA API. - D-Wave’s Hybrid solver (which combines QPU together with classical techniques). The results of this project reveal that current quantum resources have some limitations on their own. Using a pure QPU approach achieves no better results than current classical computation (CPU and GPU). However, its importance lies in the simultaneous usage of both quantum and classical resources to leverage the complexity burden and compensate for each other’s weaknesses. This is the quantum hybrid approach, which has proved to achieve nice results. These results took an execution time that is unfeasible for classical computing due to O(N!) complexity of Brute-force algorithms required to solve NP-hard problems like TSP. Regarding topologies, the use of a Zephyr prototype with many fewer qubits than Pegasus and Chimera devices has proven that Zephyr is a much better architecture due to the high connectivity of the qubits lattice that enables better minor-embedding, shorter execution times and more stability in the results obtained.
Abstract Current quantum computers can only solve optimization problems of a very limited size. For larger problems, decomposition methods are required in which the original problem is broken down into several smaller sub-problems. These are then solved on the quantum computer and their solutions are recombined into a final solution for the original problem. Often, these decomposition methods do not take the specific problem structure into account. In this paper, we present a tailored method using a divide-and-conquer strategy to solve the 2-way Number partitioning problem (NPP) with a large number of variables. The idea is to perform a specialized decomposition into smaller NPPs, which are solved on a quantum computer, and then recombine the results into another small auxiliary NPP. Solving this auxiliary problem yields an approximate solution of the original larger problem. We experimentally verify that our method allows to solve NPPs with over a thousand variables using the D-Wave Advantage quantum annealer (Advantage_system6.4).
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.
A primary challenge of computational science is solving NP-hard optimization problems since they are too complicated and cannot be effectively solved deterministically in large instances. Even though quantum computing can solve these problems with the help of its key properties quantum parallelism and tunneling, the modern hardware is yet not sufficiently developed. In this case, QICAs are considered as a new method in which the key aspects of quantum mechanics, such as superposition, entanglement, interference and tunneling are replicated in classical, non-quantum computers. It aims to attain rapid optimization of NP-hard problems through a hybrid approach that combines cartography-based exploration, variable state reduction with tensor networks as well as an inclusion of a variant-based approach inspired by QAOA. A number of standard problems are used to test the model, e.g., the Traveling Salesman Problem (TSP), the 0/1 Knapsack Problem and Max-Cut Problem. Genetic Algorithms, Simulated Annealing and Ant Colony Optimization trials all concur that QICA converges to superior solutions much faster and it can nonetheless handle bigger-sized problems. More precisely, the algorithm provides better approximation results as well as lesser computing power requirements, thus demonstrating the effectiveness of quantum-inspired methods in the case of classical systems. They establish the fact that QICAs have the potential to solve challenging optimization problems, particularly in the cases where quantum machines are absent or inaccessible. The way of solving the problem represented in the study is quite innovative and serves as a bridge between the theory of quantum and practical implementation in the optimization field.
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.