Download PDF AbstractThe 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 8nlog2(n/ε)−O(log2(n/ε)) and a T-depth of nlog2(n/ε)+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(ε). Our first design, AQFT Circuit 1, halves the T-count to 4nlog2(n/ε)−O(log2(n/ε)) 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 12nlog2(n/ε)+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 3b from the QFT circuit (See Fig. 3).Fig. 3AQFT Circuit 1: n-qubit AQFT with an error of O(ε) optimized for T-count, where b=⌈log2(n/ε)⌉. This circuit is decomposed into single-qubit H and Zθ gates, and standard two-qubit CNOT gates. To improve readability, the Zθ gates are aligned vertically to represent a gate layer; this does not imply a multi-qubit control structure. Each Zθ gate layer in the blue boxes performs an inverse PGT with the help of a Z−1 gate. The effect of inserting Z−1 gates can be canceled by inserting Z gates. Note that this circuit contains (n+1) inverse PGTs and these are constructed without using additional non-Clifford gates. We implement each inverse PGT using a quantum adder from Ref.37. Since the circuit is constructed entirely from unitary gates, it is inherently reversible.Full size image(Step 4: Inverse PGT implementation using quantum adder) In Fig. 3, each θZθ gate layer in blue boxes performs an inverse PGT with the help of a Z−1 gate. The effect of inserting the Z−1 gates can be canceled by inserting Z gates. We implement each inverse PGT using a quantum adder from Ref.37.T-count and T-depth estimationIn this section, we estimate the T-count and T-depth of AQFT Circuit 1. The T-count refers to the total number of T gates. The depth of a circuit refers to the number of sequential layers of gates that cannot be executed in parallel. Based on this, the T-depth is the number of sequential layers of T gates that cannot be parallelized, effectively ignoring the depth contributed by other gate types such as Clifford gates. The T-count and T-depth estimates presented in this paper are derived from the analytical formulas developed in the following sections, not from numerical simulations on a quantum simulator.Among the inverse PGTs in Fig. 3, the 3-qubit inverse PGT does not need to be replaced by a 3-qubit quantum adder, because it only requires a single T gate. Considering this, the T gates required to construct AQFT Circuit 1 are found in four parts: (1) (n−b+3) (b+1)-qubit quantum adders, (2) One for each of the k-qubit quantum adders, where k∈{4,5,…,b}, (3) One T gate in the 3-qubit inverse PGT, (4) T gates for preparing the special state |ψb+1⟩. The t-qubit quantum adder in Ref.37 requires a T-count of (4t−4) and a T-depth of t. With the quantum adder, the T-count and T-depth in part (1) are 4nb−4b2+12b and nb+n−b2+2b+3, respectively. The T-count and T-depth in part (2) are ∑k=4b(4k−4)=2b2−2b−12 and ∑k=4bk=b2/2+b/2−6, respectively. For part (4), (b−2) Zθ gates have to be synthesized with an error of ε/b for each gate (See Supplementary Material). The value ε/b is chosen so that AQFT Circuit 1 has an approximation error of O(ε). In the gate synthesis, we use RUS circuits from Ref.53, and the expected T-count to synthesize a Zθ gate with a Fourier angle with an error of ε′ is 1.08log2(1/ε′)+17.5. Therefore, the total T-count for AQFT Circuit 1 is4nb−2b2+b{1.08log2(bε)+27.5}−2.16log2(bε)−45=4nb−O(b2) (2) and the total T-depth for AQFT Circuit 1 isnb+n−12b2+52b+1.08log2(bε)+15.5=nb+n−O(b2) (3) Approximation error analysisThe approximation error, defined as the spectral norm54, can be found in the Supplementary Material. We demonstrate that AQFT Circuit 1 has an error of O(ε) when implemented in replacement of a QFT circuit. The approximation error in AQFT Circuit 1 arises from two sources: (1) Removing all the Z−1/2k gates with k>b, (2) Approximating Zθ gates to prepare the special state |ψb+1⟩ using RUS circuits. We call the error from part (1) ε1(1) and the error from part (2) ε1(2).The error for removing a Zθ gate ismax|ψ⟩‖(I−Zθ)|ψ⟩‖ (4) and this can be rewritten as2(1−cosθπ)=2|sin(πθ/2)|<|πθ| (5) since(I−Zθ)†(I−Zθ)=(0002(1−cosθπ)) (6) Therefore, the error ε1(1) is bounded as follows:ε1(1)≤(n−b)∙∑j=b+1nπ2jb from the QFT circuit (See Fig. 5). In the approximation process, we no longer need (n−1) ancilla qubits; instead, we only need b ancilla qubits.Fig. 5AQFT Circuit 2: n-qubit AQFT with an error of O(ε) optimized for T-depth, where b=⌈log2(n/ε)⌉. This circuit employs b ancilla qubits each of which is labeled as ai and initially in the state |0⟩. Each Zθ gate layer in the blue boxes performs an inverse PGT with the help of a Z−1 gate. The effect of inserting Z−1 gates can be canceled by inserting Z gates. Note that this circuit contains (n+1) inverse PGTs, and each yellow box contains only two T gates. We implement each inverse PGT using a quantum adder from Ref.37.Full size image(Step 4: Inverse PGT implementation using quantum adder) In Fig. 5, each Zθ gate layer in blue boxes performs an inverse PGT with the help of a Z−1 gate. The effect of inserting the Z−1 gates can be canceled by inserting Z gates. We implement each inverse PGT using a quantum adder from Ref.37.In the construction of AQFT Circuit 2, we utilize the linear-depth quantum adder described in Ref.37. While one might argue that employing a logarithmic-depth quantum adder could further reduce the T-depth in the AQFT circuit, our findings indicate that the quantum adder from Ref.37 is more efficient in terms of T-depth compared to the currently known logarithmic-depth quantum adder when utilized for AQFT implementation within the range 3b, (2) Approximating Zθ gates to prepare two of the special states |ψb+1⟩ using RUS circuits. We call the error from part (1) ε2(1) and the error from part (2) ε2(2).The error ε2(1) is bounded in the same way as ε1(1). When synthesizing Zθ gates to prepare two of the special states |ψb+1⟩ for AQFT Circuit 2, each Zθ gate is approximated with an error of ε/2b, resulting in ε2(2)≤2(b−2)∙ε2b<ε. Consequently, the total error implementing AQFT Circuit 2 instead of the QFT circuit is O(ε).Disadvantages of using logarithmic-depth quantum addersIf logarithmic-depth quantum adders were applied in the configuration of the circuit shown in Fig. 5, the T-depth of the AQFT circuit would be reduced from O(nlog(n/ε)) to O(nlog(log(n/ε))) at the expense of increasing the T-count. In this section, we compare the results of using the state-of-the-art logarithmic-depth quantum adder (In-FT-QCLA1 from Ref.38) with those of AQFT Circuit 2. Our analysis demonstrates that AQFT Circuit 2 is advantageous not only in terms of T-count but also T-depth. We refer to the AQFT circuit that uses the logarithmic-depth quantum adder in the configuration in Fig. 5 as AQFT Circuit 2’.First, we present the T-count and T-depth of AQFT Circuit 2’. As for AQFT Circuit 2, the T gates required to construct AQFT Circuit 2’ are categorized in five parts: (1) (n−b+3) (b+1)-qubit quantum adders, (2) One for each of the k-qubit quantum adders, where k∈{4,5,…,b}, (3) One T gate in the 3-qubit inverse PGT, (4) (n−1) T gates in yellow boxes in Fig. 5, (5) T gates for preparing two of the special states |ψb+1⟩. The t-qubit quantum adder (In-FT-QCLA1 from Ref.38) requires a T-count of 20t−8w(t)−8w(t−1)−4⌊log2(t)⌋−4⌊log2(t−1)⌋−8, where w(t)=t−∑⌊t/2i⌋i=1∞ represents the number of ones in the binary expansion of t, and a T-depth of 2⌊log2(t)⌋+2⌊log2(t−1)⌋+2⌊log2(t/3)⌋+2⌊log2((t−1)/3)⌋+28. For readability, we use the following notations:TCadder(t)=20t−8w(t)−8w(t−1)−4⌊log2(t)⌋−4⌊log2(t−1)⌋−8,TDadder(t)=2⌊log2(t)⌋+2⌊log2(t−1)⌋+2⌊log2(t/3)⌋+2⌊log2((t−1)/3)⌋+28 (11) In the following resource estimation, for the sake of convenience in calculation, we assume that n is even and b is odd. Even without this assumption, however, the difference in resource calculation is only O(1). Then, the T-count and T-depth in part (1) are (n−b+3)∙TCadder(b) and {2+n−b+12}∙TDadder(b), respectively. The T-count and T-depth in part (2) are ∑i=4b−1TCadder(i) and ∑i=2(b−1)/2TDadder(2i), respectively. For T gates in part (5), 2(b−2) Zθ gates have to be synthesized with an error of ε/2b for each gate. The value ε/2b is chosen to ensure that AQFT Circuit 2’ has an approximation error of O(ε). Therefore, the total T-count for AQFT Circuit 2’ is(n−b+3)∙TCadder(b)+∑i=4b−1TCadder(i)+n+b(2.16log2(2bε)+35)−4.32log2(2bε)−70=20nb+O(n) (12) and the total T-depth for AQFT Circuit 2’ is{n−b+52}∙TDadder(b)+∑i=2b−12TDadder(2i)+n+1.08log2(2bε)+17.5=4nlog2(b)+O(n) (13) Comparing AQFT Circuit 2’ with AQFT Circuit 2, the T-depth appears to be reduced at the expense of an increased T-count. However, within the range of 312nb holds, indicating that the T-depth is not reduced. This can be observed in Fig. 6. In summary, using the linear-depth adder from Ref.37 for AQFT implementation offers advantages over the state-of-the-art logarithmic-depth quantum adder from Ref.38 in terms of both T-count and T-depth.Fig. 6Comparison of T-depth for n-qubit AQFT implementations. In the figure, the blue solid lines represent the results from AQFT Circuit 2’ using the logarithmic-depth quantum adder from Ref.38, and the red dash-dot lines represent the results from AQFT Circuit 2 using the linear-depth quantum adder from Ref.37. The results here are derived from the analytical formulas, not from a numerical simulation on a quantum simulator. (a) ε=1/10. (b) ε=1/100. (c) ε=1/1000. (d) ε=1/10000.Full size imageResults and discussionIn this paper, we introduced two novel n-qubit AQFT circuits with an approximation error of O(ε): AQFT Circuit 1 for T-count optimization and AQFT Circuit 2 for T-depth optimization. AQFT Circuit 1 is designed to minimize T-count, achieving a T-count of 4nlog2(n/ε)−O(log2(n/ε)), which is roughly half of the best-known result in Ref.51. This reduction is accomplished by constructing inverse PGT circuits without using Toffoli gates and by replacing them with quantum adders from Ref.37. On the other hand, AQFT Circuit 2 is designed to minimize T-depth, reducing it from nlog2(n/ε)+O(n) to 12nlog2(n/ε)+O(n). This is achieved by pairing and parallelizing inverse PGTs using O(n) additional T gates. These results are summarized in Table 1.As shown in Fig. 7, AQFT Circuit 1 is optimized for T-count, while AQFT Circuit 2 is optimized for T-depth. In terms of T-count, the difference between AQFT Circuit 1 and AQFT Circuit 2 is only O(n), which does not affect the leading order term 4nlog2(n/ε). Consequently, the difference between them in Fig. 7a is subtle. However, AQFT Circuit 2 has the disadvantage of requiring O(log(n/ε)) more qubits than AQFT Circuit 1 (See Fig. 1). This additional resource requirement might be a limitation in scenarios with stringent hardware constraints.Fig. 7Comparison of T-count and T-depth for n-qubit AQFT implementations with a fixed ε=1/100. In the figure, the blue solid lines represent the results from Ref.51, the green dash-dot lines represent the results of AQFT Circuit 1, and the red dashed lines represent the results of AQFT Circuit 2. The results here are derived from the analytical formulas, not from a numerical simulation on a quantum simulator. (a) T-count comparison. The difference in T-count between AQFT Circuit 1 and AQFT Circuit 2 is only O(n), which does not affect the leading order term 4nlog2(n/ε). Consequently, the difference between them is subtle. (b) T-depth comparison.Full size imageTable 1 Comparison of T-count and T-depth for n-qubit AQFT implementations with an approximation error of O(ε), where b=⌈log2(n/ε)⌉. For the sake of convenience in calculation, we assume that n is even and b is odd. Even without this assumption, the difference in resource calculation is only O(1).Full size tableConclusionIn conclusion, this work successfully reduces the T gate cost of AQFTs by introducing two novel circuit designs. Our first circuit halves the T-count of the previous state-of-the-art by eliminating the need for additional non-Clifford gates in the PGT construction. Our second circuit similarly halves the T-depth through parallelization at the cost of additional ancilla qubits.Despite these advancements, certain limitations remain. Both AQFT circuits still exhibit a leading-order complexity of O(nlog2(n/ε)) for T-count and T-depth. Although employing logarithmic-depth quantum adders could theoretically further improve T-depth complexity, our analysis reveals that existing logarithmic-depth quantum adders do not yet offer practical advantages due to their inherently higher T-count and T-depth. Thus, future research should prioritize the development of novel logarithmic-depth quantum adders capable of reducing both T-count and T-depth simultaneously.Nevertheless, our results achieve meaningful reductions in T-count and T-depth for AQFT implementations. Considering that T gates constitute the primary bottleneck in the implementation of fault-tolerant quantum algorithms, and that QFT is ubiquitous in quantum computing, our proposed circuits represent a valuable contribution toward improving the practical feasibility of large-scale quantum algorithms, including Shor’s factoring and the HHL algorithm. Data availability The data generated during the current study are available from the corresponding author on reasonable request. ReferencesKitaev, Y. Quantum measurements and the Abelian stabilizer problem. https://arxiv.org/abs/quant-ph/9511026 (1995).Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science 124–134 (IEEE, 1994).Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009).Article ADS MathSciNet PubMed Google Scholar Brassard, G., Hoyer, P., Mosca, M. & Tapp, A. Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002).Article MathSciNet Google Scholar Draper, T. G. Addition on a quantum computer. https://arxiv.org/abs/quant-ph/0008033 (2000).Ruiz-Perez, L. & Garcia-Escartin, J. C. Quantum arithmetic with the quantum Fourier transform. Quantum Inf. Process. 16, 1–14 (2017).Article MathSciNet Google Scholar Şahin, E. Quantum arithmetic operations based on quantum Fourier transform on signed integers. Int. J. Quantum Inform. 18, 2050035 (2020).Article ADS MathSciNet Google Scholar Pavlidis, A. & Floratos, E. Quantum-Fourier-transform-based quantum arithmetic with qudits. Phys. Rev. A 103, 032417 (2021).Article ADS MathSciNet CAS Google Scholar Da-Zu, H., Zhi-Gang, C. & Ying, G. Multiparty quantum secret sharing using quantum Fourier transform. Commun. Theor. Phys. 51, 221 (2009).Article ADS MathSciNet Google Scholar Yang, Y.-G., Xia, J., Jia, X. & Zhang, H. Novel image encryption/decryption based on quantum Fourier transform and double phase encoding. Quantum Inf. Process. 12, 3477–3493 (2013).Article ADS MathSciNet Google Scholar Yang, Y.-G., Jia, X., Sun, S.-J. & Pan, Q.-X. Quantum cryptographic algorithm for color images using quantum Fourier transform and double random-phase encoding. Inf. Sci. 277, 445–457 (2014).Article Google Scholar Zhang, W.-W., Gao, F., Liu, B., Wen, Q.-Y. & Chen, H. A watermark strategy for quantum images based on quantum Fourier transform. Quantum Inf. Process. 12, 793–803 (2013).Article ADS MathSciNet Google Scholar Yang, H.-Y. & Ye, T.-Y. Secure multi-party quantum summation based on quantum Fourier transform. Quantum Inf. Process. 17, 129 (2018).Article ADS MathSciNet CAS Google Scholar Tan, R.-C., Lei, T., Zhao, Q.-M., Gong, L.-H. & Zhou, Z.-H. Quantum color image encryption algorithm based on a hyper-chaotic system and quantum Fourier transform. Int. J. Theor. Phys. 55, 5368–5384 (2016).Article Google Scholar Yin, H., Lu, D. & Zhang, R. Quantum windowed Fourier transform and its application to quantum signal processing. Int. J. Theor. Phys. 60, 3896–3918 (2021).Article MathSciNet Google Scholar Vorobyov, V. et al. Quantum Fourier transform for nanoscale quantum sensing. npj Quantum Inf. 7, 124 (2021).Article ADS Google Scholar Abrams, D. S. & Lloyd, S. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Phys. Rev. Lett. 83, 5162–5165 (1999).Article ADS CAS Google Scholar Lidar, D. A. & Wang, H. Calculating the thermal rate constant with exponential speedup on a quantum computer. Phys. Rev. E 59, 2429–2438 (1999).Article ADS CAS Google Scholar Aspuru-Guzik, A., Dutoi, A. D., Love, P. J. & Head-Gordon, M. Simulated quantum computation of molecular energies. Science 309, 1704–1707 (2005).Article ADS CAS PubMed Google Scholar Kassal, I., Whitfield, J. D., Perdomo-Ortiz, A., Yung, M.-H. & Aspuru-Guzik, A. Simulating chemistry using quantum computers. Annu. Rev. Phys. Chem. 62, 185–207 (2011).Article ADS CAS PubMed Google Scholar Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum principal component analysis. Nat. Phys. 10, 631–633 (2014).Article CAS Google Scholar Rebentrost, P., Mohseni, M. & Lloyd, S. Quantum support vector machine for big data classification. Phys. Rev. Lett. 113, 130503 (2014).Article ADS PubMed Google Scholar Wiebe, N., Braun, D. & Lloyd, S. Quantum algorithm for data fitting. Phys. Rev. Lett. 109, 050505 (2012).Article ADS PubMed Google Scholar Schuld, M., Sinayskiy, I. & Petruccione, F. Prediction by linear regression on a quantum computer. Phys. Rev. A 94, 022342 (2016).Article ADS Google Scholar Kerenidis, I. & Prakash, A. Quantum gradient descent for linear systems and least squares. Phys. Rev. A 101, 022316 (2020).Article ADS MathSciNet CAS Google Scholar Rebentrost, P., Gupt, B. & Bromley, T. R. Quantum computational finance: Monte Carlo pricing of financial derivatives. Phys. Rev. A 98, 022321 (2018).Article ADS CAS Google Scholar Woerner, S. & Egger, D. J. Quantum risk analysis.
Npj Quantum Inf. 5, 15 (2019).Article ADS Google Scholar Stamatopoulos, N. et al. Option pricing using quantum computers. Quantum 4, 291 (2020).Article Google Scholar Steijl, R. & Barakos, G. N. Parallel evaluation of quantum algorithms for computational fluid dynamics. Comput. Fluids 173, 22–28 (2018).Article MathSciNet Google Scholar Gaitan, F. Finding flows of a Navier-Stokes fluid through quantum computing. npj Quantum Inf. 6, 61 (2020).Article ADS Google Scholar Meng, Z. & Yang, Y. Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation. Phys. Rev. Res. 5, 033182 (2023).Article CAS Google Scholar Noorallahzadeh, M., Mosleh, M., Ahmadpour, S., Pal, J. & Sen, B. A new design of parity preserving reversible Vedic multiplier targeting emerging quantum circuits. Int. J. Numer. Modell. 36, e3089 (2023).Article Google Scholar Noorallahzadeh, M., Mosleh, M., Misra, N. K. & Mehranzadeh, A. A novel design of reversible quantum multiplier based on multiple-control toffoli synthesis. Quantum Inf. Process. 22, 167 (2023).Article ADS MathSciNet Google Scholar Ahmadpour, S.-S. et al. A new energy-efficient design for quantum-based multiplier for nano-scale devices in internet of things. Comput. Electr. Eng. 117, 109263 (2024).Article Google Scholar Noorallahzadeh, M., Mosleh, M. & Datta, K. A new design of parity-preserving reversible multipliers based on multiple-control toffoli synthesis targeting emerging quantum circuits. Front. Comput. Sci. 18, 186908 (2024).Article Google Scholar Noorallahzadeh, M. & Mosleh, M. Synthesis of a reversible quantum Vedic multiplier on IBM quantum computers. Sci. Rep. 15, 18897 (2025).Article ADS CAS PubMed PubMed Central Google Scholar Gidney, C. Halving the cost of quantum addition. Quantum 2, 74 (2018).Article Google Scholar Thapliyal, H., Muñoz-Coreas, E. & Khalus, V. Quantum circuit designs of carry lookahead adder optimized for T-count T-depth and qubits. Sust. Comput. 29, 100457 (2021).
Google Scholar Campbell, E. T., Terhal, B. M. & Vuillot, C. Roads towards fault-tolerant universal quantum computation. Nature 549, 172–179 (2017).Article ADS CAS PubMed Google Scholar Fowler, A. G., Mariantoni, M., Martinis, J. M. & Cleland, A. N. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012).Article ADS Google Scholar Knill, E. Fault-tolerant postselected quantum computation: schemes. https://arxiv.org/abs/quant-ph/0402171 (2004).Bravyi, S. & Kitaev, A. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316 (2005).Article ADS MathSciNet Google Scholar Aliferis, P., Gottesman, D. & Preskill, J. Quantum accuracy threshold for concatenated distance-3 codes. Quantum Inform. Comput. 6, 97–165 (2006).MathSciNet Google Scholar Fowler, A. G., Stephens, A. M. & Groszkowski, P. High-threshold universal quantum computation on the surface code. Phys. Rev. A 80, 052312 (2009).Article ADS Google Scholar Barenco, A., Ekert, A., Suominen, K.-A. & Törmä, P. Approximate quantum Fourier transform and decoherence. Phys. Rev. A 54, 139–146 (1996).Article ADS MathSciNet CAS PubMed Google Scholar Coppersmith, D. An approximate Fourier transform useful in quantum factoring. https://arxiv.org/abs/quant-ph/0201067 (2002).Nam, Y. S. & Blümel, R. Performance scaling of Shor’s algorithm with a banded quantum Fourier transform. Phys. Rev. A 86, 044303 (2012).Article ADS Google Scholar Nam, Y. S. & Blümel, R. Scaling laws for Shor’s algorithm with a banded quantum Fourier transform. Phys. Rev. A 87, 032333 (2013).Article ADS Google Scholar Griffiths, R. B. & Niu, C.-S. Semiclassical Fourier transform for quantum computation. Phys. Rev. Lett. 76, 3228 (1996).Article ADS CAS PubMed Google Scholar Goto, H. Resource requirements for a fault-tolerant quantum Fourier transform. Phys. Rev. A 90, 052318 (2014).Article ADS Google Scholar Nam, Y., Su, Y. & Maslov, D. Approximate quantum Fourier transform with O(nlog(n)) T gates. npj Quantum Inf. 6, 26 (2020).Article ADS Google Scholar Kitaev, A. Y., Shen, A. & Vyalyi, M. N. Classical and Quantum Computation (American Mathematical Society, 2002).Book Google Scholar Bocharov, A., Roetteler, M. & Svore, K. M. Efficient synthesis of universal repeat-until-success quantum circuits. Phys. Rev. Lett. 114, 080502 (2015).Article ADS PubMed Google Scholar Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information (Cambridge University Press, 2010).
Google Scholar Download referencesAcknowledgementsThe authors thank Sangkyu Baek for his valuable comments.FundingThis research was funded by Korea National Research Foundation (NRF) grant No. NRF-2023R1A2C1003570, RS-2023-00225385, RS-2024-00422330, AFOSR grant FA2386-21-1-0089, AFOSR grant FA2386-22-1-4052, and Amazon Web Services. This work was also supported by the National Quantum Laboratory at the University of Maryland (QLab).Author informationAuthors and AffiliationsDepartment of Electrical and Computer Engineering and Center for Quantum Information Processing, University of Seoul, 163 Seoulsiripdae-Ro, Dongdaemun-Gu, Seoul, 02504, Republic of KoreaByeongyong Park & Doyeol AhnSingularity Quantum Inc, 9506 Villa Isle Drive, Villa Park, CA, 92861, USAByeongyong Park & Doyeol AhnAuthorsByeongyong ParkView author publicationsSearch author on:PubMed Google ScholarDoyeol AhnView author publicationsSearch author on:PubMed Google ScholarContributionsB. P. developed the main idea, conducted the theoretical analysis, prepared the figures, and drafted the manuscript under the supervision of D. A. All authors reviewed the manuscript.Corresponding authorCorrespondence to Doyeol Ahn.Ethics declarations Competing interests The authors declare no competing interests. Additional informationPublisher’s noteSpringer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.Supplementary InformationSupplementary Information.Rights and permissions Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. Reprints and permissionsAbout this articleCite this articlePark, B., Ahn, D. Reducing T-count and T-depth in approximate quantum Fourier transform circuits. Sci Rep 15, 37199 (2025). https://doi.org/10.1038/s41598-025-21087-2Download citationReceived: 22 May 2025Accepted: 18 September 2025Published: 24 October 2025Version of record: 24 October 2025DOI: https://doi.org/10.1038/s41598-025-21087-2Share this articleAnyone you share the following link with will be able to read this content:Get shareable linkSorry, a shareable link is not currently available for this article.
