Quantum Annealing for Minimum Bisection Problem: A Machine Learning-based Approach for Penalty Parameter Tuning

Abstract--The Minimum Bisection Problem is a well-known NP-hard problem in combinatorial optimization, with practical applications in areas such as parallel computing, network design, and machine learning. In this paper, we examine the potential of using D-Wave Systems' quantum annealing solvers to solve the Minimum Bisection Problem, which we formulate as a Quadratic Unconstrained Binary Optimization model. A key challenge in this formulation lies in choosing an appropriate penalty parameter, as it plays a crucial role in ensuring both the quality of the solution and the satisfaction of the problem's constraints. T o address this, we introduce a novel machine learning-based approach for adaptive tuning of the penalty parameter . Specifically, we use a Gradient Boosting Regressor model trained to predict suitable penalty parameter values based on structural properties of the input graph, the number of nodes and the graph's density. This method enables the penalty parameter to be adjusted dynamically for each specific problem instance, improving the solver's ability to balance the competing goals of minimizing the cut size and maintaining equally sized partitions. We test our approach on a large dataset of randomly generated Erd os-R enyi graphs with up to 4000 nodes, and we compare the results with classical partitioning algorithms, Metis and Kernighan-Lin. Experimental findings demonstrate that our adaptive tuning strategy significantly improves the performance of quantum annealing hybrid solver and consistently outperforms the classical methods used, indicating its potential as an alternative for graph partitioning problem. RAPH partitioning is a fundamental problem in combinatorial optimization with applications in task scheduling for multiprocessor computers with focus on parallel computation, partitioning the circuit with applications in microchips design, social network analysis e.g. The problem involves dividing a given graph G into two or more subsets while optimizing certain objective, such as minimizing the number of inter-edges and/or assigned costs between them and producing balanced partitions. While general Graph Partitioning Problem (GPP) allow for flexible partition sizes, a significant special case is the Minimum Bisection Problem (MBP), where the graph is partitioned into two equal-sized subsets while minimizing the number of inter-edges [1].