In the quantum search algorithm with a known number of answers $M$ out of a search space of size $N$, it seems that the algorithm works pretty well (though not with pinpoint accuracy) for a fairly wide range of possible known answers. For instance, if the actual number of answers is $M' \in [4/9,4]M$ (for $M$ not too large compared to $N$, then Grover's algorithm optimized for $M$ will give an answer for $M'$ with probability around $1/2$ or better. Since this is a multiplicative interval, it follows that you can find a hit in time $O(\sqrt{N}\cdot \log N)$, which is not bad. In fact, you can get rid of the $\log N$ factor by looking more closely at the $O(\sqrt{N/M})$ running time of standard search.

This is dramatically simpler than the standard method of achieving $O(\sqrt{N})$ run time, which involves phase estimation. (Of course phase estimation is useful in its own right, and the method above only gives one satisfying solution and does not give the number of solutions, which is an interesting problem by itself.) I'm sure I'm not the first to notice this; does it appear somewhere?

I also know I've omitted many details, like what to do when $M$ is not very small compared to $N$. It's also worth noting that there are many examples (like hash collisions) where you have a good idea what $M$ will be without knowing its exact value.


I'm sure I'm not the first to notice this; does it appear somewhere?

Section 6 of the 1996 paper "Tight Bounds on Quantum Searching" by Boyer et al uses this strategy of iteratively trying different values of $M$, from a geometric sequence, to cover the possibility space.

One improvement they make over what you've described is that they do the big $M$ cases, the easy cases, first. This reduces the runtime to $O(\sqrt{N/M})$ from $O(\sqrt{N})$.

  • $\begingroup$ Thank you, that was exactly what I was looking for. $\endgroup$ Sep 21 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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