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
    Commented Feb 7, 2019 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$ Commented Feb 7, 2019 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
    Commented Feb 7, 2019 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$ Commented Feb 7, 2019 at 19:26
  • 1
    $\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
    Commented Feb 7, 2019 at 22:04

1 Answer 1


The QPE algorithm can estimate the phase within an additive error of $\epsilon$ using $t = N + p$ qubits with $p \propto \mathcal{O}(\text{log}(1/\epsilon))$ and $\mathcal{O}(1/\epsilon)$ controlled-U operations. See Nielson & Chuang section 5.2.1 for a full derivation and analysis.


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.