Derivation of QAOA from AQC

Question

In adiabatic quantum optimization we start with an initial Hamiltonian $H_0$ and then adiabatically evolve from $H_0$ to $H_P$ (problem hamiltonian) for a time $T$ according to \begin{equation}\label{eq:adiabatic hamiltonian} H(t) = A(t) \cdot H_0 + B(t) \cdot H_P, \end{equation} where $A(t)$ evolves from $1$ to $0$ during $T$ and $B(t)$ vice versa. In general, $H_0$ and $H_P$ do not commute.

From here we come to QAOA by this:

The unitary evolution of the Hamiltonian H(t) is approximated by the Trotter-Suzuki decomposition formula \begin{equation} U(0, T) = \mathcal{T} e^{\int_0^T A(t) \cdot H_0 + B(t) \cdot H_Pdt} \approx e^{-iH((2N-1)\delta/2)\delta}\ldots e^{-iH(3\delta/2)\delta}e^{-iH(\delta)\delta} = \\ e^{A_NH_0 + B_NH_P}\ldots e^{A_2H_0 + B_2H_P}e^{A_1H_0 + B_1H_P} \end{equation} with $A_N = -i\delta A(\frac{2N-1}{2}\delta)$, $B_N= -i\delta B(\frac{2N-1}{2}\delta)$ and $N\delta=T$. $ \mathcal{T}$ is the time-ordering operator. The unitary in the QAOA looks like this: \begin{equation} e^{\alpha_NH_0}e^{\beta_NH_P}\ldots e^{\alpha_2H_0}e^{\beta_2H_P}e^{\alpha_1H_0}e^{\beta_1H_P} \end{equation}

So, how do I come from $e^{A_NH_0 + B_NH_P}$ to $e^{\alpha_NH_0}e^{\beta_NH_P}$, what is the relation between $A_N$ and $\alpha_N$?

note: I reformulated my question inspired by the answer of DaftWullie. However, it is basically the same question as before.

Answer 1

Unfortunately, the calculation is not quite so simple. One way to see this is imagine that $H_0=X$ and $H_1=Z$, Pauli matrices on a single qubit. Any adiabatic with the specified initial/final conditions would have to convert initial state $|+\rangle$ into final state $|0\rangle$, i.e. the final unitary is $(X+Z)/\sqrt{2}$. Which means that $\alpha=\beta=\frac{\pi}{2\sqrt{2}}$. But we had a lot more freedom to pick $\alpha$ and $\beta$ than that!

So, what's gone wrong? Unitary evolution is derived from the Schrodinger equation $$ \frac{d|\psi\rangle}{dt}=-iH|\psi\rangle. $$ If $H$ is constant in time, then the solution is $e^{-iHt}|\psi\rangle$. If $H$ varies in time, but commutes with itself at all times, the solution is $e^{-i\int H(t)dt}|\psi\rangle$. However, in general, this property is not true and so the solution cannot be written like this.

Nevertheless, you will sometimes see the solution written as $$e^{-i\int H(t)dt}|\psi\rangle$$ Hopefully, wherever that appears, there's a note to emphasise that the integral is not quite the conventional integral, but "time ordered integral". What this really means is the limit of the Trotter formula $$ e^{-iH((2N-1)\delta/2)\delta}\ldots e^{-iH(3\delta/2)\delta}e^{-iH(\delta)\delta}|\psi\rangle $$ where $N\delta=T$. This is the proper Trotter-Suzuki expansion of the time evolution. The true mapping between QAOA and adiabatic thus lets you vary independently the angles at each time step, and you have lots of steps. You can then apply various approximations in the hope of reducing the circuit complexity - reducing the number of steps in the Trotter decomposition, and/or assuming many of the angles are the same. Will those approximations still give you good enough answers? That probably depends on your application although there are reasons for optimism. (There may be more than just reasons for optimism, but I'm not up to date on my reading.)

If you have one step $$ e^{-iH(t)\delta}, $$ then if $\delta$ is small you will be able to approximate it as $$ e^{-iH_0A(t)\delta}e^{-iH_PB(t)\delta}. $$ In fact, there's a second order approximation that works much better: $$ e^{-iH_0A(t)\delta/2}e^{-iH_PB(t)\delta}e^{-iH_0A(t)\delta/2}, $$ remembering that you'll be able to combine the two neighbouring $e^{-iH_0A(t)\delta/2}$ terms in an expansion. Again, if $\delta$ is not small enough, you're just kind of hoping it's a good enough approximation.