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?


1 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.

  • 1
    $\begingroup$ 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)$? $\endgroup$
    – John Wong
    Commented Jan 4, 2021 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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