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• 0 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

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•1 citation

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•0 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•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

A log-depth in-place quantum Fourier transform that rarely needs ancillas

Gregory D. Kahanamoku–Meyer, John Blue, Thiago Bergamaschi +2 more

When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth $O(\log (n / ε))$ for tunable error parameter $ε$, uses $n$ total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit's error is bounded by $ε$ on all input states except an $O(ε)$-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions [arXiv:2403.18006], the optimistic QFT yields factoring circuits of nearly linear depth using only $2n + O(n/\log n)$ total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of $O(\log (n/ε))$ with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.

arXiv:2505.00701•May 1, 2025•0 citations

Shor's algorithm requires Fanout

Lucas Gretta, Malvika Raj Joshi

Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). In this note, we resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires the $n$-qubit Fanout operation. Formally, let $\mathsf{QFT}_q$ be the gate acting on $n = \lceil \log q \rceil$ qubits that computes the QFT under modulus $q$. It is known that any $n$-qubit $\mathsf{QFT}_q$ can be implemented in constant depth using $\mathsf{FANOUT}_n$, i.e. $\mathsf{QFT}_q \in \mathsf{QAC}^0_f$. We prove the converse by using a $\mathsf{QFT}_q$ gate to construct a state of "non-negligible felinity". Consequently, $\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}$. In the case of $q = 2^n$, such as in Shor's, we approximate $\mathsf{FANOUT}_n$ using a single $\mathsf{QFT}_{2^n}$ gate and $O(1)$ two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.

quant-pharXiv:2608.06703•Aug 10, 2026•0 citations
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.
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.
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.
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.
When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth O(log⁡(n/ε))O(\log (n / ε))O(log(n/ε)) for tunable error parameter εεε, uses nnn total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit's error is bounded by εεε on all input states except an O(ε)O(ε)O(ε)-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions [arXiv:2403.18006], the optimistic QFT yields factoring circuits of nearly linear depth using only 2n+O(n/log⁡n)2n + O(n/\log n)2n+O(n/logn) total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of O(log⁡(n/ε))O(\log (n/ε))O(log(n/ε)) with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.
Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). In this note, we resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any nnn-qubit modulus, necessarily requires the nnn-qubit Fanout operation. Formally, let QFTq\mathsf{QFT}_qQFTq​ be the gate acting on n=⌈log⁡q⌉n = \lceil \log q \rceiln=⌈logq⌉ qubits that computes the QFT under modulus qqq. It is known that any nnn-qubit QFTq\mathsf{QFT}_qQFTq​ can be implemented in constant depth using FANOUTn\mathsf{FANOUT}_nFANOUTn​, i.e. QFTq∈QACf0\mathsf{QFT}_q \in \mathsf{QAC}^0_fQFTq​∈QACf0​. We prove the converse by using a QFTq\mathsf{QFT}_qQFTq​ gate to construct a state of "non-negligible felinity". Consequently, QFTq∈QAC0  ⟺  FANOUTn∈QAC0\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}QFTq​∈QAC0⟺FANOUTn​∈QAC0. In the case of q=2nq = 2^nq=2n, such as in Shor's, we approximate FANOUTn\mathsf{FANOUT}_nFANOUTn​ using a single QFT2n\mathsf{QFT}_{2^n}QFT2n​ gate and O(1)O(1)O(1) two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.