We present a polynomial time exact quantum algorithm for the hidden subgroup problem in
Zmkn. 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
(logm)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.
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.
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs
O(q2) gates (and
O(q) qubits) to perform the exact Fourier transform over
F2q. Cleve and Watrous (FOCS 2000) improved this gate count to
O(q(logq)2(loglogq)) using the integer multiplication algorithm in
O(n(logn)(loglogn)) time for two
n-bit integers (best known at that time). Our first main result shows that this gate count can be improved to
O(q(logq)). In fact, if there is a multiplication circuit, to multiply two
n-bit integers, with
O(n(logn)α) gates; we get a QFT circuit with
O(q(logq)α) gates (improving upon
O(q(logq)α+1)) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with
o(q(logq)) gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with
O(q(loglog(q/ε))α+1) gates, where
ε is the approximating parameter. Our second main result again improves this to
O(q(loglog(q/ε))α) gates.
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.