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

<p>What did we do on the bottom of page 3? It is really running the argument from the <a href="http://arxiv.org/abs/quant-ph/9612026" rel="nofollow">An Analog Analogue</a> paper backwards.</p>

<p>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 <a href="http://arxiv.org/abs/quant-ph/9612026" rel="nofollow">AAA</a>, 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.</p>

CC BY-SA 3.0
2013-11-04T13:56:17.860Z
2013-11-04T13:56:17.860Z
Daniel Nagaj
<p><em>[This might be related to one of my <a href="https://cstheory.stackexchange.com/questions/19522/questions-about-farhis-pre-adiabatic-paper">previous unanswered questions</a>.]</em></p>

<p>This proof belongs to the paper, <a href="http://arxiv.org/abs/quant-ph/0512159" rel="nofollow noreferrer">How to Make the Quantum Adiabatic Algorithm Fail</a> by Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Daniel Nagaj. It is the theorem 1 on page 3. The theorem is as follows.</p>

<blockquote>
  <p>Let $H_P$ be diagonal in the $z$ basis with a ground state subspace of
  dimension $k$. Let </p>
  
  <p>$$ H(t) = \left(1 - \frac{t}{T} \right) E \left( \mathbb{I} -
&gt; |s\rangle \langle s|  \right) + \left( \frac{t}{T} \right) H_P $$ .</p>
  
  <p>Let $P$ be the projector onto the ground state subspace of $H_P$ and
  let $b &gt; 0$ be the success probability, that is, $b = \langle \Psi (T)
&gt; | P | \Psi (T) \rangle $. Then</p>
  
  <p>$$ T \ge \frac{b}{E} \sqrt{\frac{N}{k}} - \frac{2 \sqrt{b}}{E} $$.</p>
</blockquote>

<p>As the proof proceeds I can't really follow it completely.</p>

<p>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?</p>

<cc.complexity-theory><quantum-computing><quantum-information><physics><norms>
Confusion with the proof of constraints for a particular adiabatic quantum evolution
Omar Shehab
# Confusion with the proof of constraints for a particular adiabatic quantum evolution

(Asked by: username_0 on 2013-10-26)

*[This might be related to one of my [previous unanswered questions](https://cstheory.stackexchange.com/questions/19522/questions-about-farhis-pre-adiabatic-paper).]*

This proof belongs to the paper, [How to Make the Quantum Adiabatic Algorithm Fail](http://arxiv.org/abs/quant-ph/0512159) 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?

**Tags:** cc.complexity-theory, quantum-computing, quantum-information, physics, norms

---

## 1 answers

### Answer by username_1 on 2013-11-04. Score: 3 | Accepted answer

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](http://arxiv.org/abs/quant-ph/9612026) 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](http://arxiv.org/abs/quant-ph/9612026), 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.


---

