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:2505.11464 · IEEE International Conference on Quantum Computing and Engineering (QCE)

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

Bao Gia Bach, Filip B. Maciejewski, Ilya Safro

Published Aug 30, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1109/qce65121.2025.00232

Related papers

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

Scaling QAOA: transferring optimal adiabatic schedules from small-scale to large-scale variational circuits

Ugo Nzongani, Dylan Laplace Mermoud, Arthur Braida

The Quantum Approximate Optimization Algorithm (QAOA) is a leading approach for combinatorial optimization on near-term quantum devices, yet its scalability is limited by the difficulty of optimizing \(2p\) variational parameters for a large number \(p\) of layers. Recent empirical studies indicate that optimal QAOA angles exhibit concentration and transferability across problem sizes. Leveraging this observation, we propose a schedule-learning framework that transfers spectral-gap-informed adiabatic control strategies from small-scale instances to larger systems. Our method extracts the spectral gap profile of small problems and constructs a continuous schedule governed by \(\partial_t s = κg^q(s)\), where \(g(s)\) is the instantaneous gap and \((κ, q)\) are global hyperparameters. Discretizing this schedule yields closed-form expressions for all QAOA angles, reducing the classical optimization task from \(2p\) parameters to only \(2\), independent of circuit depth. This drastic parameter compression mitigates classical optimization overhead and reduces sensitivity to barren plateau phenomena. Numerical simulations on random QUBO and 3-regular MaxCut instances demonstrate that the learnt schedules transfer effectively to larger systems while achieving competitive approximation ratios. Our results suggest that gap-informed schedule transfers provide a scalable and parameter-efficient strategy for QAOA.

quant-pharXiv:2602.14986•IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Feb 17, 2026•0 citations

Parameter Transferability in QAOA Under Noisy Conditions

Quinn Langfitt, Jose Falla, Ilya Safro +1 more

The quantum approximate optimization algorithm (QAOA) is widely recognized for its potential to deliver quantum advantage in combinatorial optimization tasks. As a hybrid classical-quantum algorithm, it achieves an approximate solution to the combinatorial optimization problem by preparing a specific quantum state via a classical optimization of the quantum circuit parameters. A key property of QAOA is the observed concentration and transferability of optimal parameters across distinct problem instances, linked to local graph characteristics such as subgraph types (lightcones) and node degrees (parity) [1]. However, quantum noise poses a critical challenge in the current NISQ era, hindering the performance of QAOA, particularly for large system sizes. In this follow-up study, we investigate the resilience of parameter transferability under noisy conditions. Leveraging zero-noise extrapolation (ZNE), we evaluate the transferability's robustness across various random graphs under different noise levels. Our analysis reveals that the transferability of optimal parameters from smaller ‘donor’ graphs to larger ‘acceptor’ graphs retains its effectiveness, even under substantial noise when combined with ZNE. Importantly, by illustrating that QAOA parameter transferability can still be exploited effectively among NISQ devices, we offer a pragmatic approach to enhance the algorithm's performance. Our research reinforces the promise of QAOA for large-scale applications under the practical challenges of quantum noise.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•1 citation

Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.

arXiv:1907.09631•Jul 13, 2019•33 citations

Sampling-Based Quantum Optimization Algorithm with Quantum Relaxation

Hiromichi Matsuyama, Yu Yamashiro

Combinatorial optimization is one of the promising applications of quantum computation. Variational Quantum Algorithm (VQA) is a classical-quantum hybrid algorithm framework for noisy quantum devices. However, the quality of the solution is readily affected by statistical fluctuations and physical noise, making it challenging to maintain applicability for largescale problems. In contrast, sampling-based quantum algorithms have recently been successfully applied to large-scale quantum chemistry problems. In the sampling-based framework, the quantum device is used only for sampling, while the ground state and its energy are estimated on the classical device. In this study, we propose the Sampling-based Quantum Optimization Algorithm (SQOA) that leverages these advantages for combinatorial optimization. There are two challenges in constructing SQOA. The first challenge is that we need to encode the optimization problem in a non-diagonal Hamiltonian, even though many VQAs encode it into the Ising Hamiltonian, which is diagonal. The second challenge is that we need a method for efficient preparation of the input state to be sampled. To address the first challenge, we utilize the Quantum Relaxation (QR) method for encoding an optimization problem within a Hamiltonian. This method achieves a higher encoding density by mapping multiple variables to a single qubit, thus requiring fewer qubits for larger problems compared to the Ising Hamiltonian approach. Moreover, to address the second challenge, we investigate the parameter transferability within the Quantum Alternating Operator Ansatz for QR Hamiltonians. We show that restricting parameters to a linear form exhibits moderate transferability for 3-regular Max-Cut problems, similar to transferability observed in the Quantum Approximate Optimization Algorithm. Therefore, this property allows us to efficiently prepare the input state for a large problem instance using the parameters obtained from a small problem instance. We leveraged transferability to create input states and applied SQOA with QR to the Max-Cut instances. By transferring parameters from a 20-node problem, we demonstrate that SQOA with QR provides high-quality solutions for 40-node problems without variational parameter optimization.

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

MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA

Bao Bach, Jose Falla, Ilya Safro

Learning the problem structure at multiple levels of coarseness to inform the decomposition-based hybrid quantum-classical combinatorial optimization solvers is a promising approach to scaling up variational approaches. We introduce a multilevel algorithm reinforced with the spectral graph representation learning-based accelerator to tackle large-scale graph maximum cut instances and fused with several versions of the quantum approximate optimization algorithm (QAOA) and QAOA-inspired algorithms. The graph representation learning model utilizes the idea of QAOA variational parameters concentration and substantially improves the performance of QAOA. We demonstrate the potential of using multilevel QAOA and representation learning-based approaches on extensive graphs by achieving high-quality solutions much faster. Reproducibility: Our source code and results are available at https://github.com/bachbao/MLQAOA.

arXiv:2404.14399•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•6 citations
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.
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].
The Quantum Approximate Optimization Algorithm (QAOA) is a leading approach for combinatorial optimization on near-term quantum devices, yet its scalability is limited by the difficulty of optimizing 2p2p2p variational parameters for a large number ppp of layers. Recent empirical studies indicate that optimal QAOA angles exhibit concentration and transferability across problem sizes. Leveraging this observation, we propose a schedule-learning framework that transfers spectral-gap-informed adiabatic control strategies from small-scale instances to larger systems. Our method extracts the spectral gap profile of small problems and constructs a continuous schedule governed by ∂ts=κgq(s)\partial_t s = κg^q(s)∂t​s=κgq(s), where g(s)g(s)g(s) is the instantaneous gap and (κ,q)(κ, q)(κ,q) are global hyperparameters. Discretizing this schedule yields closed-form expressions for all QAOA angles, reducing the classical optimization task from 2p2p2p parameters to only 222, independent of circuit depth. This drastic parameter compression mitigates classical optimization overhead and reduces sensitivity to barren plateau phenomena. Numerical simulations on random QUBO and 3-regular MaxCut instances demonstrate that the learnt schedules transfer effectively to larger systems while achieving competitive approximation ratios. Our results suggest that gap-informed schedule transfers provide a scalable and parameter-efficient strategy for QAOA.
The quantum approximate optimization algorithm (QAOA) is widely recognized for its potential to deliver quantum advantage in combinatorial optimization tasks. As a hybrid classical-quantum algorithm, it achieves an approximate solution to the combinatorial optimization problem by preparing a specific quantum state via a classical optimization of the quantum circuit parameters. A key property of QAOA is the observed concentration and transferability of optimal parameters across distinct problem instances, linked to local graph characteristics such as subgraph types (lightcones) and node degrees (parity) [1]. However, quantum noise poses a critical challenge in the current NISQ era, hindering the performance of QAOA, particularly for large system sizes. In this follow-up study, we investigate the resilience of parameter transferability under noisy conditions. Leveraging zero-noise extrapolation (ZNE), we evaluate the transferability's robustness across various random graphs under different noise levels. Our analysis reveals that the transferability of optimal parameters from smaller ‘donor’ graphs to larger ‘acceptor’ graphs retains its effectiveness, even under substantial noise when combined with ZNE. Importantly, by illustrating that QAOA parameter transferability can still be exploited effectively among NISQ devices, we offer a pragmatic approach to enhance the algorithm's performance. Our research reinforces the promise of QAOA for large-scale applications under the practical challenges of quantum noise.
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.
Combinatorial optimization is one of the promising applications of quantum computation. Variational Quantum Algorithm (VQA) is a classical-quantum hybrid algorithm framework for noisy quantum devices. However, the quality of the solution is readily affected by statistical fluctuations and physical noise, making it challenging to maintain applicability for largescale problems. In contrast, sampling-based quantum algorithms have recently been successfully applied to large-scale quantum chemistry problems. In the sampling-based framework, the quantum device is used only for sampling, while the ground state and its energy are estimated on the classical device. In this study, we propose the Sampling-based Quantum Optimization Algorithm (SQOA) that leverages these advantages for combinatorial optimization. There are two challenges in constructing SQOA. The first challenge is that we need to encode the optimization problem in a non-diagonal Hamiltonian, even though many VQAs encode it into the Ising Hamiltonian, which is diagonal. The second challenge is that we need a method for efficient preparation of the input state to be sampled. To address the first challenge, we utilize the Quantum Relaxation (QR) method for encoding an optimization problem within a Hamiltonian. This method achieves a higher encoding density by mapping multiple variables to a single qubit, thus requiring fewer qubits for larger problems compared to the Ising Hamiltonian approach. Moreover, to address the second challenge, we investigate the parameter transferability within the Quantum Alternating Operator Ansatz for QR Hamiltonians. We show that restricting parameters to a linear form exhibits moderate transferability for 3-regular Max-Cut problems, similar to transferability observed in the Quantum Approximate Optimization Algorithm. Therefore, this property allows us to efficiently prepare the input state for a large problem instance using the parameters obtained from a small problem instance. We leveraged transferability to create input states and applied SQOA with QR to the Max-Cut instances. By transferring parameters from a 20-node problem, we demonstrate that SQOA with QR provides high-quality solutions for 40-node problems without variational parameter optimization.
Learning the problem structure at multiple levels of coarseness to inform the decomposition-based hybrid quantum-classical combinatorial optimization solvers is a promising approach to scaling up variational approaches. We introduce a multilevel algorithm reinforced with the spectral graph representation learning-based accelerator to tackle large-scale graph maximum cut instances and fused with several versions of the quantum approximate optimization algorithm (QAOA) and QAOA-inspired algorithms. The graph representation learning model utilizes the idea of QAOA variational parameters concentration and substantially improves the performance of QAOA. We demonstrate the potential of using multilevel QAOA and representation learning-based approaches on extensive graphs by achieving high-quality solutions much faster. Reproducibility: Our source code and results are available at https://github.com/bachbao/MLQAOA.