# Is it ever necessary to extend an analysis of Grover's algorithm beyond $k/N = 1/2$?

Is it ever necessary to extend an analysis of Grover's algorithm beyond $k/N = 1/2$, where $k$ is the number of "hits" in a total of $N$ possible values for $|\,x\rangle$?

If we know $k$, and know that it is greater than $1/2$, can't we just redefine hits as misses by modifying the oracle to produce

$$-(-1)^{f(x)}\,|\,x\rangle$$

(note the additional negative sign) and then measure according to whatever strategy for $k<1/2$ produces satisfactory hit probabilities, $p_h$, since we can then say with confidence $p_h$ that one of the unobserved outcomes is a hit?

-
"Gover" -> "Grover"? Or is there some other algorithm out there? –  Chris White Apr 10 '13 at 2:16

Consider a state $\def\ket#1{|#1\rangle}\ket{\psi(\alpha)} = \cos(\alpha) \ket{U} + \sin(\alpha)\ket{M}$, where $\ket{U}$ and $\ket{M}$ are respectively the uniform superpositions over the unmarked and marked elements. Note that the uniform superposition $\ket{\Psi} \propto \ket{0} + \ket{1} + \cdots + \ket{N-1}$ is such a state, specifically $\ket{\Psi} = \ket{\psi(\theta)}$ such that $$\sin(\theta) = k/N, \qquad\qquad\cos(\theta) = \sqrt{1 - k^2/N^2\,}.$$ Grover's iterate rotates the state within the set of such states, by mapping $\ket{\psi(\alpha)} \mapsto \ket{\psi(\alpha + 2\theta)}$.

Suppose that $N/2 < k < N$, and let $\theta' = \pi/2 - \theta > 0$. Then $2\theta = \pi - 2\theta'$. That is to say, applying Grover's iterate is equivalent to a rotation of $\pi - 2\theta'$; and as the rotation of $\pi$ is equivalent to a global phase (which changes the vector which we use to representing the state, but not the state itself), we may say that the effect is the same as a rotation by $-2\theta'$. The effect is then to rotate the state away from $\ket{M}$, the target state which we would like to sample from. Applying Grover's algorithm when $k > N/2$ is then counterproductive.

What happens when you "relabel" the marked elements as unmarked, and vice-versa? Well, changing the labels you give to them doesn't change what set you end up sampling from; the only place that this makes a difference is in the sign-flip for reflecting about the "unmarked items" axis. But this only differs from reflecting about the "marked items" axis by a global phase of $-1$, which (again) has no effect on the state.

So no matter what you call the set $M$ of items you would like to sample from, if it contains $k > N/2$ items, you're better off not using Grover's algorithm at all, and just doing random sampling.

As a final remark, consider what happens when $k = N/2$: in this case we have $\theta = \pi/4$, and the rotation is by angles of $\pi/2$ — which maps \begin{align*}\tfrac{1}{\sqrt 2} \ket{U} + \tfrac{1}{\sqrt 2} \ket{M} \;&\mapsto\; -\tfrac{1}{\sqrt 2} \ket{U} + \tfrac{1}{\sqrt 2} \ket{M} \\&\mapsto\; -\tfrac{1}{\sqrt 2} \ket{U} - \tfrac{1}{\sqrt 2} \ket{M} \\&\mapsto\; \tfrac{1}{\sqrt 2} \ket{U} - \tfrac{1}{\sqrt 2} \ket{M} \\&\mapsto\; \tfrac{1}{\sqrt 2} \ket{U} + \tfrac{1}{\sqrt 2} \ket{M}\end{align*} cyclically, and to no effect at all. Similarly, if $k < N/2$ but $1/2 - k/N \ll 1$, the amount of time to amplify from $\alpha = \theta$ to $\alpha = \pi/2$ will be about the same as if $k/N \ll 1$, so that it's very counterproductive to use Grover's algorithm rather than just sampling items until one obtains elements of $M$.

For $k/N$ much larger than $1/4$, there's simply no benefit (asymptotic or otherwise) to using Grover's algorithm.

-
Yes, so if whatever strategy I adopt using (unmodified) Grover's algorithm achieves a probability of a hit of $p_h$, then can't I say after measuring $x\in S$ using Grover's, modified as above, that any of the unmeasured values, $y\in S\setminus x$, is a hit with probability $1-p_h$? And if so then whenever I've got a $k$ that gives me an unsatisfactory $p_h$, can't I switch to the modified version? –  raxacoricofallapatorius Apr 10 '13 at 1:08
Assume for the moment that I'm following a strategy that I'm happy with up to $k/N = 1/2$. –  raxacoricofallapatorius Apr 10 '13 at 1:39
@raxacoricofallapatorius: I have revised my answer to better answer your question. –  Niel de Beaudrap Apr 10 '13 at 12:18