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?

-

1 Answer

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$

-
The author echoed your answer. Thanks. I just asked them the following though. –  Omar Shehab Oct 28 '13 at 4:07
Can I simply interpret the Theorem 1 as follows? "If the eigenstate of the initial Hamiltonian are superposition of all possible states we cannot perform the adiabatic evolution with a diagonal Hamiltonian as the problem Hamiltonian. " Can I simply interpret the Theorem 2 as follows? "Having diagonal Hamiltonians as both initial and problem Hamiltonians will not work." –  Omar Shehab Oct 28 '13 at 4:07
The author replied as follows: To be frank, both of the two interpretations are inaccurate. The proofs are exactly for the cases listed only, and do not work for any other situation. Besides, I think the complexity to make a statement for a case as general as your first interpretation is probably NP-hard. –  Omar Shehab Oct 28 '13 at 5:29
If I remember correctly, the running time of the algorithm basically depends on the size of the gap between ground state and first excited state (this would also fit with the abstract of the paper here). This makes intuitive sense, because if the gap is big, I can perturb the Hamiltonian faster and still stay in the ground state (no energy to excite). Now in general, the gap problem is extremely hard (in all generality even undecidable), so what the authors say makes sort of sense to me. Thanks though for the further information! –  Martin Oct 28 '13 at 10:05