In the QAOA algorithm for MaxCut, the authors construct a very specific scheme where the qubits (corresponding to the vertices of the graph) are transformed using a sequence of unitaries

$$|\gamma, \boldsymbol{\beta}\rangle= U\left(B, \beta_{p}\right) U\left(C, \gamma_{p}\right) \cdots U\left(B, \beta_{1}\right) U\left(C, \gamma_{1}\right)|s\rangle$$

Here $\vert s\rangle$ is an intial state constructed by a Hadamard on the all zero state. The $U(B, \beta_i)$ and $U(C,\gamma_i)$ are also specific unitaries that the authors construct. The alternating sequence of $U(B, \beta_i)$ and $U(C,\gamma_i)$ is also specified.

QAOA works by iteratively measuring the output state $|\gamma, \boldsymbol{\beta}\rangle$. It uses a classical optimizer to choose the next set of angles $\{\beta_i\}$ and $\{\gamma_i\}$. This is repeated until the classical optimizer converges and the final measurement on the state $|\gamma, \boldsymbol{\beta}\rangle$ gives us the information of how to cut the graph.

Is there a reference that explains why this specific construction was chosen? The original paper introduces this construction and says that this yields a good cut but what motivated this very specific construction? Any references or links to talks would be greatly appreciated!


What motivated this construction is mentioned in the original paper (section VI): adiabatic quantum computing. This construction is basically a Trotterized version of the evolution by the time dependent hamiltonian: $$ H(t) = (1-t/T)B + (t/T) C $$ where T is the total runtime.

The Trotterized evolution consists of alternately applying $U_{C}$ and $U_{B}$. Here, the sum of the angles is the total runtime T.

And note that the initial state is the highest energy eigenstate of B and by evolution, we try to find the highest energy eigenstate of C. The adiabatic theorem tells you that if you evolve slowly and long enough, you end up in the seeked eigenstate. In QAOA, slowly means small angles and long enough means a good enough depth $p$. And to the limit of infinite depth, you get convergence.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.