⚛️ quantum physics

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

This paper proposes a machine learning-based framework that automatically tunes the penalty parameter for the Minimum Bisection Problem on quantum annealers, using Gradient Boosting Regressors to predict effective penalty intervals and demonstrating superior performance over classical heuristics like Metis in generating balanced partitions with lower cut values.

Original authors: Renáta Rusnáková, Martin Chovanec, Juraj Gazda

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Renáta Rusnáková, Martin Chovanec, Juraj Gazda

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast network of roads, computers, or power lines, all connected in a complex web. To manage such a system efficiently, engineers often need to split it into two equal halves, ensuring that the two new groups are balanced in size while cutting as few connections between them as possible. This task, known as the minimum bisection problem, is a classic challenge in computer science. It is fundamental to everything from designing microchips to organizing data centers, yet finding the perfect split is notoriously difficult. As the network grows, the number of possible ways to cut it explodes, making it nearly impossible for traditional computers to check every option. In recent years, a new type of computer, called a quantum annealer, has emerged as a potential tool to tackle these hard problems. These machines do not calculate answers step-by-step like a standard laptop; instead, they use the strange rules of quantum physics to explore many possibilities at once, seeking the lowest energy state, which corresponds to the best solution. However, for these quantum machines to work correctly, the problem must be translated into a specific mathematical format, and a crucial part of that translation involves a "penalty" value. This value acts like a strict rule that forces the machine to keep the two halves equal in size. If the penalty is too weak, the machine ignores the rule and produces an unbalanced, useless result. If it is too strong, the machine becomes so focused on the rule that it forgets to minimize the actual cuts, leading to a poor solution. Finding the right balance for this penalty has traditionally been a matter of guesswork and manual trial and error.

A team of researchers from the Technical University of Košice in Slovakia has developed a new way to solve this guessing game. Instead of asking a human to tweak the penalty value for every new network, they taught a computer program to predict the perfect setting automatically. The researchers started by generating hundreds of random network maps, ranging from small clusters to massive webs with thousands of nodes. For each map, they ran experiments on a quantum system provided by D-Wave Systems, testing a wide range of penalty values to see which ones produced the best results. They discovered that the ideal penalty value was not random; it followed a pattern based on the size of the network and how densely the nodes were connected. Using this data, they trained two machine learning models, specifically a type of algorithm known as a gradient boosting regressor, to act as a predictor. These models learned to look at a new, unseen network, count its nodes, measure its density, and calculate a rough starting estimate, then output a precise range for the penalty value that would likely work best.

When the researchers tested this new method on 126 completely new networks, the results were striking. In every single case, the machine learning system guided the quantum solver to find a perfectly balanced split. Furthermore, the quality of these splits was superior to those produced by the best traditional software tools currently available. The traditional software, which relies on established classical algorithms, failed to produce a balanced split in about half of the test cases. Even when it did manage to balance the groups, the number of connections it had to cut was consistently higher than what the quantum system achieved with the machine learning-tuned penalty. The researchers found that this improvement held true across all the sizes they tested, from small networks of 100 nodes up to massive ones with 4,000 nodes. The machine learning approach essentially removed the need for the tedious process of manually testing different values, allowing the quantum system to focus entirely on finding the optimal solution.

The study also looked at how this method performed on the actual quantum hardware, rather than just the hybrid system that combines classical and quantum processing. For smaller networks, the direct quantum hardware showed promise, often outperforming traditional methods, though it struggled more with the very dense connections found in some graphs. The researchers noted that the success of their approach relies heavily on the specific type of random networks they used for training. While the method worked perfectly for these synthetic maps, they caution that it would need to be retrained and tested on real-world networks, such as actual road maps or social networks, before being used in those contexts. They also pointed out that the current limitation of quantum hardware means that for very large problems, the hybrid system remains the most practical tool, as it can handle the heavy lifting of preparing the problem while the quantum part searches for the solution.

Ultimately, this work demonstrates that machine learning can serve as a vital bridge between complex optimization problems and emerging quantum technologies. By automating the tuning of critical parameters, the researchers have made the quantum annealing process more reliable and effective. Their findings suggest that as quantum computers continue to evolve, pairing them with intelligent, data-driven tuning systems will be essential for solving real-world problems that are currently too difficult for classical computers to handle efficiently. The study does not claim to have solved the minimum bisection problem for all possible scenarios, but it provides a robust, proven framework for making quantum solutions work better than they ever have before, turning a process that once required expert intuition into one that can be handled by a trained algorithm.

Technical Summary: Machine Learning–Based Penalty Parameter Tuning for Minimum Bisection on Quantum Annealers

Problem Definition
The Minimum Bisection Problem (MBP) is a fundamental NP-hard graph partitioning problem requiring the division of a graph's nodes into two equal-sized subsets while minimizing the number of edges connecting them. While MBP has applications in parallel computing and network design, solving it via Quantum Annealing requires formulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model. A critical challenge in this formulation is the selection of the penalty parameter ( $\lambda$ ), which enforces the balance constraint (equal subset sizes). If $\lambda$ is too small, the solver returns infeasible solutions violating the balance constraint; if too large, the penalty term dominates the objective function, obscuring the cut-minimization goal. Current methods rely on manual tuning or static heuristics, which are often problem-dependent and unreliable across varying graph structures.

Methodology
The authors propose a data-driven framework to automate the selection of $\lambda$ specifically for MBP on quantum annealers. The approach proceeds through four stages:

Theoretical Bounds and Initial Estimation:
The authors derive a graph-dependent initial estimate ( $\lambda_{est}$ ) by analyzing the energy landscape. They establish a theoretical lower bound ( $\lambda \ge 1$ ) and a practical upper bound based on the maximum node degree and graph size ( $\lambda \le \min(\Delta(G), n/2 - 1)$ ). The initial estimate is set to the midpoint of this interval. This method relies solely on measurable graph properties ( $n$ and $\Delta(G)$ ) rather than the generative parameters of the graph, ensuring applicability to arbitrary input graphs.
Empirical Scaling and Calibration:
Preliminary experiments revealed that the theoretical midpoint often required further scaling, particularly for larger graphs. The authors conducted a calibration phase using 607 Erdős–Rényi graphs ( $G(n, p)$ ) with sizes up to 4000 nodes. They tested various multipliers ( $\lambda_{mult}$ ) applied to $\lambda_{est}$ to identify ranges of values that yielded valid balanced partitions with minimal cut sizes using D-Wave's hybrid quantum-classical solver (QA HS).
Machine Learning Prediction:
To eliminate the need for costly manual search over candidate multipliers, the authors trained two Gradient Boosting Regressor (GBR) models.
- Inputs: The models take three features: the number of nodes ( $n$ ), the realized graph density ( $\rho$ ), and the initial penalty estimate ( $\lambda_{est}$ ).
- Outputs: One model predicts the lower bound ( $\lambda_{min}$ ) and the other predicts the upper bound ( $\lambda_{max}$ ) of the effective multiplier interval.
- Final Calculation: The final penalty parameter is computed as $\lambda = \lambda_{est} \times \frac{\lambda_{min} + \lambda_{max}}{2}$ .
Experimental Evaluation:
The trained models were evaluated on 126 independently generated Erdős–Rényi graphs (up to 4000 nodes) and compared against classical baselines: Metis (multilevel partitioning) and Kernighan–Lin (local refinement). Direct QPU experiments were also conducted on smaller graphs ( $n \le 100$ ) to assess hardware-specific performance.

Key Contributions

MBP-Specific Framework: The paper introduces a framework that combines a graph-dependent analytical estimate with machine learning to predict an effective penalty-multiplier interval, moving beyond generic penalty tuning.
Calibration Dataset: The authors generated and utilized a dataset of 607 Erdős–Rényi graphs to train the models and evaluated them on 126 unseen instances, covering a wide range of sizes (up to 4000 nodes) and densities.
Performance Validation: The study demonstrates that the learned penalty selection enables the hybrid solver to find valid balanced partitions for 100% of the evaluation instances, a significant improvement over initial heuristic estimates.

Results

Feasibility: Under the adopted experimental setup, the GBR-predicted penalty parameters allowed the D-Wave hybrid solver to return balanced partitions for all 126 evaluation instances.
Solution Quality: The hybrid solver using the predicted penalties achieved lower cut values (fewer cut edges) than Metis in 100% of the evaluated cases. Statistical analysis using the Wilcoxon signed-rank test confirmed these differences were significant ( $p < 0.001$ ).
Direct QPU Performance: For small graphs ( $n \le 100$ ), the QPU outperformed Metis in the majority of instances for $n \ge 80$ , though performance was mixed for smaller graphs, likely due to the model being trained primarily on larger instances.
Model Accuracy: The GBR model for the upper bound ( $\lambda_{max}$ ) achieved a high $R^2$ score of 0.9028. The lower bound model ( $\lambda_{min}$ ) had a lower $R^2$ (0.4489) due to the low variance in the target values, but maintained low absolute error (MAE 0.0124).

Significance and Claims
The paper claims that its primary contribution is not the general concept of automatic penalty tuning, but a specific, MBP-focused framework that derives an empirically effective penalty range from basic graph properties. The authors assert that this data-driven approach improves the reliability and solution quality of MBP on quantum annealers, reducing the need for repeated manual parameter testing.

The study positions itself as a step toward making QUBO formulations more robust for quantum hardware. The authors explicitly note that their results are specific to the Erdős–Rényi graph distribution and the D-Wave hybrid solver configuration used. They do not claim universal superiority over all classical algorithms (e.g., they acknowledge Metis is significantly faster in terms of raw runtime) but argue that the proposed tuning makes the quantum approach competitive in solution quality while ensuring feasibility. Future work is identified as extending the framework to other graph families, real-world benchmarks, and $k$ -partitioning problems.

Technical Summary: Machine Learning–Based Penalty Parameter Tuning for Minimum Bisection on Quantum Annealers

More like this