12.8 Quantum approximate optimization algorithm (QAOA)

The quantum approximate optimization algorithm, abbreviated as QAOA, is an example of a variational quantum algorithm. We can use it for combinatorial optimization problems such as the Max-Cut Problem we discussed in section 12.2.2, and we use this problem to illustrate the technique. 18 38 algorithm$QAOA algorithm$quantum approximate optimization quantum$approximate optimization algorithm algorithm$variational QAOA variational$algorithm Max-Cut Problem algorithm$QAOA maximum cut

We begin by constructing the Hamiltonians, unitaries, and circuits we need to perform the optimization.

12.8.1 Encoding the problem

Recall from section 12.2.2 on the Max-Cut Problem that we use the integer vector z with z_k = ±1. z_k = 1 if k is in U, and z_k = –1 if k is in U′. We seek to maximize

We now map this general form with n vertices to Hermitian Pauli strings and a...