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].

Quantum annealers have been designed to propose near-optimal solutions to NP-hard optimization problems. However, the accuracy of current annealers such as the ones of D-Wave Systems, Inc., is limited by environmental noise and hardware biases. One way to deal with these imperfections and to improve the quality of the annealing results is to apply a variety of pre-processing techniques such as spin reversal (SR), anneal offsets (AO), or chain weights (CW). Maximizing the effectiveness of these techniques involves performing optimizations over a large number of parameters, which would be too costly if needed to be done for each new problem instance. In this work, we show that the aforementioned parameter optimization can be done for an entire class of problems, given each instance uses a previously chosen fixed embedding. Specifically, in the training phase, we fix an embedding E of a complete graph onto the hardware of the annealer, and then run an optimization algorithm to tune the following set of parameter values: the set of bits to be flipped for SR, the specific qubit offsets for AO, and the distribution of chain weights, optimized over a set of training graphs randomly chosen from that class, where the graphs are embedded onto the hardware using E. In the testing phase, we estimate how well the parameters computed during the training phase work on a random selection of other graphs from that class. We investigate graph instances of varying densities for the Maximum Clique, Maximum Cut, and Graph Partitioning problems. Our results indicate that, compared to their default behavior, substantial improvements of the annealing results can be achieved by using the optimized parameters for SR, AO, and CW.

Researchers at Volkswagen have been at the cutting edge of implementing D-Wave quantum computers for a number of complex optimization problems, including traffic flow optimization, among other potential use cases. These efforts are generally focused on developing algorithms suitable for the company's recently purchased 2000-qubit quantum system and have expanded to a range of new machine learning possibilities, including what a research team at the company's U.S. R&D office and the Volkswagen Data:Lab in Munich are calling quantum-assisted cluster analysis. The art and science of clustering is well known for machine learning on classical computing architectures, but the VW approach that has been tailored to perform well on a quantum processor has undergone major alterations. As the team describes, to be mapped to the D-Wave architectures, the problem has to be expressed as a quadratic unconstrained binary optimization problem. Once done, the accuracy of results is similar to the what a classical clustering algorithm can produce.

January 17, 2017 --The dream of useful quantum computing may have just come one step closer. Australian researchers are combining two of the hottest topics in science: quantum computing and machine learning. Specifically, they've succeeded in training an algorithm to predict the evolving state of a simple quantum computer. Such an understanding allows real time stabilization of the system, much as tightrope walker uses a pole for balance, according to a paper published Monday in Nature Communications. That would be a big deal for everyone – from Silicon Valley to Washington, D.C.