5

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?

Norbert Schuch
  • 6,521
  • 16
  • 27
Hannah
  • 529
  • 2
  • 9

1 Answers1

6

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!)

C. Kang
  • 1,716
  • 8
  • 23
  • Thankyou! But what about quantum counting? Is that a good Idea too? – Hannah Aug 14 '20 at 21:09
  • 1
    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 – C. Kang Aug 14 '20 at 21:22
  • 1
    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. – Condo Aug 17 '20 at 13:49