We give an algorithm for approximating the quantum Fourier transform over an arbitrary Z/sub p/ which requires only O(n log n) steps where n=log p to achieve an approximation to within an arbitrary inverse polynomial in n. This improves the method of A.Y. Kitaev (1995) which requires time quadratic in n. This algorithm also leads to a general and efficient Fourier sampling technique which improves upon the quantum Fourier sampling lemma of L. Hales and S. Hallgren (1997). As an application of this technique, we give a quantum algorithm which finds the period of an arbitrary periodic function, i.e. a function which may be many-to-one within each period. We show that this algorithm is efficient (polylogarithmic in the period of the function) for a large class of periodic functions. Moreover, using standard quantum lower-bound techniques, we show that this characterization is right. That is, this is the maximal class of periodic functions with an efficient quantum period-finding algorithm.
We isolate and generalize a technique implicit in many quantum algorithms, including Shor's algorithms for factoring and discrete log.In particular, we show that the distribution sampled after a Fourier transform over Zp can be efficiently approximated by transforming over Z, for any q in a large range.Our result places no restrictions on the superposition to be transformed, generalizing previous applications.In addition, our proof easily generalizes to multi-dimensional transforms for any constant number of dimensions.
The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.
We isolate and generalize a technique implicit in many quantum algorithms, including Shor's algorithms for factoring and discrete log. In particular, we show that the distribution sampled after a Fourier transform over
Zp can be efficiently approximated by transforming over
Zq for any q in a large range. Our result places no restrictions on the superposition to be transformed, generalizing the result implicit in Shor which applies only to periodic superpositions. In addition, our proof easily generalizes to multi-dimensional transforms for any constant number of dimensions.
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 investigate and improve algorithms for computing the approximate quantum Fourier transform (QFT ) and simulating a sparse Hamiltonian. We present an improved near-linear time algorithm for the approximate QFT modulo 2™. We give a circuit for the arbitrary modulus version that matches the best currently-known bound. We then relate the difficulty of the arbitrary modulus QFT to classical integer multiplication and division. We also investigate the problem of simulating an n-qubit sparse Hamiltonian. As input we receive the system's start state, a black box which, via queries, provides the non-zero entries of each row of the Hamiltonian, and a time t. We present an improved polynomial-time quantum algorithm for computing an approximation of the state of the system at time t. Prior to this, we provide an introduction to quantum computing, and survey some quantum algorithms that are used in our improved algorithms.
The Discrete Fourier Transform (DFT) is central to the analysis of uniformly sampled signals, yet many practical applications involve non-uniform sampling, requiring the Non-Uniform Discrete Fourier Transform (NUDFT). While quantum algorithms for the standard DFT are well established, a corresponding framework for the non-uniform case remains underdeveloped. This work introduces a quantum algorithm for the Non-Uniform Quantum Fourier Transform (NUQFT) based on a low-rank factorization of the NUDFT matrix. The factorization is translated into an explicit quantum construction using block encodings, Quantum Signal Processing, and the Linear Combination of Unitaries framework, yielding an
ε-accurate block encoding of the NUDFT matrix with controlled approximation error from both classical truncation and quantum implementation. Under standard oracle access assumptions for non-uniform sampling points, we derive explicit, non-asymptotic gate-level resource estimates. The resulting complexity scales polylogarithmically with target precision, quadratically with the number of qubits through the quantum Fourier transform, and logarithmically with a geometry-dependent conditioning parameter induced by the non-uniform grid. This establishes a concrete and resource-efficient quantum analogue of the NUDFT and provides a foundation for quantum algorithms on irregularly sampled data.