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:2408.07793 · IEEE High Performance Extreme Computing Conference

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

Filip B. Maciejewski, Bao Gia Bach, Maxime Dupont, P. Aaron Lott, Bhuvanesh Sundar, David E. Bernal Neira, Ilya Safro, Davide Venturelli

Published Sep 23, 2024• 5 citations
arXivHTMLPDF

Abstract

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

DOI
10.1109/hpec62836.2024.10938438

Related papers

Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping

Filip B. Maciejewski, Jacob Biamonte, Stuart Hadfield +1 more

We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios 0.9 - 0.96 for random, fully connected graphs on n = 82 qubits, using only depth p = 1 QAOA with NDAR. This compares to 0.34 - 0.51 for standard p = 1 QAOA with the same number of function calls.

arXiv:2404.01412•Quantum•Nov 6, 2025•10 citations

Solving Large-Scale QUBO with Transferred Parameters from Multilevel QAOA of Low Depth

Bao Gia Bach, Filip B. Maciejewski, Ilya Safro

The Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum approach for tackling combinatorial optimization problems. However, hardware constraints such as limited scaling and susceptibility to noise pose significant challenges when applying QAOA to large instances. To overcome these limitations, scalable hybrid multilevel strategies have been proposed. In this work we propose a fast hybrid multilevel algorithm with QAOA parameterization throughout the multilevel hierarchy and its reinforcement with genetic algorithms, which results in a high-quality, low-depth QAOA solver. Notably, we propose transferring parameters from the coarsest level to the finer level, demonstrating that the relaxation-based coarsening preserves the problem's structural information required for QAOA parametrization. Our strategy improves the coarsening phase and leverages both Quantum Relax & Round and genetic algorithms to incorporate$p=1$QAOA samples effectively. The results highlight the practical potential of multilevel QAOA as a scalable method for combinatorial optimization on near-term quantum devices.

arXiv:2505.11464•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Quantum and Classical Multilevel Algorithms for (Hyper)Graphs

Ruslan Shaydulin

Combinatorial optimization problems on (hyper)graphs are ubiquitous in science and industry. Because many of these problems are NP-hard, development of sophisticated heuristics is of utmost importance for practical problems. In recent years, the emergence of Noisy Intermediate-Scale Quantum (NISQ) computers has opened up the opportunity to dramaticaly speedup combinatorial optimization. However, the adoption of NISQ devices is impeded by their severe limitations, both in terms of the number of qubits, as well as in their quality. NISQ devices are widely expected to have no more than hundreds to thousands of qubits with very limited error-correction, imposing a strict limit on the size and the structure of the problems that can be tackled directly. A natural solution to this issue is hybrid quantum-classical algorithms that combine a NISQ device with a classical machine with the goal of capturing “the best of both worlds”.\nBeing motivated by lack of high quality optimization solvers for hypergraph partitioning, in this thesis, we begin by discussing classical multilevel approaches for this problem. We present a novel relaxation-based vertex similarity measure termed algebraic distance for hypergraphs and the coarsening schemes based on it. Extending the multilevel method to include quantum optimization routines, we present Quantum Local Search (QLS) – a hybrid iterative improvement approach that is inspired by the classical local search approaches. Next, we introduce the Multilevel Quantum Local Search (ML-QLS) that incorporates the quantum-enhanced iterative improvement scheme introduced in QLS within the multilevel framework, as well as several techniques to further understand and improve the effectiveness of Quantum Approximate Optimization Algorithm used throughout our work.

•Jan 1, 2020•0 citations

Multilevel Combinatorial Optimization across Quantum Architectures

Hayato Ushijima-Mwesigwa, Ruslan Shaydulin, Christian F. A. Negre +3 more

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].

arXiv:1910.09985•ACM Transactions on Quantum Computing•Feb 13, 2021•57 citations

Quantum Approximate Optimization Algorithm on Different Qubit Systems

Seongmin Kim, In‐Saeng Suh, E. A. Coello Pérez +6 more

Solving optimization problems is critical across many research domains, but the high dimensionality of parameter spaces often poses significant challenges. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for accelerating optimization in the Noisy Intermediate-Scale Quantum (NISQ) era by leveraging both classical and quantum computational resources. However, its performance can vary depending on the underlying quantum hardware architecture. In this work, we evaluate the performance of QAOA on different quantum hardware platforms, specifically, superconducting transmon qubits and trapped-ion qubits, targetting real-world optimization problems formulated as fully connected Quadratic Unconstrained Binary Optimization (QUBO) instances. We evaluate both the solution quality and time-to-solution using dense QUBO matrices. Furthermore, we show that large-scale problems, such as a 100-bit QUBO instance, can be effectively tackled by integrating quantum computing with high-performance computing (HPC) resources. This study provides practical insights into the strengths and limitations of different qubit technologies and advances the application of quantum computing in solving real-world optimization problems.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Clustering-Based Sub-QUBO Extraction for Hybrid QUBO Solvers

Wending Zhao, Tang, Gaoxiang

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.

arXiv:2502.16212•Feb 22, 2025•0 citations
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].
We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios 0.9 - 0.96 for random, fully connected graphs on n = 82 qubits, using only depth p = 1 QAOA with NDAR. This compares to 0.34 - 0.51 for standard p = 1 QAOA with the same number of function calls.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum approach for tackling combinatorial optimization problems. However, hardware constraints such as limited scaling and susceptibility to noise pose significant challenges when applying QAOA to large instances. To overcome these limitations, scalable hybrid multilevel strategies have been proposed. In this work we propose a fast hybrid multilevel algorithm with QAOA parameterization throughout the multilevel hierarchy and its reinforcement with genetic algorithms, which results in a high-quality, low-depth QAOA solver. Notably, we propose transferring parameters from the coarsest level to the finer level, demonstrating that the relaxation-based coarsening preserves the problem's structural information required for QAOA parametrization. Our strategy improves the coarsening phase and leverages both Quantum Relax & Round and genetic algorithms to incorporatep=1p=1p=1QAOA samples effectively. The results highlight the practical potential of multilevel QAOA as a scalable method for combinatorial optimization on near-term quantum devices.
Combinatorial optimization problems on (hyper)graphs are ubiquitous in science and industry. Because many of these problems are NP-hard, development of sophisticated heuristics is of utmost importance for practical problems. In recent years, the emergence of Noisy Intermediate-Scale Quantum (NISQ) computers has opened up the opportunity to dramaticaly speedup combinatorial optimization. However, the adoption of NISQ devices is impeded by their severe limitations, both in terms of the number of qubits, as well as in their quality. NISQ devices are widely expected to have no more than hundreds to thousands of qubits with very limited error-correction, imposing a strict limit on the size and the structure of the problems that can be tackled directly. A natural solution to this issue is hybrid quantum-classical algorithms that combine a NISQ device with a classical machine with the goal of capturing “the best of both worlds”.\nBeing motivated by lack of high quality optimization solvers for hypergraph partitioning, in this thesis, we begin by discussing classical multilevel approaches for this problem. We present a novel relaxation-based vertex similarity measure termed algebraic distance for hypergraphs and the coarsening schemes based on it. Extending the multilevel method to include quantum optimization routines, we present Quantum Local Search (QLS) – a hybrid iterative improvement approach that is inspired by the classical local search approaches. Next, we introduce the Multilevel Quantum Local Search (ML-QLS) that incorporates the quantum-enhanced iterative improvement scheme introduced in QLS within the multilevel framework, as well as several techniques to further understand and improve the effectiveness of Quantum Approximate Optimization Algorithm used throughout our work.
Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].
Solving optimization problems is critical across many research domains, but the high dimensionality of parameter spaces often poses significant challenges. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for accelerating optimization in the Noisy Intermediate-Scale Quantum (NISQ) era by leveraging both classical and quantum computational resources. However, its performance can vary depending on the underlying quantum hardware architecture. In this work, we evaluate the performance of QAOA on different quantum hardware platforms, specifically, superconducting transmon qubits and trapped-ion qubits, targetting real-world optimization problems formulated as fully connected Quadratic Unconstrained Binary Optimization (QUBO) instances. We evaluate both the solution quality and time-to-solution using dense QUBO matrices. Furthermore, we show that large-scale problems, such as a 100-bit QUBO instance, can be effectively tackled by integrating quantum computing with high-performance computing (HPC) resources. This study provides practical insights into the strengths and limitations of different qubit technologies and advances the application of quantum computing in solving real-world optimization problems.
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.