A Lower Bound for Quantum Phase Estimation

Details A Lower Bound for Quantum Phase Estimation A Lower Bound for Quantum Phase Estimation

2004-12-01

arxiv.org/abs/quant-ph/0412008v2

Phys. Rev. A 71, 042313 (2005)

Physics

Quantum Physics

7 pages, 1 figure

Scientific paper

10.1103/PhysRevA.71.042313

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.

Affiliated with

Also associated with

No associations

Rating

A Lower Bound for Quantum Phase Estimation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Lower Bound for Quantum Phase Estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Lower Bound for Quantum Phase Estimation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-146959