The living QAOA reference

updated 2021-08-01

What is QAOA?

“Quantum Approximate Optimization Algorithm”

Performance analysis at low depth

Problem QAOA depth Graph optimal performance (satisfying fraction) best known algorithm? Papers
MAX-CUT 1 triangle-free \(1/2 + 0.30/\sqrt{D}\) No Wang+ 2018, Hastings 2019
MAX-CUT 1 any see formula ? (KM project in progress) Wang+ 2018, Hastings 2019
MAX-CUT 2 girth above 5 \(1/2 + 0.41/\sqrt{D}\) No Marwaha 2021
MAX-3-XOR (E3LIN2) 1 no overlapping constraints, or random signs at least \(1/2 + O(1/\sqrt{D})\) ? (KM project in progress) Farhi+ 2015, Barak+ 2015, Lin+ 2016
MAX-3-XOR (E3LIN2) 1 any at least \(1/2 + O(1/\sqrt{D log D})\) so far, No Farhi+ 2015, Barak+ 2015
SK Model 1-12 infinite size see formula ? Farhi+ 2019
Max Independent Set 1 any at least \(O(n/d)\) so far, No (KM project in progress) Farhi+ 2020

Choosing optimal parameters

At high depth, the algorithm’s success is dependent on choosing the best parameters. Strategies to make this easier include:

There are some studies of optimal QAOA parameters for some graphs being transferable to other graphs (instance independence); see Galda+ 2021, Brandao+ 2018, or Wurtz+ 2021.

It would be nice to discuss some results on barren plateaus here, and also mention what happens to error.

Extensions to QAOA

Several adjustments to QAOA have been proposed:

Some of these extensions are “true extensions” (sampling things from quantum computers), such as penalty proposals and adjusting the mixers; while others are new protocols that use QAOA inside of it (CD-QAOA, RQAOA).

Some of these protocols turn QAOA into a non-local algorithm.

Open problems

MAX-CUT is an interesting problem for quantum advantage

This is the case because…

VQE is the same as QAOA

It’s worth making clear similarities and differences between VQE (e.g. electronic structure) and QAOA (diagonal eigenvalue problems vs non-diagonal eigenvalue problems)

In VQE – the ansatz holds something I can’t hold classically, so intermediate strings don’t tell me what the state is.

The expected performance is what matters

You really want the highest value the QAOA returns; when you run the experiment many times, you take the best one, not the average one. But we use the average because it’s easier to calculate, and chebyshev & chernoff to get bound on tail.

The QAOA may also perform well even if the overlap with optimal value is low.

There are alternate metrics of performance, such as ___.

QAOA is just adiabatic computation

Although there are many similarities, there are settings where QAOA improves upon adiabatic computation. See Zhou+ 2018