How to understand Deutsch-Jozsa algorithm from an adiabatic perspective?

Question

I'm trying to understand the Deutsch-Jozsa algorithm from an adiabatic perspective as presented in Adiabatic quantum computing A: Review of modern physics, vol 90, (2018) pp 015002-1 (arXiv version).

When explaining the unitary interpolation technique, the authors begin with:

The initial Hamiltonian is chosen such that its ground state is the uniform superposition state [$|\phi\rangle = |+\rangle^{\otimes n}$], i.e., $H(0) = w\sum^{n}_{i = 1}|-\rangle_i \langle-|$, where $w$ is the energy scale.

• How can I calculate the ground state of $H(0)$?

Also, I have seen, but don't remember exactly where, an observation that $H(0)$ is introduced in a such a way that a penalty is provided for any state having a contribution of $|-\rangle$. What does it mean?

Then the paper goes on and states that:

An adiabatic implementation requires a final Hamiltonian $H(1)$ such that its ground state is $|\Psi(1)\rangle = U|\Psi(0)\rangle$, and that this can be accomplished via a unitary transformation of $H(0)$, i.e. $H(1) = UH(0)U^\dagger$.

where $U$ is a diagonal matrix such that:

$$U = diag[(-1)^{f(0)}, \dots,(-1)^{f(2^n-1)}] $$

At this point, I don't see why bother with this; since to arrive at the answer using adiabatic quantum computation I need to construct a unitary in such a way that I will already have the answer if $f$ is balanced or constant. Am I overlooking anything?

---

Trying to workout an example, setting $n = 1$ and making $f(x) = 1$ (constant 1).

$$H(0) = w|-\rangle\langle-| = w\pmatrix{1 & -1 \\ -1 & 1}$$

I will set $w = 1$ to get it out of the way. Then,

$$U = \pmatrix{-1 & 0 \\ 0 & -1} $$ $$H(1) = UH(0)U^\dagger = \pmatrix{-1 & 0 \\ 0 & -1}\pmatrix{1 & -1 \\ -1 & 1}\pmatrix{-1 & 0 \\ 0 & -1}$$ $$H(1) = \pmatrix{1 & -1 \\ -1 & 1}$$

Meaning that the ground state of $H(1)$ is $|+\rangle$.

If now I do the function $f(x) = x$, then $$U = \pmatrix{1 & 0 \\ 0 & -1} $$

and

$$H(1) = \pmatrix{1 & 1 \\ 1 & 1}$$

which, I suppose, has ground state $|-\rangle$. And with this we can differentiate between a constant and a balanced function $f$.

Answer 1

How can I calculate the ground state of $H(0)$?

The ground state means the eigenvector with lowest eigenvalue. Take your given example, $$ H(1)=\left(\begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array}\right). $$ You solve $\text{det}(H(1)-\lambda\mathbb{I})=0$ to find the eigenvalues. In this case, $\lambda=0,2$. So you're interested in the smallest eigenvalue, 0. So, we solve for $H(1)|\lambda\rangle=0$, which you'll find is satisfied for the state $|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$.

To find the ground state of $H(0)$ in its general form, the easiest way is just to recognise what's going on. If I apply $$ H(0)|+\rangle^{\otimes n}=0. $$ So, this is an eigenvector of 0 eigenvalue. Whenever I change a $|+\rangle$ into a $|-\rangle$, the eigenvector relation is still satisfied, but the eigenvalue increases by $w$ each time. So there is an energy penalty of $w$ for having a $|-\rangle$ state. In this way, we can construct a complete basis, and find all the eigenvalues: $kw$, repeated $\binom{n}{k}$ times for $k=0,1,\ldots ,n$.

At this point, I don't see why bother with this; since to arrive at the answer using adiabatic quantum computation I need to construct a unitary in such a way that I will already have the answer if f is balanced or constant.

Well, Deutsch-Jozsa is very much defined in terms of an oracle, i.e. the unitary is something that is given directly to you, and you can't look inside it to see what's happening. You do not construct the unitary $U$. The question then is how long your algorithm needs to run for in order to find out if the function is constant or balanced. This is where the adiabatic part comes in; using the oracle in an adiabatic way, you can calculate how long it takes, and find it's a constant time.