Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2502.16212

Clustering-Based Sub-QUBO Extraction for Hybrid QUBO Solvers

Wending Zhao, Tang, Gaoxiang

Published Feb 22, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum Approximate Optimization Algorithm (QAOA) can be used to solve quadratic unconstrained binary optimization (QUBO) problems. However, the size of the solvable problem is limited by the number of qubits. To leverage noisy intermediate-scale quantum (NISQ) devices to solve large-scale QUBO problems, one possible way is to decompose the full problem into multiple sub-problems, which we refer to as the Sub-QUBO Formalism. In this work, we enhance this formalism by proposing a sub-QUBO extraction protocol. To do so, we define a measure to quantify correlations between variables and use it to build a correlation matrix. This matrix serves as the input for clustering algorithms to group variables. Variables belonging to the same group form sub-QUBOs and are subsequently solved using QAOA. Our numerical analysis on several classes of randomly generated QUBO problems demonstrates that this grouping method outperforms previous approaches in terms of objective function values, while maintaining a comparable number of quantum subroutine calls. This method offers wide applicability for solving QUBO problems on NISQ devices.

DOI
10.48550/arxiv.2502.16212

Related papers

Hierarchical Quantum Optimization via Backbone-Driven Problem Decomposition: Integrating Tabu-Search with QAOA

Gou, Minhui, Li, Zeyang, Hong-Ze Xu +6 more

As quantum computing advances, quantum approximate optimization algorithms (QAOA) have shown promise in addressing combinatorial optimization problems. However, the limitations of Noisy Intermediate Scale Quantum (NISQ) devices hinder the scalability of QAOA for large-scale optimization tasks. To overcome these challenges, we propose Backbone-Driven QAOA, a hybrid framework that leverages adaptive Tabu search for classical preprocessing to decompose large-scale quadratic unconstrained binary (QUBO) problems into NISQ-compatible subproblems. In our approach, adaptive Tabu search dynamically identifies and fixes backbone variables to construct reduced-dimensional subspaces that preserve the critical optimization landscape. These quantum-tractable subproblems are then solved via QAOA, with the resulting solutions iteratively refining the backbone selection in a closed-loop quantum-classical cycle. Experimental results demonstrate that our approach not only competes with, and in some cases surpasses, traditional classical algorithms but also performs comparably with recently proposed hybrid classical-quantum algorithms. Our proposed framework effectively orchestrates the allocation of quantum and classical resources, thereby enabling the solution of large-scale combinatorial optimization problems on current NISQ hardware.

arXiv:2504.09575•Apr 13, 2025•0 citations

Construction of SubQUBOs by K-Means Clustering of QUBO Variables

Yuko Kamishima, Shuta Kikuchi, Shu Tanaka

Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.

IEEE Access•Jan 1, 2025•1 citation

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•7 citations

A Multilevel Approach for Solving Large-Scale QUBO Problems with Noisy Hybrid Quantum Approximate Optimization

Filip B. Maciejewski, Bao Gia Bach, Maxime Dupont +5 more

Quantum approximate optimization is one of the promising candidates for useful quantum computation, particularly in the context of finding approximate solutions to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, the existing quantum processing units (QPUs) are of relatively small size, and canonical mappings of QUBO via the Ising model require one qubit per variable, rendering direct large-scale optimization infeasible. In classical optimization, a general strategy for addressing many large-scale problems is via multilevel/multigrid methods, where the large target problem is iteratively coarsened and the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentally test how existing QPUs perform when used as a sub-solver within such a multilevel strategy. To this aim, we combine and extend (via additional classical processing steps) the recently proposed Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax & Round (QRR) algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's superconducting transmon device Ankaa-2. We find approximate solutions to 10 instances of fully connected 82-qubit Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios (ARs) in the range$\sim 0.98-1.0$, and the same class with real-valued coefficients (ARs$\sim 0.94-1.0)$. Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for 6 large-scale graphs with at most$\sim 27,000$variables. In practice, the QPU (with classical post-processing steps) is used to find approximate solutions to dozens of at most 82-qubit problems, which are iteratively used to construct the global solution. We observe that quantum optimization results are competitive in terms of the quality of solutions when compared to classical heuristics used as subsolvers within the multilevel approach. Reproducibility: source code and data will be available at [1].

arXiv:2408.07793•IEEE High Performance Extreme Computing Conference•Sep 23, 2024•5 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•12 citations

Quantum approximate optimization and k-means algorithms for data clustering

Jirawat Saiphet, Sujin Suwanna, Thiparat Chotibut +1 more

Abstract Noisy intermediate-scale quantum (NISQ) devices are cutting-edge technology expected to demonstrate potential and advantages of quantum computing over classical computing. Its low number of qubits and imperfection from noises restrict running full-scale quantum algorithms on such devices; however, quantum advantages can still be obtained. To achieve quantum advantages from NISQ devices, the hybrid quantum-classical algorithms were introduced. Quantum approximate optimization algorithm (QAOA) is a variational hybrid algorithm, which utilizes a NISQ device as a sub-unit for specific tasks and performs most calculations on a classical computer. QAOA provides an approximate solution, with arbitrary precision as the number of operations increases, for optimization problems. In this work we investigate the possibility of applying QAOA to a clustering problem and compare its performance with the classical k-means algorithm. It turns out that the weights in graph connectivity can degrade the algorithm operation and make it more difficult to approximate the solution. We also benchmark the QAOA by comparing the approximated solutions with the exact one obtained from a classical clustering algorithm.

Journal of Physics Conference Series•Jan 1, 2021•3 citations
Quantum Approximate Optimization Algorithm (QAOA) can be used to solve quadratic unconstrained binary optimization (QUBO) problems. However, the size of the solvable problem is limited by the number of qubits. To leverage noisy intermediate-scale quantum (NISQ) devices to solve large-scale QUBO problems, one possible way is to decompose the full problem into multiple sub-problems, which we refer to as the Sub-QUBO Formalism. In this work, we enhance this formalism by proposing a sub-QUBO extraction protocol. To do so, we define a measure to quantify correlations between variables and use it to build a correlation matrix. This matrix serves as the input for clustering algorithms to group variables. Variables belonging to the same group form sub-QUBOs and are subsequently solved using QAOA. Our numerical analysis on several classes of randomly generated QUBO problems demonstrates that this grouping method outperforms previous approaches in terms of objective function values, while maintaining a comparable number of quantum subroutine calls. This method offers wide applicability for solving QUBO problems on NISQ devices.
As quantum computing advances, quantum approximate optimization algorithms (QAOA) have shown promise in addressing combinatorial optimization problems. However, the limitations of Noisy Intermediate Scale Quantum (NISQ) devices hinder the scalability of QAOA for large-scale optimization tasks. To overcome these challenges, we propose Backbone-Driven QAOA, a hybrid framework that leverages adaptive Tabu search for classical preprocessing to decompose large-scale quadratic unconstrained binary (QUBO) problems into NISQ-compatible subproblems. In our approach, adaptive Tabu search dynamically identifies and fixes backbone variables to construct reduced-dimensional subspaces that preserve the critical optimization landscape. These quantum-tractable subproblems are then solved via QAOA, with the resulting solutions iteratively refining the backbone selection in a closed-loop quantum-classical cycle. Experimental results demonstrate that our approach not only competes with, and in some cases surpasses, traditional classical algorithms but also performs comparably with recently proposed hybrid classical-quantum algorithms. Our proposed framework effectively orchestrates the allocation of quantum and classical resources, thereby enabling the solution of large-scale combinatorial optimization problems on current NISQ hardware.
Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Quantum approximate optimization is one of the promising candidates for useful quantum computation, particularly in the context of finding approximate solutions to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, the existing quantum processing units (QPUs) are of relatively small size, and canonical mappings of QUBO via the Ising model require one qubit per variable, rendering direct large-scale optimization infeasible. In classical optimization, a general strategy for addressing many large-scale problems is via multilevel/multigrid methods, where the large target problem is iteratively coarsened and the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentally test how existing QPUs perform when used as a sub-solver within such a multilevel strategy. To this aim, we combine and extend (via additional classical processing steps) the recently proposed Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax & Round (QRR) algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's superconducting transmon device Ankaa-2. We find approximate solutions to 10 instances of fully connected 82-qubit Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios (ARs) in the range∼0.98−1.0\sim 0.98-1.0∼0.98−1.0, and the same class with real-valued coefficients (ARs∼0.94−1.0)\sim 0.94-1.0)∼0.94−1.0). Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for 6 large-scale graphs with at most∼27,000\sim 27,000∼27,000variables. In practice, the QPU (with classical post-processing steps) is used to find approximate solutions to dozens of at most 82-qubit problems, which are iteratively used to construct the global solution. We observe that quantum optimization results are competitive in terms of the quality of solutions when compared to classical heuristics used as subsolvers within the multilevel approach. Reproducibility: source code and data will be available at [1].
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
Abstract Noisy intermediate-scale quantum (NISQ) devices are cutting-edge technology expected to demonstrate potential and advantages of quantum computing over classical computing. Its low number of qubits and imperfection from noises restrict running full-scale quantum algorithms on such devices; however, quantum advantages can still be obtained. To achieve quantum advantages from NISQ devices, the hybrid quantum-classical algorithms were introduced. Quantum approximate optimization algorithm (QAOA) is a variational hybrid algorithm, which utilizes a NISQ device as a sub-unit for specific tasks and performs most calculations on a classical computer. QAOA provides an approximate solution, with arbitrary precision as the number of operations increases, for optimization problems. In this work we investigate the possibility of applying QAOA to a clustering problem and compare its performance with the classical k-means algorithm. It turns out that the weights in graph connectivity can degrade the algorithm operation and make it more difficult to approximate the solution. We also benchmark the QAOA by comparing the approximated solutions with the exact one obtained from a classical clustering algorithm.