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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.