Lower bound for quantum phase estimation
Arvid J. Bessen · Physical Review A · 2005
We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower-bound approaches to the case where the oracle $Q$ is given by controlled powers ${Q}^{p}$ of $Q$, as it is, for example, in Shor's order-finding algorithm. In this setting we will prove a $\ensuremath{\Omega}(\mathrm{log}\phantom{\rule{0.2em}{0ex}}1∕ϵ)$ lower bound for the number of applications of ${Q}^{{p}_{1}}$, ${Q}^{{p}_{2}},\dots{}$. This bound is tight due to a matching upper bound. We obtain the lower bound using a technique based on frequency analysis.