9

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$?

Sanchayan Dutta
  • 17,497
  • 7
  • 48
  • 110
Learner
  • 336
  • 1
  • 6
  • 2
    can you add a reference on this usage of QPE in combination with GA? – glS Feb 07 '19 at 10:42
  • 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 [edit]ed the question on your behalf this time. – Sanchayan Dutta Feb 07 '19 at 13:32
  • 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. – Learner Feb 07 '19 at 18:11
  • 1
    @Learner: could we ask you to provide a reference for this usage of quantum phase estimation, as applied to the Grover iterator? – Niel de Beaudrap Feb 07 '19 at 19:26
  • 1
    You can just use the Wikipedia quantum counting page at https://en.wikipedia.org/wiki/Quantum_counting_algorithm with the Grover operator (it is analyzed with the Grover operator on that page). – Learner Feb 07 '19 at 22:04
  • I think that this question is actually reasonably clear. However, I also think that the OP shows signs of having the resources to answer the question by themselves, and to improve the quality of the question to be one of the better posts here on Grover's Algorithm. – Niel de Beaudrap Feb 09 '19 at 13:00

1 Answers1

2

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.

ryanhill1
  • 2,493
  • 1
  • 9
  • 37