Numerous established machine learning models and various neural network architectures can be restructured as Quadratic Unconstrained Binary Optimization (QUBO) problems. A significant challenge in Adiabatic Quantum Machine Learning (AQML) is the computational demand of the training phase. To mitigate this, approximation techniques inspired by quantum annealing, like Simulated Annealing and Multiple Start Tabu Search (MSTS), have been employed to expedite QUBO-based AQML training. This paper introduces a novel hybrid algorithm that incorporates an "r-flip" strategy. This strategy is aimed at solving large-scale QUBO problems more effectively, offering better solution quality and lower computational costs compared to existing MSTS methods. The r-flip approach has practical applications in diverse fields, including cross-docking, supply chain management, machine scheduling, and fraud detection. The paper details extensive computational experiments comparing this r-flip enhanced hybrid heuristic against a standard MSTS approach. These tests utilize both standard benchmark problems and three particularly large QUBO instances. The results indicate that the r-flip enhanced method consistently produces high-quality solutions efficiently, operating within practical time constraints.
Numerous established machine learning models and various neural network architectures can be restructured as Quadratic Unconstrained Binary Optimization (QUBO) problems. A significant challenge in Adiabatic Quantum Machine Learning (AQML) is the computational demand of the training phase. To mitigate this, approximation techniques inspired by quantum annealing, like Simulated Annealing and Multiple Start Tabu Search (MSTS), have been employed to expedite QUBO-based AQML training. This paper introduces a novel hybrid algorithm that incorporates an "r-flip" strategy. This strategy is aimed at solving large-scale QUBO problems more effectively, offering better solution quality and lower computational costs compared to existing MSTS methods. The r-flip approach has practical applications in diverse fields, including cross-docking, supply chain management, machine scheduling, and fraud detection. The paper details extensive computational experiments comparing this r-flip enhanced hybrid heuristic against a standard MSTS approach. These tests utilize both standard benchmark problems and three particularly large QUBO instances. The results indicate that the r-flip enhanced method consistently produces high-quality solutions efficiently, operating within practical time constraints.
In this study, we address the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on very-large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
This study addresses the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
Machine learning model training, which ultimately optimizes a model’s cost function is usually a time- consuming and computationally intensive process on classical computers. This has been more intense due to the in- creased demand for large-scale data analysis, requiring unconventional computing paradigms like quantum computing to enhance training efficiency. Adiabatic quantum computers have excelled at solving optimization problems, which require the quadratic unconstrained binary optimization (QUBO) format of the problem of interest. In this study, the squared error minimization in the multiple linear regression model is reformulated as a QUBO problem enabling it to be solved using D-wave adiabatic quantum computers. Same formulation was used to obtain a solution using gate-based algorithms such as quantum approximate optimization algorithm (QAOA) and sampling variational quantum eigensolver (VQE) im- plemented via IBM Qiskit. The results obtained through these approaches in the context of runtime and mean squared error(MSE) were analyzed and compared to the classical approaches. Our experimental results indicate a runtime ad- vantage in the D-wave annealing approach over the classical Scikit learn regression approach. The time advantage can be observed when N>524288 compared to Sklearn Linear Regression and when N>65536 compared to Sklearn SGDRegressor. Support vector machine induced neural networks, where the margin-based entropy loss is converted into a QUBO with Lagrangian approach is also focused in this study concerning the applicability for nonlinear models.
Quadratic Unconstrained Binary Optimization (QUBO) has emerged as a unifying framework for diverse NP-hard combinatorial optimization problems. However, a major challenge in existing QUBO solvers is the need for extensive manual tuning of algorithmic hyperparameters, such as temperature schedules in simulated annealing, which can vary greatly in effectiveness depending on the problem instance. In this paper, we propose RL-assisted annealing(RLA), a novel approach that integrates reinforcement learning (RL) with annealing-based local searches. Rather than relying on hand-crafted heuristics, RLA trains an agent to adaptively determine a bit-flip policy by observing the statistical properties of the energy differences in the objective function. Crucially, RLA encodes QUBO states as fixed-dimensional statistics, making the method scalable to various problem sizes. To further support large-scale problems, we employ distributed training on multi-GPU platforms using JAX’s pmap, parallelizing both environment simulation and policy updates. Experimental evaluations on benchmark datasets, including TSP, QAP, Max-Cut, and randomly generated QUBO instances, demonstrate that RLA achieves solution qualities on par with or better than conventional annealing-based methods, while maintaining robust performance across diverse problem instances without extensive hyperparameter tuning. These results highlight RLA as a promising step toward a flexible and practical solver for QUBO-based applications.
Quadratic Unconstrained Binary Optimization (QUBO) has emerged as a unifying framework for diverse NP-hard combinatorial optimization problems.However, a major challenge in existing QUBO solvers is the need for extensive manual tuning of algorithmic hyperparameters, such as temperature schedules in simulated annealing, which can vary greatly in effectiveness depending on the problem instance.In this paper, we propose RL-driven annealing (RLA), a novel approach that integrates reinforcement learning (RL) with annealing-based local searches.Rather than relying on hand-crafted heuristics, RLA trains an agent to adaptively determine a bit-flip policy by observing the statistical properties of the energy differences in the objective function.Crucially, RLA encodes QUBO states as fixed-dimensional statistics, making the method scalable to various problem sizes.To further support large-scale problems, we employ distributed training on multi-GPU platforms using JAX's pmap, parallelizing both environment simulation and policy updates.Experimental evaluations on benchmark datasets, including TSP, QAP, Max-Cut, and randomly generated QUBO instances, demonstrate that RLA achieves solution qualities on par with or better than conventional annealing-based methods, while maintaining robust performance across diverse problem instances without extensive hyperparameter tuning.These results highlight RLA as a promising step toward a flexible and practical solver for QUBO-based applications.
Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.