Technical reports:
A Lower Bound for Quantum Phase Estimation
Arvid J. Bessen
Downloads:
- Title:
- A Lower Bound for Quantum Phase Estimation
- Author(s):
- Bessen, Arvid J.
- Date:
- 2005
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:29163
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-011-05
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- 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.
- Subject(s):
- Computer science
- Item views:
- 128