8
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ can you add a reference on this usage of QPE in combination with GA? $\endgroup$
    – glS ♦
    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$
    – Sanchayan Dutta
    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
    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$
    – Niel de Beaudrap
    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
    Feb 7, 2019 at 22:04

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.