Chapter 11
Quantum Approximate Optimisation Algorithm
As the name suggests, the Quantum Approximate Optimisation Algorithm (QAOA) is an optimisation algorithm. It is motivated by and draws upon two optimisation algorithms considered in previous chapters: AQC and VQE. From AQC it borrows the concept of solving an optimisation problem through encoding the corresponding objective function in the problem Hamiltonian and then evolving the system in such a way that the ground state of the final Hamiltonian provides the solution we are after (in a bitstring format). From VQE it borrows the variational principle applied to the parameterised quantum circuit. Roughly speaking, QAOA is a gate-model version of an optimisation solver that otherwise could have been tackled with an analog AQC approach. We can also look at QAOA as a special case of VQE with the constraints on the form of the Hamiltonian.
QAOA was introduced in the pioneering work by Farhi, Goldstone, and Gutmann [96] in 2014...
