Minimum Bisection Problem: Machine Learning-Based Penalty Parameter Tuning for Optimization on Quantum Annealers

arXiv:2509.19005v2 Announce Type: replace Abstract: The Minimum Bisection Problem is a fundamental, computationally hard graph partitioning 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 penalty parameter that enforces balanced partitions. Selecting this parameter is problem-dependent and typically relies on manual tuning or heuristics. This paper proposes a machine learning-based approach for automatic penalty-parameter tuning developed specifically for the Minimum Bisection Problem. We first derive a graph-dependent initial penalty estimate and then use two Gradient Boosting Regressor models to predict the endpoints of an effective penalty-multiplier interval from the number of nodes, graph density, and the initial estimate. The final penalty is obtained from the predicted interval and used to construct the model solved by D-Wave's quantum annealing solvers. The models were calibrated on 607 Erd\H{o}s-R\'enyi graphs, with Metis and Kernighan-Lin as classical references, and evaluated on 126 independently generated instances with up to 4000 nodes. Under the adopted experimental setup, the predicted penalties enabled the hybrid solver to return balanced partitions for all evaluation instances and lower cut values than Metis in every case.

Abstract:The Minimum Bisection Problem is a fundamental, computationally hard graph partitioning 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 penalty parameter that enforces balanced partitions. Selecting this parameter is problem-dependent and typically relies on manual tuning or heuristics. This paper proposes a machine learning-based approach for automatic penalty-parameter tuning developed specifically for the Minimum Bisection Problem. We first derive a graph-dependent initial penalty estimate and then use two Gradient Boosting Regressor models to predict the endpoints of an effective penalty-multiplier interval from the number of nodes, graph density, and the initial estimate. The final penalty is obtained from the predicted interval and used to construct the model solved by D-Wave's quantum annealing solvers. The models were calibrated on 607 Erdős-Rényi graphs, with Metis and Kernighan-Lin as classical references, and evaluated on 126 independently generated instances with up to 4000 nodes. Under the adopted experimental setup, the predicted penalties enabled the hybrid solver to return balanced partitions for all evaluation instances and lower cut values than Metis in every case.

Quantum Physics (quant-ph); Machine Learning (cs.LG)

arXiv:2509.19005 [quant-ph]

(or arXiv:2509.19005v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2509.19005 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Minimum Bisection Problem: Machine Learning-Based Penalty Parameter Tuning for Optimization on Quantum Annealers

Related coverage