Lower bound for quantum phase estimation

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 $\Omega (\log 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.

Figure 1

The quantum phase estimation algorithm in power query notation. $H$ is the Hadamard gate, $W_l^p$ a power query as in Eq. (2), and ${\mathcal{F}}_{2^T}^{-1}$ is the inverse quantum Fourier transform on $T$ qubits.

Figure 2

(Color online) The probability of measuring the state ∣2⟩ depending on $\phi$ for the algorithm depicted in Fig. 1 with $T=2$ and $T=3$.