The Minimum Bisection Problem is a fundamental NP-hard problem with applications in parallel computing, network design, and large-scale data processing. When formulated as a Quadratic Unconstrained Binary Optimization problem for quantum annealing, solution quality depends critically on the choice of the penalty parameter that enforces balanced partitions. However, selecting this parameter is problem-dependent and typically relies on manual tuning or heuristics, limiting practical applicability in engineering settings. This paper proposes a machine learning–based approach for automatic penalty parameter tuning. We employ a Gradient Boosting Regressor to predict suitable penalty values from structural graph features, specifically the number of nodes and graph density. The predicted parameter is then used to construct the model solved by D-Wave’s quantum annealing solvers. The proposed method is evaluated on a large dataset of Erdős–Rényi graphs with up to 4,000 nodes and compared against classical partitioning heuristics, including Metis and Kernighan–Lin algorithms. Experimental results show that the learned parameter selection significantly improves constraint satisfaction and cut minimization, enabling the hybrid quantum annealing solver to consistently outperform classical baselines.
The Minimum Bisection Problem is a fundamental NP-hard problem with applications in parallel computing, network design, and large-scale data processing. When formulated as a Quadratic Unconstrained Binary Optimization problem for quantum annealing, solution quality depends critically on the choice of the penalty parameter that enforces balanced partitions. However, selecting this parameter is problem-dependent and typically relies on manual tuning or heuristics, limiting practical applicability in engineering settings. This paper proposes a machine learning–based approach for automatic penalty parameter tuning. We employ a Gradient Boosting Regressor to predict suitable penalty values from structural graph features, specifically the number of nodes and graph density. The predicted parameter is then used to construct the model solved by D-Wave’s quantum annealing solvers. The proposed method is evaluated on a large dataset of Erdős–Rényi graphs with up to 4,000 nodes and compared against classical partitioning heuristics, including Metis and Kernighan–Lin algorithms. Experimental results show that the learned parameter selection significantly improves constraint satisfaction and cut minimization, enabling the hybrid quantum annealing solver to consistently outperform classical baselines.
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.
Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability number of the graph, and its computation is an NP-hard problem. In this paper, we solve the stable set problem using the D-Wave quantum annealer. By formulating the problem as a quadratic unconstrained binary optimization problem with the penalty method, we show its optimal value equals the graph's stability number for specific penalty values. However, D-Wave's quantum annealer is a heuristic, so the solutions may be far from the optimum and may not represent stable sets. To address these, we introduce a post-processing procedure that identifies samples that could lead to improved solutions. Additionally, we propose a partitioning method to handle larger instances that cannot be embedded on D-Wave's quantum processing unit. Finally, we investigate how different penalty parameter values affect the solutions' quality. Extensive computational results show that the post-processing procedure significantly improves the solution quality, while the partitioning method successfully extends our approach to medium-size instances.
Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability number of the graph, and its computation is an NP-hard problem. In this paper, we solve the stable set problem using the D-Wave quantum annealer. By formulating the problem as a quadratic unconstrained binary optimization problem with the penalty method, we show its optimal value equals the graph's stability number for specific penalty values. However, D-Wave's quantum annealer is a heuristic, so the solutions may be far from the optimum and may not represent stable sets. To address these, we introduce a post-processing procedure that identifies samples that could lead to improved solutions. Additionally, we propose a partitioning method to handle larger instances that cannot be embedded on D-Wave's quantum processing unit. Finally, we investigate how different penalty parameter values affect the solutions' quality. Extensive computational results show that the post-processing procedure significantly improves the solution quality, while the partitioning method successfully extends our approach to medium-size instances.
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.
The recent availability of quantum annealers as cloud-based services has enabled new ways to handle machine learning problems, and several relevant algorithms have been adapted to run on these devices. In a recent work, linear regression was formulated as a quadratic binary optimization problem that can be solved via quantum annealing. Although this approach promises a computational time advantage for large datasets, the quality of the solution is limited by the necessary use of a precision vector, used to approximate the real-numbered regression coefficients in the quantum formulation. In this work, we focus on the practical challenge of improving the precision vector encoding: instead of setting an array of generic values equal for all coefficients, we allow each one to be expressed by its specific precision, which is tuned with a simple adaptive algorithm. This approach is evaluated on synthetic datasets of increasing size, and linear regression is solved using the D-Wave Advantage quantum annealer, as well as classical solvers. To the best of our knowledge, this is the largest dataset ever evaluated for linear regression on a quantum annealer. The results show that our formulation is able to deliver improved solution quality in all instances, and could better exploit the potential of current quantum devices.
Cybersecurity in telecommunication networks often leads to hard combinatorial optimization problems that are challenging to solve with classical methods. This work investigates the practical feasibility of using quantum annealing to address the Restricted Vertex Minimum Multicut Problem. The problem is formulated as a Quadratic Unconstrained Binary Optimization model and implemented on D-Wave’s quantum annealer. Rather than focusing on solution quality alone, we analyze key aspects of the quantum workflow including minor embedding techniques, chain length, topology constraints, chain strength selection, unembedding procedures, and postprocessing. Our results show that quantum annealing faces substantial hardware-level constraints limitations in embedding and scalability, especially for large in-stances, while hybrid quantum-classical solvers provide improved feasibility. This study offers a realistic assessment of the D-Wave system’s current capabilities and identifies crucial parameters that govern the success of quantum optimization in cybersecurity-related network problems.