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

A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm

Raimel A. Medina, Maksym Serbyn

Published May 16, 2024• 0 citations
arXivHTMLPDF

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) uses a quantum computer to implement a variational method with $2p$ layers of alternating unitary operators, optimized by a classical computer to minimize a cost function. While rigorous performance guarantees exist for the QAOA at small depths $p$, the behavior at large depths remains less clear, though simulations suggest exponentially fast convergence for certain problems. In this work, we gain insights into the deep QAOA using an analytic expansion of the cost function around transition states. Transition states are constructed recursively: from a local minima of the QAOA with $p$ layers we obtain transition states of the QAOA with $p+1$ layers, which are stationary points characterized by a unique direction of negative curvature. We construct an analytic estimate of the negative curvature and the corresponding direction in parameter space at each transition state. Expansion of the QAOA cost function along the negative direction to the quartic order gives a lower bound of the QAOA cost function improvement. We provide physical intuition behind the analytic expressions for the local curvature and quartic expansion coefficient. Our numerical study confirms the accuracy of our approximations, and reveals that the obtained bound and the true value of the QAOA cost function gain have a characteristic exponential decrease with the number of layers $p$, with the bound decreasing more rapidly. Our study establishes an analytical method for recursively studying the QAOA applicable in the regime of high circuit depth.

DOI
10.48550/arxiv.2405.10125

Related papers

Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement

Stefan H. Sack, Raimel A. Medina, Richard Kueng +1 more

The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of $p$ layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search for initialization strategies of QAOA variational parameters. Although numerous heuristic initializations exist, an analytical understanding and performance guarantees for large $p$ remain evasive. We introduce a greedy initialization of QAOA which guarantees improving performance with an increasing number of layers. Our main result is an analytic construction of $2p+1$ transition states---saddle points with a unique negative curvature direction---for QAOA with $p+1$ layers that use the local minimum of QAOA with $p$ layers. Transition states connect to new local minima, which are guaranteed to lower the energy compared to the minimum found for $p$ layers. We use the Greedy procedure to navigate the exponentially increasing with $p$ number of local minima resulting from the recursive application of our analytic construction. The performance of the Greedy procedure matches available initialization strategies while providing a guarantee for the minimal energy to decrease with an increasing number of layers $p$.

arXiv:2209.01159•Physical Review A•Jun 2, 2023•20 citations

Energy landscapes for the quantum approximate optimization algorithm

Choy Boy, David J. Wales

Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024

Physical Review A•Jun 3, 2024•7 citations

Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm

Anuj Apte, Shree Hari Sureshbabu, Ruslan Shaydulin +5 more

Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum heuristic with empirical evidence of speedup over classical state-of-the-art for some problems. QAOA uses a parameterized circuit with $p$ layers, where higher $p$ yields better solutions, but requires optimizing $2p$ independent parameters, which is challenging at large $p$. We present an iterative interpolation method that exploits the smoothness of optimal parameter schedules by expressing them in a basis of orthogonal functions, generalizing the work of Zhou et al. By optimizing a small number of basis coefficients and iteratively increasing both circuit depth and coefficient count until convergence, our method constructs high-quality schedules for large $p$. We provide theoretical justification using Jackson's theorem and Lipschitz continuity to bound the required number of basis coefficients for a given accuracy. Our approach achieves better performance with fewer optimization steps than existing methods across three benchmark problems: the Sherrington-Kirkpatrick (SK) model, portfolio optimization, and Low Autocorrelation Binary Sequences (LABS). For the largest LABS instance, we achieve near-optimal merit factors with schedules exceeding 1000 layers, an order of magnitude beyond previous methods. Additionally, we observe that a mild growth in QAOA depth suffices to solve the SK model exactly, a result of independent theoretical interest.

quant-pharXiv:2504.01694•ACM Transactions on Quantum Computing•Apr 3, 2025•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

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

The Quantum Approximate Optimization Algorithm: Performance on Max-Cut using Heuristic Parameter determination

Jacques C. P. Bus

The Quantum Approximate Optimization Algorithm (QAOA) is one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.

•Jan 1, 2020•0 citations
The Quantum Approximate Optimization Algorithm (QAOA) uses a quantum computer to implement a variational method with 2p2p2p layers of alternating unitary operators, optimized by a classical computer to minimize a cost function. While rigorous performance guarantees exist for the QAOA at small depths ppp, the behavior at large depths remains less clear, though simulations suggest exponentially fast convergence for certain problems. In this work, we gain insights into the deep QAOA using an analytic expansion of the cost function around transition states. Transition states are constructed recursively: from a local minima of the QAOA with ppp layers we obtain transition states of the QAOA with p+1p+1p+1 layers, which are stationary points characterized by a unique direction of negative curvature. We construct an analytic estimate of the negative curvature and the corresponding direction in parameter space at each transition state. Expansion of the QAOA cost function along the negative direction to the quartic order gives a lower bound of the QAOA cost function improvement. We provide physical intuition behind the analytic expressions for the local curvature and quartic expansion coefficient. Our numerical study confirms the accuracy of our approximations, and reveals that the obtained bound and the true value of the QAOA cost function gain have a characteristic exponential decrease with the number of layers ppp, with the bound decreasing more rapidly. Our study establishes an analytical method for recursively studying the QAOA applicable in the regime of high circuit depth.
The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of ppp layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search for initialization strategies of QAOA variational parameters. Although numerous heuristic initializations exist, an analytical understanding and performance guarantees for large ppp remain evasive. We introduce a greedy initialization of QAOA which guarantees improving performance with an increasing number of layers. Our main result is an analytic construction of 2p+12p+12p+1 transition states---saddle points with a unique negative curvature direction---for QAOA with p+1p+1p+1 layers that use the local minimum of QAOA with ppp layers. Transition states connect to new local minima, which are guaranteed to lower the energy compared to the minimum found for ppp layers. We use the Greedy procedure to navigate the exponentially increasing with ppp number of local minima resulting from the recursive application of our analytic construction. The performance of the Greedy procedure matches available initialization strategies while providing a guarantee for the minimal energy to decrease with an increasing number of layers ppp.
Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024
Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum heuristic with empirical evidence of speedup over classical state-of-the-art for some problems. QAOA uses a parameterized circuit with ppp layers, where higher ppp yields better solutions, but requires optimizing 2p2p2p independent parameters, which is challenging at large ppp. We present an iterative interpolation method that exploits the smoothness of optimal parameter schedules by expressing them in a basis of orthogonal functions, generalizing the work of Zhou et al. By optimizing a small number of basis coefficients and iteratively increasing both circuit depth and coefficient count until convergence, our method constructs high-quality schedules for large ppp. We provide theoretical justification using Jackson's theorem and Lipschitz continuity to bound the required number of basis coefficients for a given accuracy. Our approach achieves better performance with fewer optimization steps than existing methods across three benchmark problems: the Sherrington-Kirkpatrick (SK) model, portfolio optimization, and Low Autocorrelation Binary Sequences (LABS). For the largest LABS instance, we achieve near-optimal merit factors with schedules exceeding 1000 layers, an order of magnitude beyond previous methods. Additionally, we observe that a mild growth in QAOA depth suffices to solve the SK model exactly, a result of independent theoretical interest.
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.
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 one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.