A Lower Bound for Quantum Phase Estimation
| dc.creator | Bessen, Arvid J. | |
| dc.date | 2004-12-01 | |
| dc.date | 2005-01-26 | |
| dc.date.accessioned | 2026-07-07T06:24:01Z | |
| dc.date.available | 2026-07-07T06:24:01Z | |
| dc.description | 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. | |
| dc.description | 7 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0412008 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0412008 | |
| dc.identifier | Phys. Rev. A 71, 042313 (2005) | |
| dc.identifier | doi:10.1103/PhysRevA.71.042313 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/96407 | |
| dc.subject | Quantum Physics | |
| dc.title | A Lower Bound for Quantum Phase Estimation | |
| dc.type | text |