Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.04240

An exact quantum order finding algorithm and its applications

Muhammad Imran

Published May 6, 2022• 0 citations
arXivHTMLPDF

Abstract

We present an efficient exact quantum algorithm for order finding problem when a multiple $m$ of the order $r$ is known. The algorithm consists of two main ingredients. The first ingredient is the exact quantum Fourier transform proposed by Mosca and Zalka in [MZ03]. The second ingredient is an amplitude amplification version of Brassard and Hoyer in [BH97] combined with some ideas from the exact discrete logarithm procedure by Mosca and Zalka in [MZ03]. As applications, we show how the algorithm derandomizes the quantum algorithm for primality testing proposed by Donis-Vela and Garcia-Escartin in [DVGE18], and serves as a subroutine of an efficient exact quantum algorithm for finding primitive elements in arbitrary finite fields. .

DOI
10.48550/arxiv.2205.04240

Related papers

An exact quantum hidden subgroup algorithm and applications to solvable groups

Muhammad Imran, Gábor Ivanyos

We present a polynomial time exact quantum algorithm for the hidden subgroup problem in $\Z_{m^k}^n$. The algorithm uses the quantum Fourier transform modulo $m$ and does not require factorization of $m$. For smooth $m$, i.e., when the prime factors of $m$ are of size $(\log m)^{O(1)}$, the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general $m$, the algorithm of Mosca and Zalka is available. Even for $m=3$ and $k=1$ our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as $m$. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.

arXiv:2202.04047•Quantum Information and Computation•May 30, 2022•1 citation

EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS

Michele Mosca, Christof Zalka

We show how the Quantum Fast Fourier Transform (QFFT) can be made exact for arbitrary orders (first showing it for large primes). Most quantum algorithms only need a good approximation of the quantum Fourier transform of order 2n to succeed with high probability, and this QFFT can in fact be done exactly. Kitaev1 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 allows one 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 approximated efficiently.

arXiv:quant-ph/0301093•International Journal of Quantum Information•Mar 1, 2004•65 citations

Quantum probabilistic subroutines and problems in number theory

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.

arXiv:quant-ph/9907020•Physical Review A•Aug 18, 2000•11 citations

Quantum Versions of Classical Randomized Algorithms

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms a' la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the ‘prime number theorem’ and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.

Progress of Theoretical Physics Supplement•Jan 1, 2000•0 citations

Approximation of a quantum algorithm for order finding

Alexander N. Prokopenya

A quantum algorithm for the computation the order of an integer, which uses the quantum Fourier transform, is discussed. The cases of the exact and approximate Fourier transform are considered, and estimates of the probability of the successful solution of the problem that significantly improve the available results are obtained. The quantum algorithm for order finding is simulated using the QuantumCircuit package written in the computer algebra system Wolfram Mathematica , and its efficiency in combination with the approximate Fourier transform is demonstrated.

Programming and Computer Software•Mar 1, 2016•1 citation

Quantum Fourier Operators and Their Application

Eric Sakk

The application of the quantum Fourier transform (QFT) within the field of quantum computation has been manifold. Shor’s algorithm, phase estimation and computing discrete logarithms are but a few classic examples of its use. These initial blueprints for quantum algorithms have sparked a cascade of tantalizing solutions to problems considered to be intractable on a classical computer. Therefore, two main threads of research have unfolded. First, novel applications and algorithms involving the QFT are continually being developed. Second, improvements in the algorithmic complexity of the QFT are also a sought after commodity. In this work, we review the structure of the QFT and its implementation. In order to put these concepts in their proper perspective, we provide a brief overview of quantum computation. Finally, we provide a permutation structure for putting the QFT within the context of universal computation.

IntechOpen eBooks•Jan 25, 2021•3 citations
We present an efficient exact quantum algorithm for order finding problem when a multiple mmm of the order rrr is known. The algorithm consists of two main ingredients. The first ingredient is the exact quantum Fourier transform proposed by Mosca and Zalka in [MZ03]. The second ingredient is an amplitude amplification version of Brassard and Hoyer in [BH97] combined with some ideas from the exact discrete logarithm procedure by Mosca and Zalka in [MZ03]. As applications, we show how the algorithm derandomizes the quantum algorithm for primality testing proposed by Donis-Vela and Garcia-Escartin in [DVGE18], and serves as a subroutine of an efficient exact quantum algorithm for finding primitive elements in arbitrary finite fields. .
We present a polynomial time exact quantum algorithm for the hidden subgroup problem in Zmkn\Z_{m^k}^nZmkn​. The algorithm uses the quantum Fourier transform modulo mmm and does not require factorization of mmm. For smooth mmm, i.e., when the prime factors of mmm are of size (log⁡m)O(1)(\log m)^{O(1)}(logm)O(1), the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general mmm, the algorithm of Mosca and Zalka is available. Even for m=3m=3m=3 and k=1k=1k=1 our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as mmm. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.
We show how the Quantum Fast Fourier Transform (QFFT) can be made exact for arbitrary orders (first showing it for large primes). Most quantum algorithms only need a good approximation of the quantum Fourier transform of order 2n to succeed with high probability, and this QFFT can in fact be done exactly. Kitaev1 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 allows one 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 approximated efficiently.
We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.
We present a quantum version of the classical probabilistic algorithms a' la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the ‘prime number theorem’ and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.
A quantum algorithm for the computation the order of an integer, which uses the quantum Fourier transform, is discussed. The cases of the exact and approximate Fourier transform are considered, and estimates of the probability of the successful solution of the problem that significantly improve the available results are obtained. The quantum algorithm for order finding is simulated using the QuantumCircuit package written in the computer algebra system Wolfram Mathematica , and its efficiency in combination with the approximate Fourier transform is demonstrated.
The application of the quantum Fourier transform (QFT) within the field of quantum computation has been manifold. Shor’s algorithm, phase estimation and computing discrete logarithms are but a few classic examples of its use. These initial blueprints for quantum algorithms have sparked a cascade of tantalizing solutions to problems considered to be intractable on a classical computer. Therefore, two main threads of research have unfolded. First, novel applications and algorithms involving the QFT are continually being developed. Second, improvements in the algorithmic complexity of the QFT are also a sought after commodity. In this work, we review the structure of the QFT and its implementation. In order to put these concepts in their proper perspective, we provide a brief overview of quantum computation. Finally, we provide a permutation structure for putting the QFT within the context of universal computation.