# Grover's algorithm: Rotation in opposite direction

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?

Image from Wikipedia entry (see here)

• 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. Commented Mar 17, 2022 at 15:38

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)$$.