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.
The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra
Pn(d), Brauer algebra
Bn(d), and walled Brauer algebra
Br,s(d). These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms.
Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter
d is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras
A from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity
poly(n,logd,log(1/ε)) for approximating the Fourier transform to error
(d−1/2+ε)⋅poly(∣A∣). Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.
It has previously been established that the logarithmic-depth approximate quantum Fourier transform (AQFT) provides a suitable replacement for the regular QFT in many quantum algorithms. Since the AQFT is less accurate by definition, polynomially many more applications of the AQFT are required to achieve the original accuracy. However, in many quantum algorithms, the smaller size of the AQFT circuit yields a net improvement over using the QFT. This paper presents a more thorough analysis of the AQFT circuit, which leads to the surprising conclusion that for sufficiently large input sizes, the difference between the QFT and the logarithmic-depth AQFT is negligible. In effect, the AQFT can be used as an direct replacement for the QFT, yielding improvements in any application which does not require exact quantum computation.
The quantum Fourier transform (QFT) can calculate the Fourier transform of a vector of size
NN with time complexity
O(log2 N)O(log2N) as compared to the classical complexity of
O(NlogN)O(NlogN). However, if one wanted to measure the full output state, then the QFT complexity becomes
O(Nlog2 N)O(Nlog2N), thus losing its apparent advantage, indicating that the advantage is fully exploited for algorithms when only a limited number of samples is required from the output vector, as is the case in many quantum algorithms. Moreover, the computational complexity worsens if one considers the complexity of constructing the initial state. In this article, this issue is better illustrated by providing a concrete implementation of these algorithms and discussing their complexities as well as the complexity of the simulation of the QFT in matlab.
The authors introduce an efficient digital-analog quantum algorithm to compute the quantum Fourier transform, a subroutine widely employed in several relevant quantum algorithms. The paper shows that, under sensible assumptions about noise sources, the fidelity of the quantum Fourier transformation improves considerably with this approach when compared against digital quantum computing. This suggests that hybrid protocols combining digital and analog quantum computing could be a sensible approach to reach quantum advantage in the Noisy Intermediate-Scale Quantum era.
The quantum Fourier transform (QFT) brings efficiency in many respects, especially usage of resource, for most operations on quantum computers. In this study, the existing QFT-based and non-QFT-based quantum arithmetic operations are examined. The capabilities of QFT-based addition and multiplication are improved with some modifications. The proposed operations are compared with the nearest quantum arithmetic operations. Furthermore, novel QFT-based subtraction, division and exponentiation operations are presented. The proposed arithmetic operations can perform nonmodular operations on all signed numbers without any limitation by using less resources. In addition, novel quantum circuits of two’s complement, absolute value and comparison operations are also presented by using the proposed QFT-based addition and subtraction operations.