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:quant-ph/0703211 · Physical Review A

Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures

Dmitri A Maslov

Published Nov 15, 2007• 83 citations
arXivHTMLPDF

Abstract

In this paper, we investigate how quantum architectures affect the efficiency of the execution of the quantum Fourier transform (QFT) and linear transformations, which are essential parts of the stabilizer and Clifford group circuits. In particular, we show that in most common and realistic physical architectures including the linear nearest neighbor, two-dimensional lattice, and bounded degree graph (containing a chain of length $n$), $n$-qubit QFT and $n$-qubit stabilizer circuits can be parallelized to linear depth using no auxiliary qubits. We construct lower bounds that show the efficiency of our approach.

DOI
10.1103/physreva.76.052310

Related papers

The quantum Fourier transform on a linear nearest neighbor architecture

Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta

We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are $O(n)$ and $O(n\log n)$, respectively, where $n$ is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.

Quantum Information and Computation•May 1, 2007•36 citations

Reducing T-count and T-depth in approximate quantum Fourier transform circuits

Byeongyong Park, Doyeol Ahn

The quantum Fourier transform (QFT) is a fundamental component in various quantum algorithms, including Shor's factoring algorithm and the Harrow-Hassidim-Lloyd (HHL) algorithm for solving systems of linear equations. Efficient implementation of the QFT is essential for the practical realization of large-scale quantum algorithms, especially in fault-tolerant quantum computing. In fault-tolerant implementations, the Clifford + T gate library is the standard choice for building quantum circuits. As the most resource-intensive component within this framework, the T gate's associated cost poses a significant challenge to the efficient implementation of the QFT and its dependent algorithms. While approximate QFT (AQFT) circuits reduce this cost, state-of-the-art implementations still require a T-count of [Formula: see text] and a T-depth of [Formula: see text]. Although these results represent a notable achievement, the associated resource cost remains a primary bottleneck for practical, large-scale quantum algorithms, motivating further optimization. To address this bottleneck, this paper introduces two novel [Formula: see text]-qubit AQFT circuits with an approximation error of [Formula: see text]. Our first design, AQFT Circuit 1, halves the T-count to [Formula: see text] by constructing inverse phase gradient transformation (PGT) circuits without using additional non-Clifford gates and by implementing the inverse PGTs using quantum adders. Our second design, AQFT Circuit 2, reduces the T-depth to [Formula: see text] through parallelization of the inverse PGTs that add only [Formula: see text] additional T gates. For both AQFT circuits, the state-of-the-art linear-depth quantum adder is employed. We demonstrate that employing the linear-depth quantum adder provides advantages over the currently known logarithmic-depth quantum adder, not only in terms of T-count but also in T-depth optimization for the AQFT, particularly within the range [Formula: see text], which encompasses practical system sizes.

Scientific Reports•Oct 24, 2025•1 citation

Performing the Quantum Fourier Transform in Linear Parallel Time

Cristopher Moore

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.

•Jan 1, 1998•0 citations

Quantum Fourier transform toolbox

Carli Bruinsma, Pietro M. Posta, Joppe Stokvis +2 more

Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over $\mathrm{GL}_2(F_q)$ that scale polynomially in $\log q$, rather than polynomially in $q$. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products $F\wr S_n$, whose cost depends on the cost of a QFT over $F$ and the size of its representation registers. This removes the restriction $|F|=\operatorname{poly}(n)$ required by previous generic constructions and can yield exponential improvements when $F$ itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.

quant-pharXiv:2608.28573•Aug 31, 2026•2 citations

Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs

Kamil Ravilevich Khadiev, Aliya Khadieva, Vadim Sagitov +1 more

In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. The QFT algorithm is a very popular technique used in many quantum algorithms. We present a generic method for constructing quantum circuits for this algorithm implementing on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates. These restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture of the qubit connection, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture. We compare quantum circuits built by our algorithm with existing quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, ``sun'' (a cycle with tails, presented by the 16-qubit IBMQ device) and ``two joint suns'' (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with existing optimized circuits for ``sun'' and ``two joint suns'' architectures, and a circuit with slightly more CNOT gates for the LNN architecture. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.

arXiv:2510.09824•Oct 10, 2025•0 citations

Linear depth approximate QFT with zero ancilla

Laxmidhar Biswal, Anirban Bhattacharjee, Hafizur Rahaman

The inseparable coupling of a quantum system with its environment adds noise at resonant frequencies, causing energy fluctuations and losses entanglement of the fragile quantum state, informally known as decoherence. By truncating Fourier wiggles with the fault-tolerant features, a robust quantum Fourier transform (QFT) scheme can mitigate the decoherence effect. However, a low qubit-count and circuit-depth-based quantum circuit is desirable because of decoherence rate scale up linearly with qubit-count, shortening the coherence time of a fragile quantum state. Indeed, due to the high latency of 1-qubit phase-gates, phase-depth becomes a more dominant factor in circuit-depth and pays a high price for scalability. The above issues are addressed in this manuscript by implementing a fault-tolerant approximate quantum Fourier-transform (AQFT) in linear phase-depth with zero ancillary cost and \(\mathcal {O}(n\log n)\) phase-count using the Clifford+ \(Z_N\) -group. By truncating lower rotated phase operators, a robust fault-tolerant AQFT is achieved with linear phase-depth and zero ancillary cost, as well as 75%, 87.6%, 94.22%, and 26.99% average improvements in phase-depth, phase-count, CNOT-count, and ancillary cost respectively over the present-state-of-the-arts 1 . The proposed AQFT maintains polynomially small approximation error, achieving a strong balance between accuracy and efficiency that makes it practical for most algorithms and well suited for NISQ hardware.

Scientific Reports•Aug 15, 2026•0 citations
In this paper, we investigate how quantum architectures affect the efficiency of the execution of the quantum Fourier transform (QFT) and linear transformations, which are essential parts of the stabilizer and Clifford group circuits. In particular, we show that in most common and realistic physical architectures including the linear nearest neighbor, two-dimensional lattice, and bounded degree graph (containing a chain of length nnn), nnn-qubit QFT and nnn-qubit stabilizer circuits can be parallelized to linear depth using no auxiliary qubits. We construct lower bounds that show the efficiency of our approach.
We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are O(n)O(n)O(n) and O(nlog⁡n)O(n\log n)O(nlogn), respectively, where nnn is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.
The quantum Fourier transform (QFT) is a fundamental component in various quantum algorithms, including Shor's factoring algorithm and the Harrow-Hassidim-Lloyd (HHL) algorithm for solving systems of linear equations. Efficient implementation of the QFT is essential for the practical realization of large-scale quantum algorithms, especially in fault-tolerant quantum computing. In fault-tolerant implementations, the Clifford + T gate library is the standard choice for building quantum circuits. As the most resource-intensive component within this framework, the T gate's associated cost poses a significant challenge to the efficient implementation of the QFT and its dependent algorithms. While approximate QFT (AQFT) circuits reduce this cost, state-of-the-art implementations still require a T-count of [Formula: see text] and a T-depth of [Formula: see text]. Although these results represent a notable achievement, the associated resource cost remains a primary bottleneck for practical, large-scale quantum algorithms, motivating further optimization. To address this bottleneck, this paper introduces two novel [Formula: see text]-qubit AQFT circuits with an approximation error of [Formula: see text]. Our first design, AQFT Circuit 1, halves the T-count to [Formula: see text] by constructing inverse phase gradient transformation (PGT) circuits without using additional non-Clifford gates and by implementing the inverse PGTs using quantum adders. Our second design, AQFT Circuit 2, reduces the T-depth to [Formula: see text] through parallelization of the inverse PGTs that add only [Formula: see text] additional T gates. For both AQFT circuits, the state-of-the-art linear-depth quantum adder is employed. We demonstrate that employing the linear-depth quantum adder provides advantages over the currently known logarithmic-depth quantum adder, not only in terms of T-count but also in T-depth optimization for the AQFT, particularly within the range [Formula: see text], which encompasses practical system sizes.
We exhibit a quantum circuit that performs the Quantum Fourier Transform on nnn 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.
Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over GL2(Fq)\mathrm{GL}_2(F_q)GL2​(Fq​) that scale polynomially in log⁡q\log qlogq, rather than polynomially in qqq. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products F≀SnF\wr S_nF≀Sn​, whose cost depends on the cost of a QFT over FFF and the size of its representation registers. This removes the restriction ∣F∣=poly⁡(n)|F|=\operatorname{poly}(n)∣F∣=poly(n) required by previous generic constructions and can yield exponential improvements when FFF itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.
In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. The QFT algorithm is a very popular technique used in many quantum algorithms. We present a generic method for constructing quantum circuits for this algorithm implementing on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates. These restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture of the qubit connection, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture. We compare quantum circuits built by our algorithm with existing quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, ``sun'' (a cycle with tails, presented by the 16-qubit IBMQ device) and ``two joint suns'' (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with existing optimized circuits for ``sun'' and ``two joint suns'' architectures, and a circuit with slightly more CNOT gates for the LNN architecture. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.
The inseparable coupling of a quantum system with its environment adds noise at resonant frequencies, causing energy fluctuations and losses entanglement of the fragile quantum state, informally known as decoherence. By truncating Fourier wiggles with the fault-tolerant features, a robust quantum Fourier transform (QFT) scheme can mitigate the decoherence effect. However, a low qubit-count and circuit-depth-based quantum circuit is desirable because of decoherence rate scale up linearly with qubit-count, shortening the coherence time of a fragile quantum state. Indeed, due to the high latency of 1-qubit phase-gates, phase-depth becomes a more dominant factor in circuit-depth and pays a high price for scalability. The above issues are addressed in this manuscript by implementing a fault-tolerant approximate quantum Fourier-transform (AQFT) in linear phase-depth with zero ancillary cost and O(nlog⁡n)\mathcal {O}(n\log n)O(nlogn) phase-count using the Clifford+ ZNZ_NZN​ -group. By truncating lower rotated phase operators, a robust fault-tolerant AQFT is achieved with linear phase-depth and zero ancillary cost, as well as 75%, 87.6%, 94.22%, and 26.99% average improvements in phase-depth, phase-count, CNOT-count, and ancillary cost respectively over the present-state-of-the-arts 1 . The proposed AQFT maintains polynomially small approximation error, achieving a strong balance between accuracy and efficiency that makes it practical for most algorithms and well suited for NISQ hardware.