Chapter 5
QAOA: Quantum Approximate Optimization Algorithm
True optimization is the revolutionary contribution of modern research to decision processes.
— George Dantzig
The techniques that we have introduced in the two previous chapters already allow us to solve combinatorial optimization problems on quantum computers. Specifically, we have studied how to write problems using the QUBO formalism and how to use quantum annealers to sample approximate solutions. This is an important approach to quantum optimization, but it is not the only one.
In this chapter, we are going to show how the ideas that we have already explored can also be used on digital quantum computers. We will be using our beloved quantum circuits — with all their qubits, quantum gates, and measurements — to solve combinatorial optimization problems formulated in the QUBO framework.
More concretely, we will be studying the famous Quantum Approximate Optimization Algorithm (QAOA), which is a gate...
