I try to understand precisely the link between AQC and QAOA, through the Trotter-Suzuki formula. A similar question is Derivation of QAOA from AQC, but I was asked by moderators to post my question independently. So here it is.

In quantum adiabatic computing, the Hamiltonian is as follows : \begin{equation}\tag{1} \mathcal{H} (t)= s(t)\mathcal{H}_{c}+ (1-s(t))\mathcal{H}_{m} \end{equation} with $s(0)=0$ and $s(T)=1$. The duration time $T$ is supposed to guarantee that the final state $|\psi\rangle(T)$ is $\varepsilon > 0$ close to the ground state of $\mathcal{H}_{c}$, the smaller $\varepsilon$, the greater $T$.

The Schrödinger equation gives : \begin{equation} U(t)= e^{-\frac{i}{\hbar}\int_{0}^{T}\mathcal{H}(u)\,du}= e^{-\frac{i}{\hbar}\biggl(\mathcal{H}_{c}\int_{0}^{T}s(u)\,du+\mathcal{H}_{m}\int_{0}^{T}[1-s(u)]\,du\biggr)} = e^{-\frac{i}{\hbar}\biggl(\mathcal{H}_{c}S(T)+\mathcal{H}_{m}[T-S(T)]\biggr)} \end{equation}

Applying the Trotter-Suzuki formula would give : \begin{equation}\tag{2} U(T)\approx \biggl[e^{-\frac{i}{\hbar}\mathcal{H}_{m} \frac{T-S(T)}{n}}e^{-\frac{i}{\hbar}\mathcal{H}_{c}\frac{S(T)}{n}}\biggr]^{n} \end{equation}

for $n\gg 1$ sufficiently high.

This formula is great as it lets one approach $U(T)$ by successively applying Hamiltonian $\mathcal{H}_c$ or $\mathcal{H}_m$ (the mixer) with some coefficients.

On the other hand, the idea usually developed to draw a link between AQC and QAOA is : \begin{equation}\tag{3} U(T)= U(t_n, t_{n-1})U(t_{n-1}, t_{n-2})\dots U(t_{2}, t_{1})U(t_{1}, t_{0}) \end{equation} with $t_0 = 0$ and $t_n = T$.

This formula derives from the exact formula : \begin{equation} U(t)= e^{-\frac{i}{\hbar}\int_{0}^{T}\mathcal{H}(u)\,du}= e^{-\frac{i}{\hbar}\biggl[\int_{0}^{t_1}\mathcal{H}(u)\,du+\dots+\int_{t_{n-1}}^{t_n}\mathcal{H}(u)\,du\biggr]} =e^{-\frac{i}{\hbar}\int_{0}^{t_1}\mathcal{H}(u)\,du}\dots e^{-\frac{i}{\hbar}\int_{t_{n-1}}^{t_n}\mathcal{H}(u)\,du} \end{equation}

For each time interval : \begin{equation} U(t_{i+1},t_{i}) = e^{-\frac{i}{\hbar}\int_{t_{i}}^{t_{i+1}}\mathcal{H}(u)\,du}= e^{-\frac{i}{\hbar}(\mathcal{H}_{c}\gamma_{i}+\mathcal{H}_{m}\beta_{i})} \end{equation}

Given that : \begin{equation} \begin{split} \gamma_{i}&= \int_{t_{i}}^{t_{i+1}}s(u)\,du\simeq s(t_{i})\,dt_{i}\simeq s(t_{i}) \frac{T}{n}\\ \beta_{i}&= \int_{t_{i}}^{t_{i+1}}[1-s(u)]\,du\simeq [1 -s(t_{i})]\,dt_{i}\simeq [1 -s(t_{i})]\frac{T}{n} \end{split} \end{equation}

The time segment can be approached again by Trotter Suzuki formula : \begin{equation} U(t_{i+1},t_{i}) = e^{-\frac{i}{\hbar}\int_{t_{i}}^{t_{i+1}}\mathcal{H}(u)\,du}= e^{-\frac{i}{\hbar}(\mathcal{H}_{c}\gamma_{i}+\mathcal{H}_{m}\beta_{i})} \simeq e^{-\frac{i}{\hbar}\mathcal{H}_{c}\gamma_{i}} e^{-\frac{i}{\hbar}\mathcal{H}_{m}\beta_{i}} \end{equation} where we used Eq. (2) but with $n=1$ (not the same "n" as in $t_n$) as $\gamma_i$ and $\beta_i$ are already "small" enough.

One could also have used a second order approximation :

\begin{equation} U(t_{i+1},t_{i}) \simeq e^{-\frac{i}{\hbar}\mathcal{H}_{c}\frac{\gamma_{i}}{2}} e^{-\frac{i}{\hbar}\mathcal{H}_{m}\beta_{i}} e^{-\frac{i}{\hbar}\mathcal{H}_{c}\frac{\gamma_{i}}{2}} \end{equation}

Then, this draws a direct link between Eq. 1 (AQC) and Eq. 2 (QAOA) : \begin{equation} \begin{split} |\psi\rangle (T)&= U_{m}(\beta_{p}) U_{c}(\gamma_{p})U_{m}(\beta_{p-1}) U_{c}(\gamma_{p-1})\dots U_{m}(\beta_{1}) U_{c}(\gamma_{1})|\psi (0)\rangle\\ &= e^{-i\beta_{p}H_{m}} e^{-i\gamma_{p}H_{c}}e^{-i\beta_{p-1}H_{m}} e^{-i\gamma_{p-1}H_{c}}\dots e^{-i\beta_{1}H_{m}} e^{-i\gamma_{1}H_{c}}|\psi (0)\rangle \end{split} \end{equation}

where $|\psi (0)\rangle$ is the ground state of $\mathcal{H}_m$.

Is my understanding correct ?



Your Answer

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

Browse other questions tagged or ask your own question.