Minimum Bisection Problem: Machine learning-based penalty parameter tuning for optimization on quantum annealers

Abstract

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.