An Improved Quantum Fourier Transform Algorithm and Applications

We give an algorithm for approximating the quantum Fourier transform over an arbitrary Z/sub p/ which requires only O(n log n) steps where n=log p to achieve an approximation to within an arbitrary inverse polynomial in n. This improves the method of A. Y. Kitaev (1995) which requires time quadratic in n. This algorithm also leads to a general and efficient Fourier sampling technique which improves upon the quantum Fourier sampling lemma of L. Hales and S. Hallgren (1997). As an application of this technique, we give a quantum algorithm which finds the period of an arbitrary periodic function, i. e. a function which may be many-to-one within each period. We show that this algorithm is efficient (polylogarithmic in the period of the function) for a large class of periodic functions. Moreover, using standard quantum lower-bound techniques, we show that this characterization is right. That is, this is the maximal class of periodic functions with an efficient quantum period-finding algorithm.

Authors

• Lisa Hales
• Sean Hallgren

Keywords

• Fourier transforms
• Quantum computing
• Sampling methods
• Machinery
• Application software
• Logic
• Computer science
• Polynomials
• Eigenvalues and eigenfunctions
• Multidimensional systems
• Fourier Transform
• Quantum Fourier Transform
• N Log N
• High Probability
• Denominator
• Efficient Algorithm
• Unit Vector
• Functional Class
• Correction Algorithm
• Output Of Algorithm
• Periodic Function
• Output Distribution
• Power-of-two
• Cyclic Group
• Quantum Algorithms
• Continued Fraction
• Proof Of Claim
• Greatest Common Divisor
• Hidden Problem
• Set Of Fractions
• Fractional Value