Abstract The field of Quantum Computing has gathered significant popularity in recent years and a large number of papers have studied its effectiveness in tackling many tasks. We focus in particular on Quantum Annealing (QA), a meta-heuristic solver for Quadratic Unconstrained Binary Optimization (QUBO) problems. It is known that the effectiveness of QA is dependent on the task itself, as is the case for classical solvers, but there is not yet a clear understanding of which are the characteristics of a problem that make it difficult to solve with QA. In this work, we propose a new methodology to study the effectiveness of QA based on meta-learning models. To do so, we first build a dataset composed of more than five thousand instances of ten different optimization problems. We define a set of more than a hundred features to describe their characteristics and solve them with both QA and three classical solvers. We publish this dataset online for future research. Then, we train multiple meta-models to predict whether QA would solve that instance effectively and use them to probe which features with the strongest impact on the effectiveness of QA. Our results indicate that it is possible to accurately predict the effectiveness of QA, validating our methodology. Furthermore, we observe that the distribution of the problem coefficients representing the bias and coupling terms is very informative in identifying the probability of finding good solutions, while the density of these coefficients alone is not enough. The methodology we propose allows to open new research directions to further our understanding of the effectiveness of QA, by probing specific dimensions or by developing new QUBO formulations that are better suited for the particular nature of QA. Furthermore, the proposed methodology is flexible and can be extended or used to study other quantum or classical solvers.
Abstract The field of Quantum Computing has gathered significant popularity in recent years and a large number of papers have studied its effectiveness in tackling many tasks. We focus in particular on Quantum Annealing (QA), a meta-heuristic solver for Quadratic Unconstrained Binary Optimization (QUBO) problems. It is known that the effectiveness of QA is dependent on the task itself, as is the case for classical solvers, but there is not yet a clear understanding of which are the characteristics of a problem that make it difficult to solve with QA. In this work, we propose a new methodology to study the effectiveness of QA based on meta-learning models. To do so, we first build a dataset composed of more than five thousand instances of ten different optimization problems. We define a set of more than a hundred features to describe their characteristics and solve them with both QA and three classical solvers. We publish this dataset online for future research. Then, we train multiple meta-models to predict whether QA would solve that instance effectively and use them to probe which features with the strongest impact on the effectiveness of QA. Our results indicate that it is possible to accurately predict the effectiveness of QA, validating our methodology. Furthermore, we observe that the distribution of the problem coefficients representing the bias and coupling terms is very informative in identifying the probability of finding good solutions, while the density of these coefficients alone is not enough. The methodology we propose allows to open new research directions to further our understanding of the effectiveness of QA, by probing specific dimensions or by developing new QUBO formulations that are better suited for the particular nature of QA. Furthermore, the proposed methodology is flexible and can be extended or used to study other quantum or classical solvers.
This paper explores the applications of quantum annealing (QA) and classical simulated annealing (SA) to a suite of combinatorial optimization problems in machine learning, namely feature selection, instance selection, and clustering. We formulate each task as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implement both quantum and classical solvers to compare their effectiveness. For feature selection, we propose several QUBO configurations that balance feature importance and redundancy, showing that quantum annealing (QA) produces solutions that are computationally more efficient. In instance selection, we propose a few novel heuristics for instance-level importance measures that extend existing methods. For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement, and demonstrate consistent improvements in cluster compactness and retrieval metrics. Our results suggest that QA can be a competitive and efficient tool for discrete machine learning optimization, even within the constraints of current quantum hardware.
This paper explores the application of Quantum Annealing (QA) to the field of combinatorial optimization. The core idea is to leverage the principles of quantum mechanics, specifically quantum tunneling, to efficiently solve complex optimization problems. We present a framework for utilizing QA to tackle problems represented as quadratic unconstrained binary optimization (QUBO) models. The methodology focuses on mapping the problem's constraints and objective function into a form suitable for QA hardware. We discuss the challenges involved in this mapping process, including the limitations of current QA devices and the need for careful problem formulation. Furthermore, we analyze the potential advantages of QA over classical optimization techniques, particularly concerning the exploration of a wider solution space. The research highlights the promise of QACO as a viable approach for tackling computationally demanding combinatorial optimization tasks, offering a novel method to enhance optimization efficiency.
The increasing complexity of computational problems in various fields entails the development of efficient methods to solve them. Thus, the emerging technology of quantum computers comes with algorithms, such as quantum annealing, that could solve optimization problems exponentially faster. In particular, to solve the 3SAT problem on quantum annealers, it must be transformed into an instance of Quadratic Unconstrained Binary Optimization (QUBO). Given that the choice of 3SAT-to-QUBO transformation affects the solution quality on quantum annealing, an algorithmic method for creating numerous 3SAT-to-QUBO transformations has recently been proposed, aiming to investigate more deeply such effect. This represents a challenge when deciding which is the best performing 3SAT-to-QUBO transformation that should be used when solving a 3SAT instance on quantum annealing. To overcome this issue, this work investigates the impact of different 3SAT-to-QUBO transformations on the solution quality of simulated annealing, as a classical analogue to quantum annealing. We demonstrate that different QUBO encodings of the same 3SAT instance can lead to different outcomes in terms of energy and clause satisfaction. We also reveal some correlations between 3SAT features, QUBO structural properties, and solution quality. These findings underscore the importance of the choice of 3SAT-to-QUBO transformation in simulated annealing, and provide a foundation for the future development of machine learning models for guiding encoding choices in both classical and quantum environments.
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.
Quantum annealing is a metaheuristic method aimed at finding the global minimum of a pseudo-Boolean quadratic function. To solve a problem by a quantum annealer, it must be restated as a QUBO (quadratic unconstrained binary optimization) problem, the standard format acceptable to an annealer. However, there are many natural problems that turn out be of cubic or higher order, yet promising solutions can be obtained for many instances using quantum annealers, after converting to the QUBO format, using order reduction criteria. Accordingly, quadratization becomes a crucial preprocessing step in order to make use of present-day quantum annealing hardware that relies on coupling technology, which can only process interactions of at most degree two. A critical challenge is that quadratization methods often require many additional variables, degrading the performance of the annealers. A number of algorithmic and heuristic quadratization techniques have been proposed and used for annealing in the literature, affecting the performance of the annealers differently. We examine a number of such quadratization techniques, focusing on their efficiency, compactness, and applicability. We analyze the approaches motivated by diverse goals and highlight the transition from foundational approaches to more recent compact approaches. An evaluation of the current usage of different quadratization methods in the literature is carried out at the end of the survey. Further, we comment on the limitations on usage and show possible opportunities to enhance the performance of annealers.
This paper explores the application of quantum annealing to the field of symbolic regression, a technique for automatically discovering mathematical equations from data. The core idea is to frame the symbolic regression problem as a quadratic unconstrained binary optimization (QUBO) problem, which can then be solved using the quantum annealing algorithm. This approach aims to identify previously unknown mathematical relationships that accurately represent a given dataset. The paper details the methodology, including the mapping process, the QUBO formulation, and the utilization of the quantum annealing solver. We demonstrate, through theoretical analysis and conceptual design, the potential for quantum annealing to outperform classical methods in certain scenarios, particularly when dealing with complex datasets and high-dimensional search spaces. The resulting equations are presented as a set of symbolic expressions, enabling both quantitative analysis and further investigation. The ultimate goal is to provide a framework for automated equation discovery, potentially leading to advancements in various scientific and engineering domains.