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

Scientific Reports

Linear depth approximate QFT with zero ancilla

Laxmidhar Biswal, Anirban Bhattacharjee, Hafizur Rahaman

Published Aug 15, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1038/s41598-026-66835-0

Related papers

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

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

Phase-Fidelity-Aware Truncated Quantum Fourier Transform for Scalable Phase Estimation on NISQ Hardware

Akoramurthy B, Surendiran. B

Quantum phase estimation~(QPE) is central to numerous quantum algorithms, yet its standard implementation demands an $\calO(m^{2})$-gate quantum Fourier transform~(QFT) on $m$ control qubits-a prohibitive overhead on near-term noisy intermediate-scale quantum (NISQ) devices. We introduce the \emph{Phase-Fidelity-Aware Truncated QFT} (PFA-TQFT), a family of approximate QFT circuits parameterised by a truncation depth~$d$ that omits controlled-phase rotations below a hardware-calibrated fidelity threshold~$\eps$. Our central result establishes $\TV(P_{\varphi},P_{\varphi}^{d})\leqπ(m{-}d)/2^{d}$, showing that for $d=\calO(\log m)$ circuit size collapses from $\calO(m^{2})$ to $\calO(m\log m)$ while estimation error grows by at most $\calO(2^{-d})$. We characterise $\dstar=\Floor{\log_{2}(2π/\eps_{2q})}$ directly from native gate fidelities, demonstrating 31.3 -43.7\% at m = 30, gate-count reduction on IBM Eagle/Heron and IonQ~Aria with negligible accuracy loss. Numerical experiments on the transverse-field Ising model confirm all theoretical predictions and reveal a \emph{noise-truncation synergy}: PFA-TQFT outperforms full QFT under NISQ noise $\eps_{2q}\gtrsim 2\times10^{-3}$.

quant-pharXiv:2604.05456•Apr 8, 2026•0 citations

Synthesis Techniques for Fault-tolerant Quantum Circuit Implementation using Clifford+ Z N -group

Laxmidhar Biswal, Debjyoti Bhattacharjee, Amlan Chakrabarti +1 more

Decoherence jeopardizes the entanglement of fragile quantum states, and is among the foremost challenges towards engineering scalable quantum computers. Realizing quantum circuit implementation with small qubit count and shallow circuit depth is necessary due to the linear scaling of decoherence rate with qubit count and circuit depth. Conversely, reasonable correction of small unitary errors can be achieved by using surface codes along with a transversal gate set to protect quantum information from decoherence. In this paper, we analyze and report the upper bound of non-Clifford phase-depth for different mapping schemes and synthesis approaches. We introduce a synthesis methodology based on lookup-table (LUT) networks, wherein the Boolean logic translates into fault-tolerant quantum logic using Clifford+ Z N group with zero ancillary cost. We also present fault-tolerant synthesis techniques for k -LUT network using additional ancillary lines with exponential phase-count and unit phase-depth.

ACM Transactions on Quantum Computing•Jun 14, 2024•1 citation

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 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
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.
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.
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.
Quantum phase estimation~(QPE) is central to numerous quantum algorithms, yet its standard implementation demands an $\calO(m^{2})$-gate quantum Fourier transform~(QFT) on mmm control qubits-a prohibitive overhead on near-term noisy intermediate-scale quantum (NISQ) devices. We introduce the \emph{Phase-Fidelity-Aware Truncated QFT} (PFA-TQFT), a family of approximate QFT circuits parameterised by a truncation depth~ddd that omits controlled-phase rotations below a hardware-calibrated fidelity threshold~$\eps$. Our central result establishes $\TV(P_{\varphi},P_{\varphi}^{d})\leqπ(m{-}d)/2^{d}$, showing that for $d=\calO(\log m)$ circuit size collapses from $\calO(m^{2})$ to $\calO(m\log m)$ while estimation error grows by at most $\calO(2^{-d})$. We characterise $\dstar=\Floor{\log_{2}(2π/\eps_{2q})}$ directly from native gate fidelities, demonstrating 31.3 -43.7\% at m = 30, gate-count reduction on IBM Eagle/Heron and IonQ~Aria with negligible accuracy loss. Numerical experiments on the transverse-field Ising model confirm all theoretical predictions and reveal a \emph{noise-truncation synergy}: PFA-TQFT outperforms full QFT under NISQ noise $\eps_{2q}\gtrsim 2\times10^{-3}$.
Decoherence jeopardizes the entanglement of fragile quantum states, and is among the foremost challenges towards engineering scalable quantum computers. Realizing quantum circuit implementation with small qubit count and shallow circuit depth is necessary due to the linear scaling of decoherence rate with qubit count and circuit depth. Conversely, reasonable correction of small unitary errors can be achieved by using surface codes along with a transversal gate set to protect quantum information from decoherence. In this paper, we analyze and report the upper bound of non-Clifford phase-depth for different mapping schemes and synthesis approaches. We introduce a synthesis methodology based on lookup-table (LUT) networks, wherein the Boolean logic translates into fault-tolerant quantum logic using Clifford+ Z N group with zero ancillary cost. We also present fault-tolerant synthesis techniques for k -LUT network using additional ancillary lines with exponential phase-count and unit phase-depth.
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.
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.