A Lower Bound for Quantum Phase Estimation

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.

7 pages, 1 figure

References in corpus (5)

• Strengths and Weaknesses of Quantum Computing
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Tight bounds on quantum searching
• Eigenvector Approximation Leading to Exponential Speedup of Quantum Eigenvalue Calculation
• Approximation of Various Quantum Query Types

Cited by in corpus (7)

• Near-optimal ground state preparation
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Optimal phase estimation in quantum networks
• Lower Bounds for Unitary Property Testing with Proofs and Advice
• General quantum phase estimation and calibration of a timepiece in a quantum dot system
• Quantum Lower Bounds by Sample-to-Query Lifting
• Quantum Lower Bounds by Entropy Numbers