A Lower Bound for Quantum Phase Estimation

Abstract

The author obtains a query lower bound for quantum algorithms solving the phase estimation problem. The analysis generalizes existing lower-bound approaches to the case where the oracle Q is given by controlled powers Q(sup P) of Q, as it is for example in Shor's order-finding algorithm. In this setting, he will prove an OMEGA (log 1/epsilon) lower bound for the number of applications of Q(sup P1), Q(sup P2), etc. This bound is tight due to a matching upper bound. The author obtains the lower bound using a new technique based on frequency analysis.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 26, 2005
Accession Number
ADA437280

Entities

People

  • Arvid J. Bessen

Organizations

  • Columbia University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Air Force Research Laboratories
  • Algorithms
  • Coefficients
  • Computational Complexity
  • Computer Science
  • Computers
  • Eigenvalues
  • Eigenvectors
  • Equations
  • Frequency
  • Information Processing
  • Polynomials
  • Probability
  • Quantum Algorithms
  • Quantum Computing
  • Quantum Information

Fields of Study

  • Computer science

Readers

  • Linear Algebra
  • Nuclear and Radiation Engineering.
  • Statistical inference.

Technology Areas

  • Quantum Computing