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

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?

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 $$$$H(t) = \left(1-\frac{t}{T}\right)H_B(t) + \frac{t}{T} H_C$$$$ 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 : $$$$e^{A+B} = lim_{n \rightarrow \infty} \left(e^{\frac{A}{n}}e^{\frac{B}{n}}\right)^n$$$$

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.

• Thanks! I guess the time evolution under $H(t)$ is $U(t) = \exp\left(-i/h \int_0^t H(s) ds \right)$. How can we show that $U(t)$ can be approximated by alternating $\exp(H_B)$ and $\exp(H_C)$? Jan 4 '21 at 3:26