Confusion with the proof of constraints for a particular adiabatic quantum evolution

Question

[This might be related to one of my previous unanswered questions.]

This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Daniel Nagaj. It is the theorem 1 on page 3. The theorem is as follows.

Let $H_P$ be diagonal in the $z$ basis with a ground state subspace of dimension $k$. Let

$$ H(t) = \left(1 - \frac{t}{T} \right) E \left( \mathbb{I} - > |s\rangle \langle s| \right) + \left( \frac{t}{T} \right) H_P $$ .

Let $P$ be the projector onto the ground state subspace of $H_P$ and let $b > 0$ be the success probability, that is, $b = \langle \Psi (T) > | P | \Psi (T) \rangle $. Then

$$ T \ge \frac{b}{E} \sqrt{\frac{N}{k}} - \frac{2 \sqrt{b}}{E} $$.

As the proof proceeds I can't really follow it completely.

For example, there are three equations at the bottom of page 3 which evaluates $S(t)s$. As per the paper $S(t)$ is the sum on $x$. But the expression looks to involve norms. I understand that there are more than one kind of norms. What kind of norm are we talking about here? Why? What is the physical significance of this quantity in this context?

Answer 1

The norms are the usual norms of a ket vector, i.e. $|||a\rangle||^2 = \langle a|a\rangle$.

What did we do on the bottom of page 3? It is really running the argument from the An Analog Analogue paper backwards.

Imagine we start from the state $|g_x\rangle$ (a particular ground state of the final Hamiltonian $H_{P}$, related to $|x\rangle$), and evolve backwards with an inverse algorithm. Similarly to AAA, we are looking at whether evolving backwards with no purpose (without knowledge of $x$) makes the evolution any different from evolving with a Hamiltonian that involves $x$. We show that for a successful algorithm, it is necessary that the quantity $S(0)$ must be large enough. However, running back in time from $T$ to $0$, this $S(t)$ doesn't change much, which allows us to show that $T$ must be large.