Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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?

share|improve this question
    
"Gover" -> "Grover"? Or is there some other algorithm out there? –  Chris White Apr 10 '13 at 2:16
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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