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 \(8n{\text{log}}_{2}(n/\varepsilon )-O({\text{log}}^{2}(n/\varepsilon ))\) and a T-depth of \(n{\text{log}}_{2}(n/\varepsilon )+O(n)\) . 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 \(n\) -qubit AQFT circuits with an approximation error of \(O(\varepsilon )\) . Our first design, AQFT Circuit 1, halves the T-count to \(4n{\text{log}}_{2}(n/\varepsilon )-O({\text{log}}^{2}(n/\varepsilon ))\) 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 \(\frac{1}{2}n{\text{log}}_{2}(n/\varepsilon )+O(n)\) through parallelization of the inverse PGTs that add only \(O(n)\) 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 \(3<n/\varepsilon <{10}^{13}\) , which encompasses practical system sizes.
