Phys. Rev. A 71, 042313 (2005) [6 pages]Lower bound for quantum phase estimationReceived 1 December 2004; published 8 April 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 Qp of Q, as it is, for example, in Shor’s order-finding algorithm. In this setting we will prove a Ω(log 1∕ϵ) lower bound for the number of applications of Qp1, Qp2,…. This bound is tight due to a matching upper bound. We obtain the lower bound using a technique based on frequency analysis. © 2005 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevA.71.042313
DOI:
10.1103/PhysRevA.71.042313
PACS:
03.67.Lx
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.