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