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

Quantum alternating operator ansatz beyond low depth with gradually changing unitaries

Vladimir Kremenetski, Anuj Apte, Tad Hogg, Stuart Hadfield, Norm M. Tubman

Published Nov 5, 2026• 28 citations
arXivHTMLPDF

Abstract

The Quantum Approximate Optimization Algorithm and its generalization to Quantum Alternating Operator Ansatz (QAOA) is a promising approach for applying quantum computers to challenging problems such as combinatorial optimization and computational chemistry. In this paper, we study the underlying mechanisms governing the behavior of QAOA circuits beyond shallow depth in the practically relevant setting of gradually varying unitaries. We use the discrete adiabatic theorem, which complements and generalizes the insights obtained from the continuous-time adiabatic theorem primarily considered in prior work. Our analysis explains some general properties that are conspicuously depicted in the recently introduced QAOA performance diagrams. For parameter sequences derived from continuous schedules (e.g. linear ramps), these diagrams capture the algorithm's performance over different parameter sizes and circuit depths. Surprisingly, they have been observed to be qualitatively similar across different performance metrics and application domains. Our analysis explains this behavior as well as entails some unexpected results, such as connections between the eigenstates of the cost and mixer QAOA Hamiltonians changing based on parameter size and the possibility of reducing circuit depth without sacrificing performance.

DOI
10.1103/ydpy-by46

Related papers

Quantum Alternating Operator Ansatz (QAOA) Phase Diagrams and Applications for Quantum Chemistry

Vladimir Kremenetski, Tad Hogg, Stuart Hadfield +2 more

Determining Hamiltonian ground states and energies is a challenging task with many possible approaches on quantum computers. While variational quantum eigensolvers are popular approaches for near term hardware, adiabatic state preparation is an alternative that does not require noisy optimization of parameters. Beyond adiabatic schedules, QAOA is an important method for optimization problems. In this work we modify QAOA to apply to finding ground states of molecules and empirically evaluate the modified algorithm on several molecules. This modification applies physical insights used in classical approximations to construct suitable QAOA operators and initial state. We find robust qualitative behavior for QAOA as a function of the number of steps and size of the parameters, and demonstrate this behavior also occurs in standard QAOA applied to combinatorial search. To this end we introduce QAOA phase diagrams that capture its performance and properties in various limits. In particular we show a region in which non-adiabatic schedules perform better than the adiabatic limit while employing lower quantum circuit depth. We further provide evidence our results and insights also apply to QAOA applications beyond chemistry.

arXiv:2108.13056•Aug 30, 2021•50 citations

Analytical framework for quantum alternating operator ansätze

Stuart Hadfield, Tad Hogg, Eleanor Gilbert Rieffel

Abstract We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansätze (QAOA). In the context of combinatorial optimization, our framework relates quantum cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function neighborhood structure. By considering QAOA circuits from the Heisenberg picture, we derive exact general expressions for expectation values as series expansions in the algorithm parameters, cost gradient operators, and cost difference functions. This enables novel interpretability and insight into QAOA behavior in various parameter regimes. For single-level QAOA1 we show the leading-order changes in the output probabilities and cost expectation value explicitly in terms of classical cost differences, for arbitrary cost functions. This demonstrates that, for sufficiently small positive parameters, probability flows from lower to higher cost states on average. By selecting signs of the parameters, we can control the direction of flow. We use these results to derive a classical random algorithm emulating QAOA1 in the small-parameter regime, i.e. that produces bitstring samples with the same probabilities as QAOA1 up to small error. For deeper QAOA p circuits we apply our framework to derive analogous and additional results in several settings. In particular we show QAOA always beats random guessing. We describe how our framework incorporates cost Hamiltonian locality for specific problem classes, including causal cone approaches, and applies to QAOA performance analysis with arbitrary parameters. We illuminate our results with a number of examples including applications to QUBO problems, MaxCut, and variants of MaxSAT. We illustrate the generalization of our framework to QAOA circuits using mixing unitaries beyond the transverse-field mixer through two examples of constrained optimization problems, Max Independent Set and Graph Coloring. We conclude by outlining some of the further applications we envision for the framework.

arXiv:2105.06996•Quantum Science and Technology•Nov 17, 2022•39 citations

Alignment between initial state and mixer improves QAOA performance for constrained optimization

Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti +4 more

Abstract Quantum alternating operator ansatz (QAOA) has a strong connection to the adiabatic algorithm, which it can approximate with sufficient depth. However, it is unclear to what extent the lessons from the adiabatic regime apply to QAOA as executed in practice with small to moderate depth. In this paper, we demonstrate that the intuition from the adiabatic algorithm applies to the task of choosing the QAOA initial state. Specifically, we observe that the best performance is obtained when the initial state of QAOA is set to be the ground state of the mixing Hamiltonian, as required by the adiabatic algorithm. We provide numerical evidence using the examples of constrained portfolio optimization problems with both low (p ≤ 3) and high (p = 100) QAOA depth. Additionally, we successfully apply QAOA with XY mixer to portfolio optimization on a trapped-ion quantum processor using 32 qubits and discuss our findings in near-term experiments.

arXiv:2305.03857•npj Quantum Information•Nov 27, 2023•72 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•167 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•4 citations

Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization

Mingyou Wu, Hanwu Chen

The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for demonstrating quantum advantage on near-term devices, yet the physical origins of its efficacy remain poorly understood. In this work, we study QAOA for random $k$-SAT problems within a universal-mixer $k$-local search framework, establishing a formal correspondence between adiabatic state transfer and the QAOA ansatz. This correspondence yields a rigorous performance guarantee for random instances with clause density $m=O(n^{1+ε})$ and circuit depth $Θ(n^2)$. We further investigate the NISQ regime with shallow circuits of depth $p=O(n)$. Surprisingly, the optimal parameters do not become stochastic under depth compression, but instead remain confined to a structured low-dimensional region, which we identify as a smooth adiabatic manifold. Numerical evidence indicates that this manifold persists across different circuit depths and arises from the variational suppression of adiabatic leakage. Based on this structure, we propose the smooth adiabatic-manifold parameterization (SAMP) strategy, transforming parameter optimization from an unstructured high-dimensional search into a guided refinement process. Numerical experiments on random 3-SAT instances show that SAMP achieves sublinear optimization scaling with circuit depth while providing robust zero-cost initialization for deep circuits.

quant-pharXiv:2605.20288•May 20, 2026•0 citations
The Quantum Approximate Optimization Algorithm and its generalization to Quantum Alternating Operator Ansatz (QAOA) is a promising approach for applying quantum computers to challenging problems such as combinatorial optimization and computational chemistry. In this paper, we study the underlying mechanisms governing the behavior of QAOA circuits beyond shallow depth in the practically relevant setting of gradually varying unitaries. We use the discrete adiabatic theorem, which complements and generalizes the insights obtained from the continuous-time adiabatic theorem primarily considered in prior work. Our analysis explains some general properties that are conspicuously depicted in the recently introduced QAOA performance diagrams. For parameter sequences derived from continuous schedules (e.g. linear ramps), these diagrams capture the algorithm's performance over different parameter sizes and circuit depths. Surprisingly, they have been observed to be qualitatively similar across different performance metrics and application domains. Our analysis explains this behavior as well as entails some unexpected results, such as connections between the eigenstates of the cost and mixer QAOA Hamiltonians changing based on parameter size and the possibility of reducing circuit depth without sacrificing performance.
Determining Hamiltonian ground states and energies is a challenging task with many possible approaches on quantum computers. While variational quantum eigensolvers are popular approaches for near term hardware, adiabatic state preparation is an alternative that does not require noisy optimization of parameters. Beyond adiabatic schedules, QAOA is an important method for optimization problems. In this work we modify QAOA to apply to finding ground states of molecules and empirically evaluate the modified algorithm on several molecules. This modification applies physical insights used in classical approximations to construct suitable QAOA operators and initial state. We find robust qualitative behavior for QAOA as a function of the number of steps and size of the parameters, and demonstrate this behavior also occurs in standard QAOA applied to combinatorial search. To this end we introduce QAOA phase diagrams that capture its performance and properties in various limits. In particular we show a region in which non-adiabatic schedules perform better than the adiabatic limit while employing lower quantum circuit depth. We further provide evidence our results and insights also apply to QAOA applications beyond chemistry.
Abstract We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansätze (QAOA). In the context of combinatorial optimization, our framework relates quantum cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function neighborhood structure. By considering QAOA circuits from the Heisenberg picture, we derive exact general expressions for expectation values as series expansions in the algorithm parameters, cost gradient operators, and cost difference functions. This enables novel interpretability and insight into QAOA behavior in various parameter regimes. For single-level QAOA1 we show the leading-order changes in the output probabilities and cost expectation value explicitly in terms of classical cost differences, for arbitrary cost functions. This demonstrates that, for sufficiently small positive parameters, probability flows from lower to higher cost states on average. By selecting signs of the parameters, we can control the direction of flow. We use these results to derive a classical random algorithm emulating QAOA1 in the small-parameter regime, i.e. that produces bitstring samples with the same probabilities as QAOA1 up to small error. For deeper QAOA p circuits we apply our framework to derive analogous and additional results in several settings. In particular we show QAOA always beats random guessing. We describe how our framework incorporates cost Hamiltonian locality for specific problem classes, including causal cone approaches, and applies to QAOA performance analysis with arbitrary parameters. We illuminate our results with a number of examples including applications to QUBO problems, MaxCut, and variants of MaxSAT. We illustrate the generalization of our framework to QAOA circuits using mixing unitaries beyond the transverse-field mixer through two examples of constrained optimization problems, Max Independent Set and Graph Coloring. We conclude by outlining some of the further applications we envision for the framework.
Abstract Quantum alternating operator ansatz (QAOA) has a strong connection to the adiabatic algorithm, which it can approximate with sufficient depth. However, it is unclear to what extent the lessons from the adiabatic regime apply to QAOA as executed in practice with small to moderate depth. In this paper, we demonstrate that the intuition from the adiabatic algorithm applies to the task of choosing the QAOA initial state. Specifically, we observe that the best performance is obtained when the initial state of QAOA is set to be the ground state of the mixing Hamiltonian, as required by the adiabatic algorithm. We provide numerical evidence using the examples of constrained portfolio optimization problems with both low (p ≤ 3) and high (p = 100) QAOA depth. Additionally, we successfully apply QAOA with XY mixer to portfolio optimization on a trapped-ion quantum processor using 32 qubits and discuss our findings in near-term experiments.
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.
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 a leading candidate for demonstrating quantum advantage on near-term devices, yet the physical origins of its efficacy remain poorly understood. In this work, we study QAOA for random kkk-SAT problems within a universal-mixer kkk-local search framework, establishing a formal correspondence between adiabatic state transfer and the QAOA ansatz. This correspondence yields a rigorous performance guarantee for random instances with clause density m=O(n1+ε)m=O(n^{1+ε})m=O(n1+ε) and circuit depth Θ(n2)Θ(n^2)Θ(n2). We further investigate the NISQ regime with shallow circuits of depth p=O(n)p=O(n)p=O(n). Surprisingly, the optimal parameters do not become stochastic under depth compression, but instead remain confined to a structured low-dimensional region, which we identify as a smooth adiabatic manifold. Numerical evidence indicates that this manifold persists across different circuit depths and arises from the variational suppression of adiabatic leakage. Based on this structure, we propose the smooth adiabatic-manifold parameterization (SAMP) strategy, transforming parameter optimization from an unstructured high-dimensional search into a guided refinement process. Numerical experiments on random 3-SAT instances show that SAMP achieves sublinear optimization scaling with circuit depth while providing robust zero-cost initialization for deep circuits.