The living QAOA reference

What is QAOA?

QAOA is short for “Quantum Approximate Optimization Algorithm”.

• Protocol for approximately solving an optimization problem on a quantum computer
• Can be implemented on near-term devices!
• Variable parameter \(p\) (depth) – the optimal performance increases with \(p\) and solves\(^*\) the problem as \(p \to \infty\) (\(^*\)QAOA recovers adiabatic evolution, will only solve it if the adiabatic algorithm will solve it)
• In order to use this algorithm optimally, you have to tune \(2p\) parameters (this gets hard as \(p\) grows!)
• This is a ‘local’ algorithm, which may limit its power.

For deeper mathematical descriptions, see the paper or tutorials (here, here, here, here). Some important jargon: mixing terms, cost functions, circuit depth, and Trotterization.

See a list of papers tagged ‘QAOA’ on the arXiv.wiki.

Performance analysis at low depth

The QAOA at low depth is easiest to analyze. Here is a table of known results:

There are some other results on low-depth QAOA (perhaps could be added to the table above):

• Marika Svensson’s papers
• The performance of QAOA at \(p=1\) for a “QUBO” (quadratic cost function) is known
• Stuart Hadfield’s thesis (for example, on MaxDiCut)
• NASA QuAIL’s paper on Grover search with QAOA
• Claes+ 2021 on mixed-spin glass models
• the ‘toy’ Hamming-weight ramp and variations (there is a bound showing only states near weight \(n/2\) matter for \(p=1\)); and maximally constrained 3-SAT with a single satisfying assignment. These allow perfect solution with \(p=1\).
• Worst-case bounds on MAX-CUT of d-regular bipartite graphs are known via Bravyi+ 2019 and Farhi+ 2020b. The former proves the bound by showing a weaker version of a symmetry-protected No-Low Energy Trivial States (NLTS) conjecture, and the latter improves upon the obstruction via an indistinguishability argument about the local-neighborhood of random $d$-regular graphs.

The graph structure may impact QAOA performance; see Herrman+ 2021 for a study on small graphs.

QAOA & the Overlap Gap Property

A sequence of recent results has conclusively established the so-called “Overlap Gap Property” (OGP), which is a statement about the solution geometry of near-optimal solutions of a problem, as a conclusive obstacle to the QAOA up to a depth where it is local (does not see the entire input w.h.p.). For example, see Farhi+ 2020a and CLSS21. These obstructions are Average-Case and typically apply to almost all instances of a problem drawn from a “natural” distribution.

In particular, CLSS21 shows that QAOA up to depth \(c\cdot \log(n)\) is obstructed on almost all instances of any Constraint Satisfaction Problem (CSP) that satisfies a property called the “Coupled Overlap Gap Property” (C-OGP). This immediately implies that QAOA up to the depth above is obstructed on random instances of MAX-k-XOR for \(k \geq 4\) and even (as a C-OGP is demonstrated to exist for the problem by CLSS21, extending a result of CGPR19). Furthermore, as consequence of one of the concentration lemmas in CLSS21, the “Landscape Independence” conjecture of BBFGN18 is also resolved positively - This asserts that up to \(c\cdot \log(n)\) depth, the QAOA algorithm (with any fixed angles) performs almost equally well on almost all instances.

Choosing optimal parameters

At high depth, the algorithm’s success is dependent on choosing good parameters. There are different strategies to set good parameters, depending on your goal. (Note: Optimally tuning your parameters is a NP-hard problem!) Here is a table of different parameter-setting strategies:

Barren plateaus pose a challenge to numerically calculating optimal parameters. Parameter landscapes have many local optima and a lot of “flat” regions (“barren plateaus”). This means that local changes in parameters (e.g. gradient methods) may not improve the QAOA, making it very difficult to identify optimal parameters. See McClean+ 2018 and Wang+ 2020.

Some studies suggest that optimal QAOA parameters can transfer from graph instance to graph instance: see Lotshaw+ 2021 for study at small graphs, Galda+ 2021, and Wurtz+ 2021. This is also true on large graphs; see a theoretical result of instance independence in Brandao+ 2018.

For certain problems with instance independence you can get analytical expressions for the optimal QAOA parameters. This happens for local problems like MAX-CUT on degree-3 graphs and for the SK model. On these problems, one can classically find the universal angles that apply to any (large) problem instance.

QAOA might (and from simulations, appears to) perform well with good parameters, not necessarily optimal. This suggests (but doesn’t prove!) that aiming to find optimal parameters for large \(p\) is not only difficult, but also unnecessary.

There are different strategies to optimize parameters treating the QAOA optimization as a control problem; see Niu+ 2019, Dong+ 2019, Wiersema+ 2020.

QAOA performance under noise and errors

The quality of solutions found by QAOA (without error correction or mitigation) quickly decays under noise. Noise also makes it harder to find optimal parameters.

• Franca+ 2020 shows that assuming each gate in the circuit fails with probability q, at a depth scaling like \(1/q\) the expected energy of the output string is provably worse than that obtained by efficient classical algorithms. Interestingly, their results show that this can even happen at depths of the order \(1/(10q)\), i.e. when only a small fraction of the qubits has been corrupted. This indicates that very small noise rates might be necessary to obtain an advantage if implementing the QAOA unitaries in the physical device requires a large depth.
• Under similar assumptions, Wang+ 2020 shows that the gradient of the parameters of the QAOA circuit is exponentially small at depths of order \(n/q\), where \(n\) is the number of qubits. This shows that the circuits are essentially untrainable at large depths.
• Quiroz+ 2021 shows that the performance of QAOA decays exponentially with errors in the parameters. See also Marshall+ 2020, Xue+ 2019.

The rapid decay of the quality of QAOA due to noise has also been observed experimentally in Harrigan+ 2021.

There are also strategies to deal with errors:

• Shaydulin+ 2021 shows how the symmetries in QAOA ansatz can be used to mitigate errors. Applies this approach on quantum hardware fo MaxCut.
• Botelho+ 2021 exteneds symmetry approach to Quantum Alternating Operator Ansatz

Extensions to QAOA

Several adjustments to QAOA have been proposed. Some of these are new protocols that use QAOA as a subroutine; others add penalty terms, use thermal state based objectives, or adjust the mixing Hamiltonian. Here is a list:

Some extensions use alternative cost functions besides the cost Hamiltonian, including CVaR (Conditional Value-at-Risk) (Barkoutsos+ 2019), feedback-based approaches (Magann+ 2021), and Gibbs sampling. These aim to estimate higher moments of the distribution to improve the “best” (vs expected) performance of QAOA.

Open problems

• Which problems and families of instances can we show that QAOA provides advantage over classical algorithms?
  • Sreedhar+ 2022 have numerically observed that low entangled tensor network based classical approximations of QAOA work equally well as standard QAOA when applied to randomly generated MaxCut on Erdos-Renyi graph instances and Exact Cover 3 instances. This suggests reduced likelihood for a quantum advantage for these families of instances.
• How can we analyze QAOA at higher depth? (for example, some ideas in Hadfield+ 2021)
  • What happens at log depth?
  • What happens at poly depth?
• How does the QAOA performance scale with \(p\)?
• How can we better choose the QAOA parameters?
• How do we best implement constrained optimization?
  • When are penalty terms useful?
• What are the optimal choices of mixers? (comparing \(p\), or circuit size)
• How can we best mitigate error from noise?

Figure from Barak+ 2021:

Myths about QAOA

Have more to add? Edit this page (button on the left) or email Kunal Marwaha at marwahaha@berkeley.edu.