Despite being considered as the next frontier in computation, Quantum Computing is still in an early stage of development. Indeed, current commercial quantum computers suffer from some critical restraints, such as noisy processes and a limited amount of qubits, among others, that affect the performance of quantum algorithms. Despite these limitations, researchers have devoted much effort to propose different frameworks for efficiently using these Noisy Intermediate-Scale Quantum (NISQ) devices. One of these procedures is D'WAVE Systems' quantum-annealer, which can be used to solve optimization problems by translating them into an energy minimization problem. In this context, this work is focused on providing useful insights and information into the behaviour of the quantum-annealer when addressing real-world combinatorial optimization problems. Our main motivation with this study is to open some quantum computing frontiers to non-expert stakeholders. To this end, we perform an extensive experimentation, in the form of a parameter sensitive analysis. This experimentation has been conducted using the Traveling Salesman Problem as benchmarking problem, and adopting two QUBOs: state-of-the-art and a heuristically generated. Our analysis has been performed on a single 7-noded instance, and it is based on more than 200 different parameter configurations, comprising more than 3700 unitary runs and 7 million of quantum reads. Thanks to this study, findings related to the energy distribution and most appropriate parameter settings have been obtained. Finally, an additional study has been performed, aiming to determine the efficiency of the heuristically built QUBO in further TSP instances.
Despite being considered as the next frontier in computation, Quantum Computing is still in an early stage of development. Indeed, current commercial quantum computers suffer from some critical restraints, such as noisy processes and a limited amount of qubits, among others, that affect the performance of quantum algorithms. Despite these limitations, researchers have devoted much effort to propose different frameworks for efficiently using these Noisy Intermediate-Scale Quantum (NISQ) devices. One of these procedures is D'WAVE Systems' quantum-annealer, which can be used to solve optimization problems by translating them into an energy minimization problem. In this context, this work is focused on providing useful insights and information into the behaviour of the quantum-annealer when addressing real-world combinatorial optimization problems. Our main motivation with this study is to open some quantum computing frontiers to non-expert stakeholders. To this end, we perform an extensive experimentation, in the form of a parameter sensitive analysis. This experimentation has been conducted using the Traveling Salesman Problem as benchmarking problem, and adopting two QUBOs: state-of-the-art and a heuristically generated. Our analysis has been performed on a single 7-noded instance, and it is based on more than 200 different parameter configurations, comprising more than 3700 unitary runs and 7 million of quantum reads. Thanks to this study, findings related to the energy distribution and most appropriate parameter settings have been obtained. Finally, an additional study has been performed, aiming to determine the efficiency of the heuristically built QUBO in further TSP instances.
Quantum computing has emerged as a promising computational paradigm with the potential to solve problems that are intractable for classical computers. This paper provides an overview of the current state of quantum computing, including its historical development, hardware advancements, applications, and challenges. Special attention is given to combinatorial optimization, which is considered one of the most promising application domains. The limitations of current quantum systems and future research directions are also discussed. This paper presents a comparative study between a conventional D-Wave-based simulated annealing approach and a proposed hybrid optimization model for solving largescale combinatorial optimization problems. The study focuses on benchmark problems, including AES, TSP gr24, and a real-world load balancing problem, all formulated as QUBO models. The D-Wave approach employs the dwave-neal simulated annealing engine with various parameter settings, while the proposed model introduces a decomposition-based framework combined with adaptive parameter control and iterative refinement. The experimental results demonstrate that the proposed model consistently outperforms the conventional approach in terms of solution quality, achieving significantly lower energy values across all problem instances. In particular, for the TSP gr24 problem, the proposed model achieves near-optimal solutions with substantially reduced computation time. For large-scale problems such as AES and load balancing, the proposed model maintains scalability and robustness, whereas the conventional approach suffers from increased computational cost and performance degradation. Although the proposed method introduces additional computational steps, its hybrid structure effectively mitigates limitations related to local minima, parameter sensitivity, and scalability. These findings indicate that integrating classical optimization techniques with quantum-inspired methods is essential for practical applications. The proposed model provides a promising framework for solving complex real-world optimization problems and highlights the importance of hybrid approaches in advancing quantum annealing technologies.
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.
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.
This paper studies the Hamiltonian cycle problem (HCP) and the traveling salesman problem (TSP) on D-Wave quantum systems. Motivated by the fact that most libraries present their benchmark instances in terms of adjacency matrices, we develop a novel matrix formulation for the HCP and TSP Hamiltonians, which enables the seamless and automatic integration of benchmark instances in quantum platforms. We also present a thorough mathematical analysis of the precise number of constraints required to express the HCP and TSP Hamiltonians. This analysis explains quantitatively why, almost always, running incomplete graph instances requires more qubits than complete instances. It turns out that QUBO models for incomplete graphs require more quadratic constraints than complete graphs, a fact that has been corroborated by a series of experiments. Moreover, we introduce a technique for the min-max normalization for the coefficients of the TSP Hamiltonian to address the problem of invalid solutions produced by the quantum annealer, a trend often observed. Our extensive experimental tests have demonstrated that the D-Wave Advantage_system4.1 is more efficient than the Advantage_system1.1, both in terms of qubit utilization and the quality of solutions. Finally, we experimentally establish that the D-Wave hybrid solvers always provide valid solutions, without violating the given constraints, even for arbitrarily big problems up to 120 nodes.
Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000Qquantum hardware demonstrate that the optimal solutions for several instances can be attained.
The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.