# Confusion about a lemma on the time constraint of an adiabatic evolution (arXiv:quant-ph/0604077)

I am going through the paper Quantum adiabatic evolutions that can't be used to design efficient algorithms by Zhaohui Wei and Mingsheng Ying. On the second page they prove a lemma. The statement goes as follows.

Lemma 1 Suppose $f : \{ 0,1 \}^n \to R$ is a function that is bounded by a polynomial of $n$. Let $H_0$ and $H_1$ be the initial and the final Hamiltonians of a quantum adiabatic evolution with a linear path $H(t)$. Concretely,

$$H_0 = I - |\alpha \rangle \langle \alpha |$$, $$H_1 = \sum_{z=1}^{N} f(z)|z\rangle \langle z|$$, $$H(t) = (1- \frac{t}{T}) H_0 + (\frac{t}{T}) H_1$$,

where, $T$ is the running time of the quantum adiabatic evolution and

$$|\alpha \rangle = |0^n \rangle = \frac{1}{\sqrt{N}} \sum_{i=1}^{N} > |i\rangle, N = 2^n$$.

Then we have

$$g_{min} < \frac{2}{2^{\frac{n}{2} - \frac{n}{100}}}$$.

This $T$ is exponential in $n$.

I don't get the definition of $|\alpha\rangle$. Suppose $n = 3$. So,

$$|\alpha \rangle = |0^3 \rangle = |000 \rangle = \left( \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array} \right)$$

If I use the other expression,

$$|\alpha \rangle = \frac{1}{\sqrt{N}} \sum_{i=1}^{N} |i\rangle \\ = \frac{1}{2\sqrt{2}} \sum_{i=1}^{8} |i\rangle \\ = \frac{1}{2\sqrt{2}} \left( |1\rangle + |2\rangle + |3\rangle + |4\rangle + |5\rangle + |6\rangle + |7\rangle + |8\rangle \right) \\ = \frac{1}{2\sqrt{2}} \left( |000\rangle + |001\rangle + |010\rangle + |011\rangle + |100\rangle + |101\rangle + |110\rangle + |111\rangle \right)$$

So, I am getting two different values of $|\alpha \rangle$ and definitely one of them is not true. What am I missing here?

-

I'd say you are missing the "hat", i.e. they write $|\hat{0^n}\rangle$ instead of $|0^n\rangle$ and never really define what they mean by that before the lemma. If, however, you look at eqns (19)-(21), you'll find a definition that the hat indicates the Hadamard basis - and then the two definitions should be equivalent.
To be completely clear: it seems to me that the sum definition is correct, i.e. $|\alpha\rangle \propto \sum_i |i\rangle$