5
$\begingroup$

When running Grovers Algorithm one has to know how many solutions there are right? When the number of solutions are not known is then what do you do then?

$\endgroup$
6
$\begingroup$

It's a good question, as the number of solutions is sometimes unknown. The approach is described in Algorithm 2 of this paper. Essentially, you can repeatedly apply Grover's, but incrementally (yet exponentially) increase the number of applications of the Grover iterate; thus, if you find the solution, you're done. Otherwise, because the prior trial failed, there are likely more solutions than expected, so you can increase the number of applications of the iterate.

The entire proof is sketched out here, but here's the brief pseudocode:

m = 1
while m <= \sqrt{N}:
   pick k in {1 ... m}
   apply the Grover iterate k times to the superposition state
   measure the register; if a solution, exit and return
   otherwise, m = lambda * m

For some $ \lambda \in (1, \frac{4}{3}) $.

(Btw: This technique underlies Amplitude Amplification!)

$\endgroup$
3
  • $\begingroup$ Thankyou! But what about quantum counting? Is that a good Idea too? $\endgroup$
    – Hannah
    Aug 14 '20 at 21:09
  • 1
    $\begingroup$ I'm not sure asymptotically which is better - it might be! The Wiki page says that quantum counting can be used in conjunction with Grover's $\endgroup$
    – C. Kang
    Aug 14 '20 at 21:22
  • 1
    $\begingroup$ Quantum counting is nothing but quantum phase estimation on the Grover search iterate. So the technique for quantum search with an unknown number of marked items (i.e. amplitude amplification) gives rise to the counting algorithm in this instance also. $\endgroup$
    – Condo
    Aug 17 '20 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.