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:2106.13814 · Physical Review A

Training saturation in layerwise quantum approximate optimization

Ernesto Campos, Daniil Rabinovich, V. Akshay, Jacob Biamonte

Published Sep 15, 2021• 44 citations
arXivHTMLPDF

Abstract

The quantum approximate optimization algorithm (QAOA) is the most studied gate-based variational quantum algorithm today. We train QAOA one layer at a time to maximize overlap with an $n$ qubit target state. Doing so we discovered that such training always saturates---called training saturation---at some depth ${p}^{*}$, meaning that past a certain depth, overlap cannot be improved by adding subsequent layers. We formulate necessary conditions for saturation. Numerically, we find layerwise QAOA reaches its maximum overlap at depth ${p}^{*}=n$ for the problem of state preparation. The addition of coherent dephasing errors to training removes saturation, recovering robustness to layerwise training. This study sheds new light on the performance limitations and prospects of QAOA.

DOI
10.1103/physreva.104.l030401

Related papers

Smart Insert Layerwise learning QAOA for solving MaxCut problem

Jaejoon Gill, Yunpyo Hong, Byung-Soo Kim

In the Noisy Intermediate-Scale Quantum (NISQ) era, the Quantum Approximate Optimization Algorithm (QAOA) has attracted significant attention as an algorithm for solving combinatorial optimization problems that are classically intractable. Various modifications and training strategies have been proposed to enhance the performance of QAOA. However, as the circuit depth increases, existing methods encounter greater training difficulty and reach a barren plateau in performance improvements. In this paper, we propose the Smart Insert Layerwise QAOA (SIL QAOA) to overcome these challenges. In SIL QAOA, at each stage, a new layer is inserted into all possible positions; each circuit is independently optimized, and the parameter set from the circuit yielding the highest expectation value is adopted as the initial parameter for the next stage. Applying the proposed method to the MaxCut problem, we achieved up to approximately 11% higher approximation ratios compared to conventional Layerwise learning QAOA, while successfully mitigating early performance saturation observed at shallow depths. These results demonstrate the superior performance improvement capability of SIL QAOA. Furthermore, we also discuss its potential applicability to more complex optimization problems and deeper variational quantum circuits in future work.

IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia)•Oct 27, 2025•0 citations

A Cyclic Layerwise QAOA Training

Enhyeok Jang, Zihan Chen, Dongho Ha +6 more

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical algorithm for solving combinatorial optimization problems. Multi-angle QAOA (MA-QAOA), which assigns independent parameters to each Hamiltonian operator term, achieves superior approximation performance even with fewer layers than standard QAOA. Unfortunately, this increased expressibility can raise the classical computational cost due to a greater number of parameters. The recently proposed Layerwise MA-QAOA (LMA-QAOA) reduces this overhead by training one layer at a time, but it may suffer from obtaining the precise solution due to the previously fixed parameters. This work addresses two questions for efficient MA-QAOA training: (i) What is the optimal granularity for parameter updates per epoch, and (ii) How can we get precise final cost function results while only partially updating the parameters per epoch? Despite the benefit of reducing the parameters that update per epoch can reduce the classical computation overhead, too fine or coarse a granularity of Hamiltonian update can degrade the MA-QAOA training efficiency. We find that optimizing one complete layer per epoch is an efficient granularity. Moreover, selectively retraining each layer by tracking gradient variations can achieve a final cost function equivalent to the standard MA-QAOA while lowering the parameter update overhead. Based on these insights, we propose Orbit-QAOA, which cyclically revisits layers and selectively freezes stabilized parameters. Across diverse graph benchmarks, Orbit-QAOA reduces training steps by up to 81.8%, reduces approximation ratio error by up to 72x compared to the unified stop condition-applied enhanced LMA-QAOA, and achieves equivalent approximation performance compared to the standard MA-QAOA.

quant-pharXiv:2601.20029•Quantum Machine Intelligence•Jan 29, 2026•1 citation

Iterative layerwise training for the quantum approximate optimization algorithm

Xinwei Lee, Xinjian Yan, Ningyi Xie +3 more

The capability of the quantum approximate optimization algorithm (QAOA) in solving combinatorial optimization problems has been intensively studied in recent years due to its application in the quantum-classical hybrid regime. Despite having difficulties that are innate in the variational quantum algorithms (VQA), such as barren plateaus and the local minima problem, QAOA remains one of the applications that is suitable for the recent noisy intermediate scale quantum (NISQ) devices. Recent works have shown that the performance of QAOA largely depends on the initial parameters, which motivate parameter initialization strategies to obtain good initial points for the optimization of QAOA. On the other hand, optimization strategies focus on the optimization part of QAOA instead of the parameter initialization. Instead of having absolute advantages, these strategies usually impose trade-offs to the performance of the optimization problems. One such example is the layerwise optimization strategy, in which the QAOA parameters are optimized layer by layer instead of the full optimization. The layerwise strategy costs less in total compared to the full optimization, in exchange of lower approximation ratio. In this work, we propose the iterative layerwise optimization strategy and explore the possibility for the reduction of optimization cost in solving problems with QAOA. Using numerical simulations, we found that by combining the iterative layerwise strategy with proper initialization strategies, the optimization cost can be significantly reduced in exchange for a minor reduction in the approximation ratio. We also show that in some cases, the approximation ratio given by the iterative layerwise strategy is even higher than that given by the full optimization.

arXiv:2309.13552•Physical Review A•May 2, 2024•15 citations

Depth scaling of unstructured search via quantum approximate optimization

Ernesto Campos, Daniil Rabinovich, Alexey Uvarov

Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms---the quantum approximate optimization algorithm (QAOA)---was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search, which consists of finding a particular bit string or, equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such a problem we build on its known solution in a continuous time quantum walk (CTQW). We Trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state that approaches perfect overlap with the target state. The obtained complexity exceeds Grover's algorithm complexity $O({N}^{\frac{1}{2}})$, but remains smaller than $O({N}^{\frac{1}{2}+c})$ for any $c>0$, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits.

arXiv:2403.15540•Physical Review A•Jul 9, 2024•3 citations

Addressing Barren Plateaus in QAOA using layer-wise and adaptive optimization

Urvi Sharma

The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quan- tum algorithm for solving combinatorial optimization problems. One major challenge with QAOA arises when the optimizer is unable to progress due to barren plateau problems. To address this, we propose a novel optimization technique called the Layered Quantum Approximate Optimization Al- gorithm (LQAOA), which uses warm-starting by fine-tuning parameters from previously optimized layers to initialize subsequent layers, training one layer at a time. Additionally, we incorporate adaptive layer-adding strategies, where layers are added based on a cost-convergence condition. The optimization approach, tested on Erdős–Rényi graphs for the Max-Cut problem with various hyperparameter settings, demonstrates improved performance over standard QAOA.

Työväentutkimus Vuosikirja•Jan 30, 2025•0 citations

Circuit depth scaling for quantum approximate optimization

V. Akshay, Hariphan Philathong, Ernesto Campos +4 more

Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density---a problem constraint to a variable ratio---induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a $3\ensuremath{\sigma}$ confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5--15 qubits.

arXiv:2205.01698•Physical Review A•Oct 25, 2022•21 citations
The quantum approximate optimization algorithm (QAOA) is the most studied gate-based variational quantum algorithm today. We train QAOA one layer at a time to maximize overlap with an nnn qubit target state. Doing so we discovered that such training always saturates---called training saturation---at some depth p∗{p}^{*}p∗, meaning that past a certain depth, overlap cannot be improved by adding subsequent layers. We formulate necessary conditions for saturation. Numerically, we find layerwise QAOA reaches its maximum overlap at depth p∗=n{p}^{*}=np∗=n for the problem of state preparation. The addition of coherent dephasing errors to training removes saturation, recovering robustness to layerwise training. This study sheds new light on the performance limitations and prospects of QAOA.
In the Noisy Intermediate-Scale Quantum (NISQ) era, the Quantum Approximate Optimization Algorithm (QAOA) has attracted significant attention as an algorithm for solving combinatorial optimization problems that are classically intractable. Various modifications and training strategies have been proposed to enhance the performance of QAOA. However, as the circuit depth increases, existing methods encounter greater training difficulty and reach a barren plateau in performance improvements. In this paper, we propose the Smart Insert Layerwise QAOA (SIL QAOA) to overcome these challenges. In SIL QAOA, at each stage, a new layer is inserted into all possible positions; each circuit is independently optimized, and the parameter set from the circuit yielding the highest expectation value is adopted as the initial parameter for the next stage. Applying the proposed method to the MaxCut problem, we achieved up to approximately 11% higher approximation ratios compared to conventional Layerwise learning QAOA, while successfully mitigating early performance saturation observed at shallow depths. These results demonstrate the superior performance improvement capability of SIL QAOA. Furthermore, we also discuss its potential applicability to more complex optimization problems and deeper variational quantum circuits in future work.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical algorithm for solving combinatorial optimization problems. Multi-angle QAOA (MA-QAOA), which assigns independent parameters to each Hamiltonian operator term, achieves superior approximation performance even with fewer layers than standard QAOA. Unfortunately, this increased expressibility can raise the classical computational cost due to a greater number of parameters. The recently proposed Layerwise MA-QAOA (LMA-QAOA) reduces this overhead by training one layer at a time, but it may suffer from obtaining the precise solution due to the previously fixed parameters. This work addresses two questions for efficient MA-QAOA training: (i) What is the optimal granularity for parameter updates per epoch, and (ii) How can we get precise final cost function results while only partially updating the parameters per epoch? Despite the benefit of reducing the parameters that update per epoch can reduce the classical computation overhead, too fine or coarse a granularity of Hamiltonian update can degrade the MA-QAOA training efficiency. We find that optimizing one complete layer per epoch is an efficient granularity. Moreover, selectively retraining each layer by tracking gradient variations can achieve a final cost function equivalent to the standard MA-QAOA while lowering the parameter update overhead. Based on these insights, we propose Orbit-QAOA, which cyclically revisits layers and selectively freezes stabilized parameters. Across diverse graph benchmarks, Orbit-QAOA reduces training steps by up to 81.8%, reduces approximation ratio error by up to 72x compared to the unified stop condition-applied enhanced LMA-QAOA, and achieves equivalent approximation performance compared to the standard MA-QAOA.
The capability of the quantum approximate optimization algorithm (QAOA) in solving combinatorial optimization problems has been intensively studied in recent years due to its application in the quantum-classical hybrid regime. Despite having difficulties that are innate in the variational quantum algorithms (VQA), such as barren plateaus and the local minima problem, QAOA remains one of the applications that is suitable for the recent noisy intermediate scale quantum (NISQ) devices. Recent works have shown that the performance of QAOA largely depends on the initial parameters, which motivate parameter initialization strategies to obtain good initial points for the optimization of QAOA. On the other hand, optimization strategies focus on the optimization part of QAOA instead of the parameter initialization. Instead of having absolute advantages, these strategies usually impose trade-offs to the performance of the optimization problems. One such example is the layerwise optimization strategy, in which the QAOA parameters are optimized layer by layer instead of the full optimization. The layerwise strategy costs less in total compared to the full optimization, in exchange of lower approximation ratio. In this work, we propose the iterative layerwise optimization strategy and explore the possibility for the reduction of optimization cost in solving problems with QAOA. Using numerical simulations, we found that by combining the iterative layerwise strategy with proper initialization strategies, the optimization cost can be significantly reduced in exchange for a minor reduction in the approximation ratio. We also show that in some cases, the approximation ratio given by the iterative layerwise strategy is even higher than that given by the full optimization.
Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms---the quantum approximate optimization algorithm (QAOA)---was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search, which consists of finding a particular bit string or, equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such a problem we build on its known solution in a continuous time quantum walk (CTQW). We Trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state that approaches perfect overlap with the target state. The obtained complexity exceeds Grover's algorithm complexity O(N12)O({N}^{\frac{1}{2}})O(N21​), but remains smaller than O(N12+c)O({N}^{\frac{1}{2}+c})O(N21​+c) for any c>0c>0c>0, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quan- tum algorithm for solving combinatorial optimization problems. One major challenge with QAOA arises when the optimizer is unable to progress due to barren plateau problems. To address this, we propose a novel optimization technique called the Layered Quantum Approximate Optimization Al- gorithm (LQAOA), which uses warm-starting by fine-tuning parameters from previously optimized layers to initialize subsequent layers, training one layer at a time. Additionally, we incorporate adaptive layer-adding strategies, where layers are added based on a cost-convergence condition. The optimization approach, tested on Erdős–Rényi graphs for the Max-Cut problem with various hyperparameter settings, demonstrates improved performance over standard QAOA.
Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density---a problem constraint to a variable ratio---induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a $3\ensuremath{\sigma}$ confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5--15 qubits.