Exact quantum Fourier transforms and discrete logarithm algorithms

Details Exact quantum Fourier transforms and discrete logarithm algorithms Exact quantum Fourier transforms and discrete logarithm algorithms

2003-01-17

arxiv.org/abs/quant-ph/0301093v1

Physics

Quantum Physics

10 pages Latex

Scientific paper

We show how the quantum fast Fourier transform (QFFT) can be made exact for arbitrary orders (first for large primes). For most quantum algorithms only the quantum Fourier transform of order $2^n$ is needed, and this can be done exactly. Kitaev \cite{kitaev} showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as ``amplitude amplification''. Although unlikely to be of any practical use, this construction e.g. allows to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that ``quantum'' need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely the parameters of the gates can be calculated efficiently.

Affiliated with

Also associated with

No associations

Rating

Exact quantum Fourier transforms and discrete logarithm algorithms 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 Exact quantum Fourier transforms and discrete logarithm algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact quantum Fourier transforms and discrete logarithm algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-646611