EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
From MaRDI portal
Publication:4674243
DOI10.1142/S0219749904000109zbMATH Open1067.81017arXivquant-ph/0301093OpenAlexW2065276051MaRDI QIDQ4674243FDOQ4674243
Authors: Michele Mosca, Christof Zalka 
Publication date: 9 May 2005
Published in: International Journal of Quantum Information (Search for Journal in Brave)
Abstract: 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 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.
Full work available at URL: https://arxiv.org/abs/quant-ph/0301093
Recommendations
- Quantum algorithms and the Fourier transform
- Quantum arithmetic with the quantum Fourier transform
- scientific article; zbMATH DE number 2086431
- Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
- Quantum Fourier transform in computational basis
- Approximate quantum Fourier transform and quantum algorithm for phase estimation
- The universality of the quantum Fourier transform in forming the basis of quantum computing algorithms
- Paired quantum Fourier transform with \(\log_2N\) Hadamard gates
- Quantum computation of discrete logarithms in semigroups
- scientific article; zbMATH DE number 1406111
Cites Work
Cited In (17)
- Discrete quantum computation and Lagrange's four-square theorem
- Photonic scheme of quantum phase estimation for quantum algorithms via quantum dots
- Integer numeric multiplication using quantum Fourier transform
- Approximation of a quantum algorithm for order finding
- Quantum Fourier transform over symmetric groups -- improved result
- Quantum deduction rules
- Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
- Zero sum subsequences and hidden subgroups
- Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
- Uniformity of quantum circuit families for error-free algorithms
- Inverting well conditioned matrices in quantum logspace
- Collapse of the hierarchy of constant-depth exact quantum circuits
- Quantum arithmetic with the quantum Fourier transform
- An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
- A generalization of Bernstein-Vazirani algorithm with multiple secret keys and a probabilistic oracle
- A quantum computing primer for operator theorists
- Quantum algorithms for algebraic problems
This page was built for publication: EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4674243)
