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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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!)
-
$\begingroup$ Thankyou! But what about quantum counting? Is that a good Idea too? $\endgroup$– HannahCommented Aug 14, 2020 at 21:09
-
1
-
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$– CondoCommented Aug 17, 2020 at 13:49