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:2504.20832

Approximate Quantum Fourier Transform in Logarithmic Depth on a Line

Elisa Bäumer, David Sutter, Stefan Woerner

Published Apr 29, 2025• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2504.20832

Related papers

Improved Bounds for the Approximate QFT

Donny Cheung

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.

arXiv:quant-ph/0403071•Mar 9, 2004•16 citations

T-count optimization of approximate quantum Fourier transform

Byeongyong Park, Doyeol Ahn

The quantum Fourier transform (QFT) is a ubiquitous quantum operation that is used in numerous quantum computing applications. The major obstacle to constructing a QFT circuit is that numerous elementary gates are required. Among the elementary gates, T gates dominate the cost of fault-tolerant implementation. Currently, the smallest-known T-count required to construct an n-qubit QFT circuit approximated to error O(\varepsilon) is ~8nlog_2(n/\varepsilon). Moreover, the depth of T gates (T-depth) in the approximate QFT circuit is ~2nlog_2(n/\varepsilon). This approximate QFT circuit was constructed using Toffoli gates and quantum adders. In this study, we present a new n-qubit QFT circuit approximated to error O(\varepsilon). Our approximate QFT circuit shows a T-count of ~4nlog_2(n/\varepsilon) and a T-depth of ~nlog_2(n/\varepsilon). Toffoli gates, which account for half of the T-count in the approximate QFT circuit reported in the previous study, are unnecessary in our construction. Quantum adders, which dominate the leading order term of T-depth in our approximate QFT circuit, are arranged in parallel to reduce T-depth.

arXiv:2203.07739•Mar 15, 2022•11 citations

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

Logarithmic-depth quantum state preparation of polynomials

Baptiste Claudon, Alexis Lucas, Jean-Philip Piquemal +2 more

Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree$-d$ polynomial, using circuits with logarithmic depth in the number $n$ of qubits and only $\mathcal O(n)$ ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only $n$ terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state $|1\rangle$. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using $14$ qubits and more than $500$ primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.

quant-pharXiv:2603.16527•Mar 18, 2026•4 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

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
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.
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) is a ubiquitous quantum operation that is used in numerous quantum computing applications. The major obstacle to constructing a QFT circuit is that numerous elementary gates are required. Among the elementary gates, T gates dominate the cost of fault-tolerant implementation. Currently, the smallest-known T-count required to construct an n-qubit QFT circuit approximated to error O(\varepsilon) is ~8nlog_2(n/\varepsilon). Moreover, the depth of T gates (T-depth) in the approximate QFT circuit is ~2nlog_2(n/\varepsilon). This approximate QFT circuit was constructed using Toffoli gates and quantum adders. In this study, we present a new n-qubit QFT circuit approximated to error O(\varepsilon). Our approximate QFT circuit shows a T-count of ~4nlog_2(n/\varepsilon) and a T-depth of ~nlog_2(n/\varepsilon). Toffoli gates, which account for half of the T-count in the approximate QFT circuit reported in the previous study, are unnecessary in our construction. Quantum adders, which dominate the leading order term of T-depth in our approximate QFT circuit, are arranged in parallel to reduce T-depth.
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.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d-d−d polynomial, using circuits with logarithmic depth in the number nnn of qubits and only O(n)\mathcal O(n)O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only nnn terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩|1\rangle∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 141414 qubits and more than 500500500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.
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.
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.