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

Performing the Quantum Fourier Transform in Linear Parallel Time

Cristopher Moore

Published Jan 1, 1998• 0 citations
OpenAlex

Abstract

We exhibit a quantum circuit that performs the Quantum Fourier Transform on $n$ qubits in $ (n)$ depth. Thus, a parallel quantum computer can carry out the QFT in linear time. We conjecture that this can, in fact, be reduced to $ ({\rm log} n)$ depth, which would place the QFT in the class {\bf QNC} of problems solvable in logarithmic parallel time.

Related papers

Some Notes on Parallel Quantum Computation

Cristopher Moore, Martin Nilsson

We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we exhibit a simple quantum circuit related to it that we believe cannot be parallelized to less than linear depth, and therefore might be used to prove that QNC < QP.

arXiv:quant-ph/9804034•Apr 14, 1998•3 citations

Parallel Quantum Computation and Quantum Codes

Cristopher Moore, Martin Nilsson

We study the class QNC of efficient parallel quantum circuits, the quantum analog of NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic depth, including circuits for encoding and decoding standard quantum error-correcting codes, or, more generally, any circuit consisting of controlled-not gates, controlled $\pi$-shifts, and Hadamard gates. Finally, while we note the exact quantum Fourier transform can be parallelized to linear depth, we conjecture that neither itnor a simpler "staircase" circuit can be parallelized to less than this.

SIAM Journal on Computing•Jan 1, 2001•172 citations

Parallel Quantum Computation and Quantum Codes

Cristopher Moore, Martin Nilsson

We propose a definition of QNC, the quantum analog of the efficient parallel class NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic depth, including circuits for encoding and decoding standard quantum error-correcting codes, or more generally any circuit consisting of controlled-not gates, controlled pi-shifts, and Hadamard gates. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we conjecture that an even simpler `staircase' circuit cannot be parallelized to less than linear depth, and might be used to prove that QNC < QP.

arXiv:quant-ph/9808027•Aug 17, 1998•16 citations

Fast parallel circuits for the quantum Fourier transform

Richard Cleve, John Watrous

We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n+log log(1//spl epsiv/)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2/sup n/ with error bounded by /spl epsiv/. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log(n//spl epsiv/)). As an application of this depth bound, we show that P. Shor's (1997) factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial size, in combination with classical polynomial-time pre- and postprocessing. Next, we prove an /spl Omega/(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically tight (for a reasonable range of values of /spl epsiv/). We also give an upper bound of O(n(log n)/sup 2/ log log n) on the circuit size of the exact QFT modulo 2/sup n/, for which the best previous bound was O(n/sup 2/). Finally, based on our circuits for the QFT with power-of-2 moduli, we show that the QFT with respect to an arbitrary modulus m can be approximated with accuracy /spl epsiv/ with circuits of depth O((log log m)(log log 1//spl epsiv/)) and size polynomial in log m+log(1//spl epsiv/).

arXiv:quant-ph/0006004•Annual Symposium on Foundations of Computer Science•Nov 7, 2002•220 citations

Approximate Quantum Fourier Transform in Logarithmic Depth on a Line

Elisa Bäumer, David Sutter, Stefan Woerner

The approximate quantum Fourier transform (AQFT) on $n$ qubits can be implemented in logarithmic depth using $8n$ qubits with all-to-all connectivity, as shown in [Hales, PhD Thesis Berkeley, 2002]. However, realizing the required all-to-all connectivity can be challenging in practice. In this work, we use dynamic circuits, i.e., mid-circuit measurements and feed-forward operations, to implement the AQFT in logarithmic depth using only $4n$ qubits arranged on a line with nearest-neighbor connectivity. Furthermore, for states with a specific structure, the number of qubits can be further reduced to $2n$ while keeping the logarithmic depth and line connectivity. As part of our construction, we introduce a new implementation of an adder with logarithmic depth on a line, which allows us to improve the AQFT construction of Hales.

arXiv:2504.20832•Apr 29, 2025•0 citations

A review on quantum Fourier transform

Tomás Barros, Pablo Álvarez, Bárbara Vidal +1 more

This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.

Quantum Information Processing•Jan 27, 2026•2 citations
We exhibit a quantum circuit that performs the Quantum Fourier Transform on nnn qubits in (n) (n)(n) depth. Thus, a parallel quantum computer can carry out the QFT in linear time. We conjecture that this can, in fact, be reduced to (logn) ({\rm log} n)(logn) depth, which would place the QFT in the class {\bf QNC} of problems solvable in logarithmic parallel time.
We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we exhibit a simple quantum circuit related to it that we believe cannot be parallelized to less than linear depth, and therefore might be used to prove that QNC < QP.
We study the class QNC of efficient parallel quantum circuits, the quantum analog of NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic depth, including circuits for encoding and decoding standard quantum error-correcting codes, or, more generally, any circuit consisting of controlled-not gates, controlled π\piπ-shifts, and Hadamard gates. Finally, while we note the exact quantum Fourier transform can be parallelized to linear depth, we conjecture that neither itnor a simpler "staircase" circuit can be parallelized to less than this.
We propose a definition of QNC, the quantum analog of the efficient parallel class NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic depth, including circuits for encoding and decoding standard quantum error-correcting codes, or more generally any circuit consisting of controlled-not gates, controlled pi-shifts, and Hadamard gates. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we conjecture that an even simpler `staircase' circuit cannot be parallelized to less than linear depth, and might be used to prove that QNC < QP.
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n+log log(1//spl epsiv/)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2/sup n/ with error bounded by /spl epsiv/. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log(n//spl epsiv/)). As an application of this depth bound, we show that P. Shor's (1997) factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial size, in combination with classical polynomial-time pre- and postprocessing. Next, we prove an /spl Omega/(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically tight (for a reasonable range of values of /spl epsiv/). We also give an upper bound of O(n(log n)/sup 2/ log log n) on the circuit size of the exact QFT modulo 2/sup n/, for which the best previous bound was O(n/sup 2/). Finally, based on our circuits for the QFT with power-of-2 moduli, we show that the QFT with respect to an arbitrary modulus m can be approximated with accuracy /spl epsiv/ with circuits of depth O((log log m)(log log 1//spl epsiv/)) and size polynomial in log m+log(1//spl epsiv/).
The approximate quantum Fourier transform (AQFT) on nnn qubits can be implemented in logarithmic depth using 8n8n8n qubits with all-to-all connectivity, as shown in [Hales, PhD Thesis Berkeley, 2002]. However, realizing the required all-to-all connectivity can be challenging in practice. In this work, we use dynamic circuits, i.e., mid-circuit measurements and feed-forward operations, to implement the AQFT in logarithmic depth using only 4n4n4n qubits arranged on a line with nearest-neighbor connectivity. Furthermore, for states with a specific structure, the number of qubits can be further reduced to 2n2n2n while keeping the logarithmic depth and line connectivity. As part of our construction, we introduce a new implementation of an adder with logarithmic depth on a line, which allows us to improve the AQFT construction of Hales.
This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.