EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS

DOI10.1142/S0219749904000109MaRDI QIDQ4674243zbMATHOpenAlexFDO

Authors Michele Mosca, Christof Zalka

Publication date 9 May 2005

Published in International Journal of Quantum Information (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0301093

zbMATH Keywords

exact algorithmsdiscrete logarithm problemquantum algorithmsquantum Fourier transformation

Mathematics Subject Classification ID

Quantum computation (81P68) Numerical methods for discrete and fast Fourier transforms (65T50)

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 $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.

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

• Quantum algorithms and the Fourier transform
• Quantum algorithms revisited

Cited in

(17)

• Quantum deduction rules
• Discrete quantum computation and Lagrange's four-square theorem
• Zero sum subsequences and hidden subgroups
• Quantum Fourier transform over symmetric groups -- improved result
• An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
• Inverting well conditioned matrices in quantum logspace
• Collapse of the hierarchy of constant-depth exact quantum circuits
• Quantum arithmetic with the quantum Fourier transform
• Integer numeric multiplication using quantum Fourier transform
• A generalization of Bernstein-Vazirani algorithm with multiple secret keys and a probabilistic oracle
• Uniformity of quantum circuit families for error-free algorithms
• Photonic scheme of quantum phase estimation for quantum algorithms via quantum dots
• Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
• Quantum algorithms for algebraic problems
• A quantum computing primer for operator theorists
• Approximation of a quantum algorithm for order finding
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs

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)