Grover's algorithm: Rotation in opposite direction

Question

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)

Answer 1

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.