# Why is it crucial that the initial Hamiltonian does not commute with the final Hamiltonian in adiabatic quantum computation?

I've read in many sources and books on adiabatic quantum computation (AQC) that it is crucial for the initial Hamiltonian $\hat{H}_i$ to not commute with the final Hamiltonian $\hat{H}_f$, i.e. $\left[\hat{H}_i,\hat{H}_f\right]\neq 0$. But I've never seen an argument to why it's so important.

If we assume a linear time dependence the Hamiltonian of the AQC is $$\hat{H}\left(t\right)~=~\left(1-\frac{t}{\tau}\right)\hat{H}_i+\frac{t}{\tau}\hat{H}_f, \qquad \left(0\leq t\leq \tau \right)$$ where $\tau$ is the adiabatic time scale.

So my question is: Why is it crucial that the initial Hamiltonian does not commute with the final Hamiltonian?

In adiabatic QC, you encode your problem in a Hamiltonian such that your result can be extracted from the ground state. Preparing that ground state is hard to do directly, so you instead prepare the ground state of an 'easy' Hamiltonian, and then slowly interpolate between the two. If you go slow enough, the state of your system will stay in the ground state. At the end of your process, you'll have the solution.

This works according to the Adiabatic theorem. For the theorem to hold, there must be an energy gap between the ground state and the first excited state. The smaller the gap becomes, the slower you need to interpolate to prevent mixing between the ground state and first excited states. If the gap closes, such mixing cannot be prevent, and you can't go slow enough. The procedure fails at that point.

If the initial and final Hamiltonian commute, it means they have the same energy eigenstates. So they agree on which states get assigned energy, and only disagree on the energies they get. Interpolating between the two Hamiltonians just changes the energies. The final ground state would therefore have been an excited state at the beginning, and the original ground state becomes excited at the end. At some point, when passing by each other, the energies of these states will be be equal, and so the gap between them closes. This is sufficient to see that the energy gap must close at some point.

Having non-commuting Hamiltonians is therefore a necessary condition of keeping the gap open, and hence for AQC.

• This sounds quite convincing and clear. May you explicitly explain why there cannot be an avoided crossing during the adiabatic evolution (which would allow the nature of the ground state to change but with no degeneracy)? – agaitaarino Apr 27 '18 at 14:50

If two matrices (in this case, Hamiltonians) commute, they have the same eigenvectors. So, if you prepare a ground state of the first Hamiltonian, then that will (roughly speaking) remain an eigenstate throughout the whole adiabatic evolution, and so you get out just what you put in. There's no value to it.

If you want to be a little more strict, then it could be that your initial Hamiltonian has a degeneracy which is lifted by the second Hamiltonian, and you might be hoping to cause the system to evolve into the unique ground state. Note, however, that the degeneracy is lifted the instant there's a non-zero amount of the second Hamiltonian. Whatever effect it can have is an instantaneous one. I believe that you don't get a proper adiabatic evolution. Instead, you have to write your initial state as a superposition of the new eigenstates, and these start to evolve over time, but you never increase the overlap of your state with the target state (the ground state).

• Just wondering if your first statement is true. Take the Identity matrix for example, it commutes every Hamiltonian. But surely there is no reason for the identity matrix to have the same eigenvectors as an arbitrary Hamiltonian. – Turbotanten Apr 27 '18 at 11:57
• You can decompose the identity many in any basis, including the basis of the Hamiltonian. But the point is that it's highly degenerate, so then you're talking about my second paragraph. – DaftWullie Apr 27 '18 at 13:08

In the context of Ising optimizers having an initial Hamiltonian that commutes with the problem Hamiltonian means it is essentially products of $\sigma^Z$ operators, which means that its eigenstates are classical bitstrings. Hence the groundstate at the beginning ($t$=0) will be classical as well, not a superposition of all possible bitstrings.

Moreover, even going beyond the strict boundaries of AQC (e.g. open-system quantum annealing, QAOA etc.) if the driving Hamiltonian commutes then it cannot induce transitions between the eigenstates of the problem Hamiltonian but only change the phase of the amplitudes in the wavefunction; and you want a driver which is able to induce spin-flips in order to explore the search space.

Let's start with a simple example where $H_i$ and $H_f$ commute because they are both diagonal:

$H_i= \begin{pmatrix}1 & 0\\ 0 & -1 \end{pmatrix}$

$H_p= \begin{pmatrix}-1 & 0\\ 0 & -0.1 \end{pmatrix}$

The eigenvector with lowest eigenvalue (i.e. the ground state) of $H_i$ is $|1\rangle$ so we start in this state. The ground state of $H_f$ is $|0\rangle$ so this is what we're looking for.

Remember the minimum runtime for the AQC to give the correct answer to within an error $\epsilon$:
$\tau\ge \max_t\left(\frac{||H_i - H_f||^2}{\epsilon E_{\rm{gap}}(t)^3}\right)$.

This is given and explained in Eq. 2 of Tanburn et al. (2015).

• Let's say we want $\epsilon = 0.1$.
• Notice that $||H_i - H_f||^2 = 0.1$ according Eq. 4 of the same paper.
• Notice that $\frac{||H_i - H_f||^2}{\epsilon}=1$ (I've chosen $\epsilon$ so that this would happen, but it doesn't matter).
• We now have $\tau \ge \max_t\left(\frac{1}{E_{\rm{gap}}(t)^3}\right)$

So what is the minimum gap between ground and first excited state (which gives the $\max_t$) ?
When $t=20\tau/29$, the Hamiltonian is:

$H=\frac{9}{29}H_i + \frac{20}{29}H_p$

$H=\frac{9}{29}\begin{pmatrix}1 & 0\\ 0 & -1 \end{pmatrix} + \frac{20}{29}\begin{pmatrix}-1 & 0\\ 0 & -0.1 \end{pmatrix}$

$H=\begin{pmatrix}\frac{9}{29} & 0\\ 0 & -\frac{9}{29} \end{pmatrix}+\begin{pmatrix}-\frac{20}{29} & 0\\ 0 & -\frac{2}{29} \end{pmatrix}$

$H=\begin{pmatrix}\frac{-11}{29} & 0\\ 0 & -\frac{11}{29} \end{pmatrix}$

So when $t=\frac{20}{29}\tau$, we have $E_{\rm{gap}}=0$ and the lower bound on $\tau$ is essentially $\infty$.

So the adiabatic theorem still applies, but when it states that the Hamiltonian needs to change "slowly enough", it turns out it needs to change "infinitely slowly", which means you will not likely ever get the answer using AQC.

• Thanks! I like the example. Though that's a new expression of the minimum runtime that I've never seen before. Usually in the literature the adiabatic condition is given by $\tau \gg \frac{\underset{0\leq s \leq 1}{\text{max}} \left|\langle\psi_1(s)| \dfrac{d \hat{\mathscr{H}}(s)} {d s}|\psi_0(s)\rangle\right|} {\underset{0\leq s \leq 1}{\text{min}}\Delta^2(s)}; \qquad s\equiv\frac{t}{\tau}$ where $\Delta^2(s) = (E_1(s)-E_0(s))^2$. See Ref [1] & [2] – Turbotanten Jul 2 '18 at 7:44
• @Turbotanten: Thanks for the bounty. My proof works whether we use 1/gap^2 or 1/gap^3. In both cases gap=0 means runtime = infinity. In your expression, we can just have "max_s" on the outside, then we don't need "min_s" in the denominator. Also reference 2 of the Tanburn paper that I linked to, gives the gap^3 formula, which is a slightly tighter bound than the gap^2 formula. It is still popular to use the (slightly looser bound of) gap^2, mainly because some people haven't seen the recent literature on gap^3. – user1271772 Jul 2 '18 at 17:59