# Quantum Approximation Optimization Algorithm

By [Shivam](https://paragraph.com/@zakutaish) · 2022-08-10

---

### What is QAOA?

QAOA is short for “Quantum Approximate Optimization Algorithm”.

*   It is a Variational Quantum Algorithm (VQA) which approximately solves an optimization problem on a quantum computer.
    
*   One of the reasons a lot of researchers are interested in studying it is because it can be implemented on a near-term quantum device.
    
*   Depth (level) p — the optimal performance increases with increase in depth p and analysis in literature has shown that as p \\rightarrow \\infty, QAOA attains optimal solution.
    
*   As it is a VQA, in order to use QAOA optimally, one has to optimize 2p parameters (at a particular depth p, there are 2p parameters) which is done classically. This becomes difficult with increase in depth p.
    

For more rigorous understanding of the algorithm, the reader can refer to the original paper ([here](https://arxiv.org/abs/1411.4028)) and to get more hands-on intuition ([here](https://www.mustythoughts.com/quantum-approximate-optimization-algorithm-explained), [here](https://github.com/rsln-s/QAOA_tutorial) and [here](https://qiskit.org/textbook/ch-applications/qaoa.html)).

### Busting Myths about QAOA

*   MAX-CUT is clearly an interesting problem for quantum advantage
    
    *   Goemans-Williamson (SDP) is potentially optimal (if Unique Games Conjecture is true). There may be families of graphs where quantum computing can help; but other problems have much bigger gaps between best classical algorithm and limits of approximation.
        
*   VQE is the same as QAOA
    
    *   VQE is a routine for finding the minimum eigenvalue of a “quantum” Hamiltonian (e.g. electronic structure problem). The variational method is required because we can’t evaluate the Hamiltonian classically. In QAOA, by contrast, the Hamiltonian can be represented classically, but the best solution is not known. Stuart Hadfield refers to this distinction as non-diagonal eigenvalue problem vs diagonal eigenvalue problem. See more information about [variational quantum algorithms here](https://www.mustythoughts.com/vqas-how-do-they-work). However, one can use QAOA-like algorithms on quantum Hamiltonians; see [Anshu+ 2020](https://arxiv.org/abs/2003.14394), [Anshu+ 2021](https://arxiv.org/abs/2105.01193).
        
*   QAOA is just adiabatic computation
    
    *   Although there are many similarities, there are settings where QAOA improves upon adiabatic computation. See [Zhou+ 2018](https://arxiv.org/abs/1812.01041) and also [Brady+ 2021](https://arxiv.org/abs/2107.01218). Other comparisons bound the depth _p_ for QAOA to approximate adiabatic computation, and compare the control strategies ([Bapat+ 2018](https://arxiv.org/abs/1812.02746)).
        
*   Using QAOA gives quantum advantage
    
    *   Although sampling from a p=1 QAOA distribution is not possible classically ([Farhi+ 2016](https://arxiv.org/abs/1602.07674)), simply _using_ QAOA does not necessarily mean you are calculating things classical computers cannot. In fact, there are no strong examples (yet?) of provable quantum advantage using QAOA on an optimization problem.
        

### 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. Here is a list of different parameter-setting strategies (non-exhaustive):

*   brute force
    
    *   Pre-compute the optimal parameters. Then use optimal parameters to run the algorithm. Although the parameters are found, this takes time exponential with the graph size.
        
*   variational
    
    *   Run the algorithm several times on a quantum computer, then use the results to choose new parameters. Repeat until you achieve convergence. This requires using a quantum computer many times to find the right parameters. Noise in quantum computers may make it more challenging to choose improved parameters at each step.
        
*   interpolative or Fourier methods
    
    *   Solve optimal beta and gamma at small p, and use that to guess optimal betas and gammas at larger p. This does not guarantee that the optimal parameters are the best possible for QAOA.
        
*   ML/RL
    
    *   Use a classical optimization method to compute nearly-optimal parameters. The computed parameters may not be optimal, because of barren plateaus.
        
*   Explicit formulas at Infinite Size limit
    
    *   Use the analysis of QAOA on random models at infinite size limit to predict near-optimal parameters. Estimate energy of SK-model at infinite size by devising a Monte-Carlo algorithm. Cannot be generalized for q-spin models q≥3 for depth p>1. Their hypothesis is limited to small instances
        
*   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](https://arxiv.org/abs/1803.11173) and [Wang+ 2020](https://arxiv.org/abs/2007.14384).
    
*   Some studies suggest that optimal QAOA parameters can transfer from graph instance to graph instance: see [Lotshaw+ 2021](https://arxiv.org/abs/2102.06813) for study at small graphs, [Galda+ 2021](https://arxiv.org/abs/2106.07531), and [Wurtz+ 2021](https://arxiv.org/abs/2107.00677). This is also true on large graphs; see a theoretical result of instance independence in [Brandao+ 2018](https://arxiv.org/abs/1812.04170).
    
*   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.
    
*   There are different strategies to optimize parameters treating the QAOA optimization as a control problem; see [Niu+ 2019](https://arxiv.org/abs/1905.12134), [Dong+ 2019](https://arxiv.org/abs/1911.00789), [Wiersema+ 2020](https://arxiv.org/abs/2008.02941).
    

### QAOA Variants

*   ST-QAOA (Spanning Tree QAOA)
    
    *   Changes the mixer to a sum of X\_i X\_j terms on a spanning tree
        
*   CD-QAOA (Counter-diabatic QAOA)
    
    *   Adds terms to the mixer to mimic corrections to adiabaticity
        
*   Quantum Alternating Operator Ansatz
    
    *   Generalization of QAOA (parameterized unitaries and mixers; incorporating constraints into the mixers)
        
*   RQAOA (Recursive QAOA)
    
    *   Recursively generates a more and more constrained problem. Uses QAOA (or some other quantum routine) to add constraints.
        
*   GM-QAOA (Grover Mixer QAOA) and Th-QAOA (Threshold-based QAOA)
    
    *   Change the mixers to “flip phase” for a marked element (GM) or above a certain threshold (Th); imitates Grover search operators
        
*   Warm-start QAOA
    
    *   Approximately solve the problem with a different method; then use that output as the initial state to QAOA
        
*   Multi-angle QAOA
    
    *   Separate the cost Hamiltonian into individual terms, and use a different angle per term at every step
        

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

QAOA in Practice: [Shaydulin+ 2021](https://arxiv.org/abs/2110.05555) (QAOA-Kit) and [Q-Tensor](https://github.com/danlkv/qtensor) (based on tensor networks; supports parallel QAOA simulations).

---

*Originally published on [Shivam](https://paragraph.com/@zakutaish/quantum-approximation-optimization-algorithm)*