Suppose we are using GA (Grover's algorithm) such that we are given it has 2 or more solutions. The search space is of size $N$. We all know Grover's algorithm has, at worst, a time complexity proportional to $\sqrt{N}$. Now assume we are using quantum phase estimation to get the exact number of solutions in GA to precision $p$ bits (which is actually an angle on the complex unit circle) – so this means we will need to apply quantum phase estimation to get this angle – from this we get the exact numbers of solutions in GA. Using GA with phase estimation in this way is well known.

My question is, does the quantum phase estimation algorithm, in the worst case, run in polynomial time and polynomial space according to $N$?

  • 2
    $\begingroup$ can you add a reference on this usage of QPE in combination with GA? $\endgroup$ – glS Feb 7 '19 at 10:42
  • $\begingroup$ Hi, Learner. Welcome to Quantum Computing SE! Please use MathJax for properly typesetting mathematical expressions. Go through How to write a good question?. I've edited the question on your behalf this time. $\endgroup$ – Sanchayan Dutta Feb 7 '19 at 13:32
  • $\begingroup$ The answer is free to reference any source as long as it can be used to answer to my question to prove it is true or false. $\endgroup$ – Learner Feb 7 '19 at 18:11
  • 1
    $\begingroup$ @Learner: could we ask you to provide a reference for this usage of quantum phase estimation, as applied to the Grover iterator? $\endgroup$ – Niel de Beaudrap Feb 7 '19 at 19:26
  • $\begingroup$ You can just use the Wikipedia quantum counting page at en.wikipedia.org/wiki/Quantum_counting_algorithm with the Grover operator (it is analyzed with the Grover operator on that page). $\endgroup$ – Learner Feb 7 '19 at 22:04

Your Answer

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

Browse other questions tagged or ask your own question.