1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 18, 2023 at 14:24
  • $\begingroup$ @MateusAraújo Of course I'm not going to do that. But I want to understand how Grover works :) $\endgroup$
    – leonboe1
    Jul 18, 2023 at 14:32

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What if I overshoot the axis and just try to do more iterations? Then I always turn in circles, counterclockwise. Isn't it possible that I'll end up on the solution at some point? $\endgroup$
    – leonboe1
    Jul 19, 2023 at 9:37

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.