2005 Reports

# A 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 log (1/epsilon) lower bound for the number of applications of Q^p1, Q^p2, ... This bound is tight due to a matching upper bound. We obtain the lower bound using a new technique based on frequency analysis.

## Subjects

## Files

- cucs-011-05.pdf application/pdf 156 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-011-05
- Published Here
- April 26, 2011