Corollary 1.1

Corollary 1.1: We seek to show that after applying A, both k^' and l^' are positive, under the following conditions:

Let the state vector for:

• one state have amplitude k
• each of the remaining (N - 1) states the amplitude is l

And let:

• k and l be real
• k be negative, and l be positive
• $\left\vert\vphantom{\frac{k}{l}}\right.$${\frac{{k}}{{l}}}$$\left.\vphantom{\frac{k}{l}}\right\vert$ < $\sqrt{{N}}$
• N$\ge$9

Then, after applying A, both k^' and l^' are positive.

Proof:

First we will show that k^' is positive:

• From theorem 1 we know k^' = $\left(\vphantom{\frac{2}{N} - 1 }\right.$${\frac{{2}}{{N}}}$ - 1$\left.\vphantom{\frac{2}{N} - 1 }\right)$k + 2${\frac{{(N-1)}}{{N}}}$l.

• By assumption k is negative. Since N > 2 by assumption, $\left(\vphantom{\frac{2}{N} - 1 }\right.$${\frac{{2}}{{N}}}$ - 1$\left.\vphantom{\frac{2}{N} - 1 }\right)$ is negative.

• By assumption l is positive. Since N > 2 by assumption, 2${\frac{{(N-1)}}{{N}}}$ is positive.

• Thus the expression for k^' is of the form negative*negative + positive*positive, which must be positive.

Next we will show that l^' is positive:

• From theorem 1 we know l^' = ${\frac{{2}}{{N}}}$k + ${\frac{{(N-2)}}{{N}}}$l.

• By assumption $\left\vert\vphantom{\frac{k}{l}}\right.$${\frac{{k}}{{l}}}$$\left.\vphantom{\frac{k}{l}}\right\vert$ < $\sqrt{{N}}$

• For N$\ge$9, ${\frac{{(N-2)}}{{2}}}$ > $\sqrt{{N}}$. Therefore when N$\ge$9: ${\frac{{(N-2)}}{{2}}}$ > $\sqrt{{N}}$ > $\left\vert\vphantom{\frac{k}{l}}\right.$${\frac{{k}}{{l}}}$$\left.\vphantom{\frac{k}{l}}\right\vert$, and:
  l^' = $${\frac{{2}}{{N}}}$$k + $${\frac{{(N-2)}}{{N}}}$$l > $${\frac{{2}}{{N}}}$$k + $$\left\vert\vphantom{\frac{k}{l}}\right.$$$${\frac{{k}}{{l}}}$$$$\left.\vphantom{\frac{k}{l}}\right\vert$$l

• Because k is negative and l is positive by assumption, $\left\vert\vphantom{\frac{k}{l}}\right.$${\frac{{k}}{{l}}}$$\left.\vphantom{\frac{k}{l}}\right\vert$ = ${\frac{{-k}}{{l}}}$.

• Therefore:
  l^' = $${\frac{{2}}{{N}}}$$k + $${\frac{{(N-2)}}{{N}}}$$l > $${\frac{{2}}{{N}}}$$k + $${\frac{{-k}}{{l}}}$$l = ($${\frac{{2}}{{N}}}$$ - 1)k

• It follows that l^' is positive because k is positive and ${\frac{{2}}{{N}}}$ -1 > 0 for N$\ge$3 (and by assumption N$\ge$9).

[Grover96]