# Does Grover work for more than N/2 solutions?

I know that only one iteration is required to find the correct answer for $$M=N/4$$ solutions with Grover's algorithm. Also, I noticed that Grover never finds a solution when there are $$N/2$$ solutions.

What I am unsure about is what happens between $$N/4$$ and $$N$$ solutions. I assume that between $$N/4$$ and $$N/2$$ solutions, Grover will find the correct solution, but it will take more than just one iteration. For more than $$N/2$$ solutions, I don't have an idea how to check/prove what happens. Does anyone have an idea?

• If you have $N/2$ or more solutions there is no point in running Grover, just try random solutions and you'll succeed with probability at least 1/2. Commented Jul 18, 2023 at 14:24
• @MateusAraújo Of course I'm not going to do that. But I want to understand how Grover works :) Commented Jul 18, 2023 at 14:32

If there are more than $$N/2$$ solutions then there are more solutions than non-solutions. This actually has the essential effect of making the states that are marked by the algorithm unmarked and the states that are unmarked marked during the flipping around the mean that occurs with the diffusion operator, meaning if there are $$N/2 + k$$ solutions for $$0 < k < N/2$$ then it will function as a search to amplify the probabilities of the $$N/2 - k$$ non-solutions, and will be equivalent in the number of iterations required to optimize this probability. In terms of what Grover's algorithm is used for, this idiosyncrasy is not normally a big deal since Grover's algorithm assumes by the requirements of its design one has a tractable method to determine whether a specific given input is a solution or not, meaning if there are more solutions than otherwise just classically picking a few random inputs and trying the check on them should find you a solution.
If one makes a 2-dimensional real plane with the two axes being associated with the orthogonal vectors of a uniform superposition of all the unmarked states (denoted $$|s\rangle$$) and a uniform superposition of all marked states (denoted $$|\omega\rangle$$), then the opening uniform superposition of all states will be rotated counterclockwise from $$|s\rangle$$ at an angle of $$\sin^{-1}(\sqrt{\frac{m}{N}})$$ towards $$|\omega\rangle$$ where $$m$$ is the number of solutions, and each iteration will do a further counterclockwise rotation of twice that value. The closer it is rotated to either side of the $$|\omega\rangle$$ axis, the better the probability. Under this paradigm, the nature of all these statements of what happens with a certain solution density can be shown: if exactly $$N/2$$ solutions then the starting angle is $$\sin^{-1}(\frac{1}{\sqrt{2}}) = \frac{\pi}{4}$$ and each iteration will rotate by $$\pi/2$$, meaning it will just switch between the diagonals of each quadrant and never reach the axes themselves. At $$N/4$$ then the angle is $$\pi/6$$ and after adding twice that one gets $$\pi/2$$ which lands you right on the axis, hence why that requires a single iteration. Between the two, a single iteration will overshoot the axis and provide a weaker and weaker improved probability as the number of solutions gets closer and closer to $$N/2$$. In the end though, if one is dealing with this sort of ratio of solutions to non-solution there's not really a quantum advantage to be gained by a search here, it's finding a needle in a haystack that is more than a quarter needles. Though, the related quantum counting algorithm can, from the Grover operator, determine the number of solutions, which may be classically harder.