QAOA: the quantum approximate optimization algorithm

Short answer: The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm that aims to solve combinatorial optimization problems that are classically intractable, and a 2024 Physics Reports review calls it highly promising. It encodes a problem's cost function into a quantum circuit and uses layers of time evolution to find a good approximate solution. The review's own material says the literature still has conflicting opinions on whether it can outperform classical algorithms on current devices.

What is the core mechanism of QAOA?

A review of QAOA in Physics Reports, also on arXiv, calls it a highly promising variational quantum algorithm that aims to solve combinatorial optimization problems that are classically intractable. Slides from a presentation of the review describe the key idea: encode the cost function of the optimization problem in the cost Hamiltonian, then encode it into a variational quantum circuit and leverage time evolution and layering to find a good approximated solution.

The slides say QAOA was first introduced by Farhi et al. in 2014 as a variational algorithm able to find approximate solutions to the MaxCut problem, which they link to QUBO instances, and say it is suitable to be run on NISQ devices. They say that, inspired by Trotterized adiabatic quantum computation, QAOA was designed as a variational algorithm with repeated cost and mixing layers.

How does QAOA relate to adiabatic evolution?

The slides state that as the number of layers p goes to infinity, QAOA can at least exactly approximate adiabatic quantum evolution and can therefore find the exact optimal solution. That is a statement about a theoretical limit, and this article does not say anything about how many layers any real device can run.

The review covers performance analysis in diverse scenarios, applicability across various problem instances, and hardware-specific challenges such as error susceptibility and noise resilience. It also includes a comparative study of selected QAOA extensions and variants, and discusses future prospects and directions.

What are the current performance and hardware challenges?

The presentation slides list two motivations: the lack of commonly acknowledged guidelines on QAOA may limit its impact in the quantum technology ecosystem, and the literature still contains many conflicting opinions on whether QAOA can actually outperform classical algorithms with current quantum devices. This article does not claim a speedup.

The authors say they aim to provide insights into whether QAOA can outperform classical algorithms and under what circumstances it should be used, and they offer specific practical points in the form of a short guide. The slides frame it as a guide for suggested uses, with two questions: whether QAOA can outperform classical algorithms, and when and how it should be used. This article summarises the review's abstract and slides and does not reproduce that guide.

How should practitioners approach using QAOA?

FAQ

What does QAOA aim to do?

According to a review in Physics Reports, it aims to solve combinatorial optimization problems that are classically intractable, by finding approximate solutions.

Who introduced it?

Slides presenting the review say it was first introduced by Farhi et al. in 2014, to find approximate solutions to the MaxCut problem.

Does QAOA find the exact optimum?

The slides say that in the limit of an infinite number of layers it can at least exactly approximate adiabatic quantum evolution and therefore find the exact optimal solution. That is a theoretical limit.

Can QAOA beat classical algorithms?

The review's material says the literature still contains many conflicting opinions on whether QAOA can outperform classical algorithms with current quantum devices.

What hardware challenges does the review discuss?

Error susceptibility and noise resilience.