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:2405.09169 · npj Quantum Information

Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems

J. A. Montañez-Barrera, Kristel F. L. Michielsen

Published Aug 4, 2025• 34 citations
arXivHTMLPDF

Abstract

Abstract The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters $${\{{\gamma }_{i},{\beta }_{i}\}}_{i = 0}^{p-1}$$ { γ i , β i } i = 0 p − 1 . While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to N q = 42 qubits and p = 400 layers suggest that the success probability scales as $$P({x}^{* })\approx {2}^{-\eta (p){N}_{q}+C}$$ P ( x * ) ≈ 2 − η ( p ) N q + C , where η ( p ) decreases with increasing p . For example, in Weighted Maxcut instances, η (10) = 0.22 improves to η (100) = 0.05. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to N q = 109 qubits, p = 100, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.

DOI
10.1038/s41534-025-01082-1

Related papers

Extrapolation method to optimize linear-ramp quantum approximate optimization algorithm parameters: Evaluation of runtime scaling

Vanessa Dehn, Martin Zaefferer, Gerhard Hellstern +3 more

The quantum approximate optimization algorithm (QAOA) has been suggested as a promising candidate for the solution of combinatorial optimization problems. Yet, whether—or under what conditions—it may offer an advantage compared with classical algorithms remains to be proven. Using the standard variational form of QAOA requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which constitutes a bottleneck for achieving a potential scaling advantage. The linear-ramp QAOA has been proposed to address this issue, as it relies on only two parameters that have to be optimized. Based on this, we develop a method to estimate suitable values for those parameters through extrapolation, starting from smaller problem sizes (number of qubits) toward larger problem sizes. We apply this method to several use cases, such as portfolio optimization, feature selection, clustering, and weighted maxcut. From results obtained on a noiseless quantum emulator, we evaluate the quantum runtime scaling for finding the optimal solution and compare it with that of classical methods. In the case of portfolio optimization, we demonstrate superior scaling compared with the classical runtime for the problem sizes of up to 28 qubits that we consider in this work.

arXiv:2504.08577•Physical Review A•Jan 15, 2026•2 citations

Evaluating the performance of quantum processing units at large width and depth

J. A. Montañez-Barrera, Kristel F. L. Michielsen, David E. Bernal Neira

Quantum computers have now surpassed classical simulation limits, yet noise continues to limit their practical utility. As the field shifts from proof-of-principle demonstrations to early deployments, there is no standard method for meaningfully and scalably comparing heterogeneous quantum hardware. Existing benchmarks typically focus on gate-level fidelity or constant-depth circuits, offering limited insight into algorithmic performance at depth. Here we introduce a benchmarking protocol based on the linear ramp quantum approximate optimization algorithm (LR-QAOA), a fixed-parameter, deterministic variant of QAOA. LR-QAOA quantifies a QPU's ability to preserve a coherent signal as circuit depth increases, identifying when performance becomes statistically indistinguishable from random sampling. We apply this protocol to 24 quantum processors from six vendors, testing problems with up to 156 qubits and 10,000 layers across 1D-chains, native layouts, and fully connected topologies. This constitutes the most extensive cross-platform quantum benchmarking effort to date, with circuits reaching a million two-qubit gates. LR-QAOA offers a scalable, unified benchmark across platforms and architectures, making it a tool for tracking performance in quantum computing.

arXiv:2502.06471•Feb 10, 2025•0 citations

Shallow and Robust QAOA: Improving Feasibility and Hardware Performance via Linear-Chain and Ramp Schedules

Talha Azfar, Ruimin Ke

Abstract The Quantum Approximate Optimization Algorithm (QAOA) is known to struggle on near-term hardware due to constraint handling, parameter search overhead, and tight depth limits. We address this with a hardware-aware co-design: a linear-ramp parameter schedule paired with a Linear-Chain (LC) ansatz that restricts $ZZ$ interactions to nearest neighbors, lowering swaps and depth. We benchmark Linear-Ramp LC-QAOA against standard QAOA, Two-Step QAOA, and Grover-Mixer QAOA on small VRP instances across ideal simulation, Aer simulation, and IBM Eagle/Heron runs, measuring feasibility, solution quality, and hardware efficiency. Linear-ramp improves convergence and feasibility; LC reduces two-qubit gates and boosts noise robustness. Grover-Mixer and Two-Step can aid constraints in theory but are hampered in practice by deeper circuits. On hardware, overall feasibility remains $<1$\%, yet LC-QAOA with $XpXm$ dynamical decoupling more than doubles feasibility and recovers the optimum in several trials. We also show efficient scaling, including a larger case with ramp-initialized LC-QAOA plus CVaR. The results underscore hardware-aligned ansätze and structured schedules as a promising path.

•Jan 5, 2026•0 citations

Multi-angle quantum approximate optimization algorithm

Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski +2 more

The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.

arXiv:2109.11455•Scientific Reports•Apr 26, 2022•117 citations

Quantum algorithms for combinatorial optimization

Vanessa Minouche Dehn

Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.

•Jan 1, 2026•0 citations

Transferring linearly fixed QAOA angles: performance and real device results

Ryo Sakai, Hiromichi Matsuyama, Wai-Hong Tam +1 more

Quantum Approximate Optimization Algorithm (QAOA) enables solving combinatorial optimization problems on quantum computers by optimizing variational parameters for quantum circuits. We investigate a simplified approach that combines linear parameterization with parameter transferring, reducing the parameter space to just 4 dimensions regardless of the number of layers. This simplification draws inspiration from quantum annealing schedules providing both theoretical grounding and practical advantages. We compare this combined approach with standard QAOA and other parameter setting strategies such as INTERP and FOURIER, which require computationally demanding incremental layer-by-layer optimization. Notably, previously known methods like INTERP and FOURIER yield parameters that can be well fitted by linear functions, which supports our linearization strategy. Our analysis reveals that for the random Ising model, cost landscapes in this reduced parameter space demonstrate consistent structural patterns across different problem instances. Our experiments extend from classical simulation to actual quantum hardware implementation on IBM's Eagle processor, demonstrating the approach's viability on current NISQ devices. Furthermore, the numerical results indicate that parameter transferability primarily depends on the energy scale of problem instances, with normalization techniques improving transfer quality. Most of our numerical experiments are conducted on the random Ising model, while problem-dependence is also investigated across other models. A key advantage of parameter transferring is the complete elimination of instance-specific classical optimization overhead, as pre-trained parameters can be directly applied to other problem instances, reducing classical optimization costs by orders of magnitude for deeper circuits.

arXiv:2504.12632•Apr 17, 2025•0 citations
Abstract The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters {γi,βi}i=0p−1{\{{\gamma }_{i},{\beta }_{i}\}}_{i = 0}^{p-1}{γi​,βi​}i=0p−1​ { γ i , β i } i = 0 p − 1 . While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to N q = 42 qubits and p = 400 layers suggest that the success probability scales as P(x∗)≈2−η(p)Nq+CP({x}^{* })\approx {2}^{-\eta (p){N}_{q}+C}P(x∗)≈2−η(p)Nq​+C P ( x * ) ≈ 2 − η ( p ) N q + C , where η ( p ) decreases with increasing p . For example, in Weighted Maxcut instances, η (10) = 0.22 improves to η (100) = 0.05. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to N q = 109 qubits, p = 100, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.
The quantum approximate optimization algorithm (QAOA) has been suggested as a promising candidate for the solution of combinatorial optimization problems. Yet, whether—or under what conditions—it may offer an advantage compared with classical algorithms remains to be proven. Using the standard variational form of QAOA requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which constitutes a bottleneck for achieving a potential scaling advantage. The linear-ramp QAOA has been proposed to address this issue, as it relies on only two parameters that have to be optimized. Based on this, we develop a method to estimate suitable values for those parameters through extrapolation, starting from smaller problem sizes (number of qubits) toward larger problem sizes. We apply this method to several use cases, such as portfolio optimization, feature selection, clustering, and weighted maxcut. From results obtained on a noiseless quantum emulator, we evaluate the quantum runtime scaling for finding the optimal solution and compare it with that of classical methods. In the case of portfolio optimization, we demonstrate superior scaling compared with the classical runtime for the problem sizes of up to 28 qubits that we consider in this work.
Quantum computers have now surpassed classical simulation limits, yet noise continues to limit their practical utility. As the field shifts from proof-of-principle demonstrations to early deployments, there is no standard method for meaningfully and scalably comparing heterogeneous quantum hardware. Existing benchmarks typically focus on gate-level fidelity or constant-depth circuits, offering limited insight into algorithmic performance at depth. Here we introduce a benchmarking protocol based on the linear ramp quantum approximate optimization algorithm (LR-QAOA), a fixed-parameter, deterministic variant of QAOA. LR-QAOA quantifies a QPU's ability to preserve a coherent signal as circuit depth increases, identifying when performance becomes statistically indistinguishable from random sampling. We apply this protocol to 24 quantum processors from six vendors, testing problems with up to 156 qubits and 10,000 layers across 1D-chains, native layouts, and fully connected topologies. This constitutes the most extensive cross-platform quantum benchmarking effort to date, with circuits reaching a million two-qubit gates. LR-QAOA offers a scalable, unified benchmark across platforms and architectures, making it a tool for tracking performance in quantum computing.
Abstract The Quantum Approximate Optimization Algorithm (QAOA) is known to struggle on near-term hardware due to constraint handling, parameter search overhead, and tight depth limits. We address this with a hardware-aware co-design: a linear-ramp parameter schedule paired with a Linear-Chain (LC) ansatz that restricts ZZZZZZ interactions to nearest neighbors, lowering swaps and depth. We benchmark Linear-Ramp LC-QAOA against standard QAOA, Two-Step QAOA, and Grover-Mixer QAOA on small VRP instances across ideal simulation, Aer simulation, and IBM Eagle/Heron runs, measuring feasibility, solution quality, and hardware efficiency. Linear-ramp improves convergence and feasibility; LC reduces two-qubit gates and boosts noise robustness. Grover-Mixer and Two-Step can aid constraints in theory but are hampered in practice by deeper circuits. On hardware, overall feasibility remains <1<1<1\%, yet LC-QAOA with XpXmXpXmXpXm dynamical decoupling more than doubles feasibility and recovers the optimum in several trials. We also show efficient scaling, including a larger case with ramp-initialized LC-QAOA plus CVaR. The results underscore hardware-aligned ansätze and structured schedules as a promising path.
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.
Quantum Approximate Optimization Algorithm (QAOA) enables solving combinatorial optimization problems on quantum computers by optimizing variational parameters for quantum circuits. We investigate a simplified approach that combines linear parameterization with parameter transferring, reducing the parameter space to just 4 dimensions regardless of the number of layers. This simplification draws inspiration from quantum annealing schedules providing both theoretical grounding and practical advantages. We compare this combined approach with standard QAOA and other parameter setting strategies such as INTERP and FOURIER, which require computationally demanding incremental layer-by-layer optimization. Notably, previously known methods like INTERP and FOURIER yield parameters that can be well fitted by linear functions, which supports our linearization strategy. Our analysis reveals that for the random Ising model, cost landscapes in this reduced parameter space demonstrate consistent structural patterns across different problem instances. Our experiments extend from classical simulation to actual quantum hardware implementation on IBM's Eagle processor, demonstrating the approach's viability on current NISQ devices. Furthermore, the numerical results indicate that parameter transferability primarily depends on the energy scale of problem instances, with normalization techniques improving transfer quality. Most of our numerical experiments are conducted on the random Ising model, while problem-dependence is also investigated across other models. A key advantage of parameter transferring is the complete elimination of instance-specific classical optimization overhead, as pre-trained parameters can be directly applied to other problem instances, reducing classical optimization costs by orders of magnitude for deeper circuits.