3
$\begingroup$

In Grover's algorithm we have the solution superposition $|\omega\rangle$ and the non-solution superposition $|s'\rangle$ (containing all non-solutions). Furthermore, we rotate our starting equal-superposition state $|s\rangle$ (where all states have equal probability) towards $|\omega\rangle$ during the algorithm.

It is clear that in a typical scenario, the number of solutions is a lot smaller than the number of elements and therefore $|s\rangle$ is a lot 'closer' to $|s'\rangle$ than to $|\omega\rangle$ (i.e. $\langle s |s' \rangle \gg \langle s | \omega \rangle$).


So the question is: is there no way we can rotate towards $|s' \rangle$ instead of rotating towards $| \omega \rangle $, as this would take a lot fewer steps?


Obviously, knowing the non-solutions is equivalent to knowing the solutions themselves.

Even though the search algorithm is already optimal (i.e. such a circuit cannot exist probably), it is not clear at all to me why we cannot construct a circuit that does this opposite rotation. Is there some intuition behind that?

1

Image from Wikipedia entry (see here)

$\endgroup$
1
  • $\begingroup$ As you alluded to, the optimality of Grover implies that the algorithm must make at least $\Omega(\sqrt{2^n})$ steps or "rotations", so you simply can't expect to be able to do less. You also said that knowing non-solutions is the same as finding solutions, so if you could rotate in fewer steps in the "other direction" then you would be contradicting optimality. $\endgroup$
    – Condo
    Mar 17, 2022 at 15:38

1 Answer 1

3
$\begingroup$

Well, technically, this works, but the complexity is worse than what you think. The problem is this sentence:

Obviously, knowing the non-solutions is equivalent to knowing the solutions themselves.

That's true, but knowing the non-solutions entirely is hard. Let us assume that I'm looking for an $n$-bit element $w$ amongst all possible $n$-bit strings (for instance, a cipher's key).

Rotating "the other way" is simple : it takes $\mathcal{O}\left(\sqrt{\frac{2^n-1}{2^n}}\right)=\mathcal{O}(1)$ steps to get an answer $s$ which we know isn't a solution to our problem. We then continue until we've completely determined the set of non-solutions, which takes $O\left(2^n\right)$ operation, since the aforementioned set has $2^n-1$ elements.

On the other hand, running Grover towards the solution runs in $\mathcal{O}\left(2^{\frac{n}{2}}\right)$.

More generally, as @Condo mentioned in the comments, Grover's algorithm is exactly optimal for the problem it solves. That is, unless you have more assumptions about your problem, it is not possible to find an algorithm that will do better than Grover's.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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