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 1


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$

  • $\begingroup$ The author echoed your answer. Thanks. I just asked them the following though. $\endgroup$ Oct 28, 2013 at 4:07
  • $\begingroup$ 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." $\endgroup$ Oct 28, 2013 at 4:07
  • $\begingroup$ 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. $\endgroup$ Oct 28, 2013 at 5:29
  • 1
    $\begingroup$ 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! $\endgroup$
    – Martin
    Oct 28, 2013 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.