Why QAOA with $p \rightarrow \infty $ gives the optimal solution?

Question

In the QAOA paper, it is shown that the optimal value of the p-ansatz $M_p$ converges to $\max_z C(z)$ as $p \rightarrow \infty$ on page 10. The proof is to relate to QAOA by considering the time-dependent Hamiltonian $H(t) = (1 − t/T)B + (t/T)C$, which I don't follow.

First, I guess the QAOA paper is to use the Trotterization to approximate $e^{-i H(t)}$ using $e^{-i \beta B}e^{-i \gamma C}\cdots e^{-i \beta B}e^{-i \gamma C}$. But this approximation is only for a ${\bf fixed}$ $t$, right? So how can this Trotterized approximation be close to $e^{-i C}$?

Second, $C$ has many eigenstates, and why should the state $z$ with the largest value of $C(z)$ be returned?

Answer 1

The Quantum Approximate Optimization Algorithm is closely related to the Quantum Adiabatic Algorithm. Let's say we have a simple Hamiltonian (in our case $H_B$) with a known ground state and another Hamiltonian $H_C$, whose ground state we want to calculate. Consider the time-dependent Hamiltonian \begin{equation} H(t) = \left(1-\frac{t}{T}\right)H_B(t) + \frac{t}{T} H_C \end{equation} For $t=0$ the system is described by $H_B$ while for $t=T$ it is described by $H_C$.

The adiabatic theorem states that if we start in the ground state of $H_B$ and slowly start to increase $t$ up to time $T$, then throughout the process the system will always remain in the ground state of $H(t)$, which means that at the end of the evolution the system will be in the ground state of $H_C$.

The Trotterization is defined as : \begin{equation} e^{A+B} = lim_{n \rightarrow \infty} \left(e^{\frac{A}{n}}e^{\frac{B}{n}}\right)^n \end{equation}

Now consider the time evolution of the Hamiltonian $H(t)$, $U(t) = e^{iH(t)t}$. It is straightforward to see the why in the limit of $p\rightarrow \infty$ you get an approximation ratio of $1$.

Quantum Approximate Optimization Algorithm can be seen as truncated version of QAA. That is, we choose up to what layers we wish to make the Trotterization, but that comes with a cost. It is instance dependent what approximation ratio you will get for fixed layers and it is always smaller that $1$. Our goal is to make it as large as possible!

As for the second part of the question, it is NOT always the eigenstate of $C(z)$ with the largest value returned and that is the reason why you are aiming for a big approximation value. If it close to 1, the expectation value is concentrated near the optimal value and you will get most of the times the desired bitstring.