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

A Faster Quantum Fourier Transform

Shah, Ronit

Published Jan 19, 2025• 0 citations
arXivHTMLPDF

Abstract

We present an asymptotically improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. Historically, the approximate QFT has been implemented in $Θ(n \log n)$ gates, and the exact in $Θ(n^2)$ gates. In this work, we show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits. Specifically, our approach yields an $Θ(n(\log \log n)^2)$ algorithm for the approximate QFT using $Θ(\log n)$ ancillas, and an $Θ(n(\log n)^2)$ algorithm for the exact QFT requiring $Θ(n)$ ancillas.

DOI
10.48550/arxiv.2501.12414

Related papers

A Quantum Bluestein's Algorithm for Arbitrary-Size Quantum Fourier Transform

Nan-Hong Kuo, Renata Wong

We propose a quantum analogue of Bluestein's algorithm (QBA) that implements an exact $N$-point Quantum Fourier Transform (QFT) for arbitrary $N$. Our construction factors the $N$-dimensional QFT unitary into three diagonal quadratic-phase gates and two standard radix-2 QFT subcircuits of size $M = 2^m$ (with $M \ge 2N - 1$). This achieves asymptotic gate complexity $O((\log N)^2)$ and uses $O(\log N)$ qubits, matching the performance of a power-of-two QFT on $m$ qubits while avoiding the need to embed into a larger Hilbert space. We validate the correctness of the algorithm through a concrete implementation in Qiskit and classical simulation, confirming that QBA produces the exact $N$-point discrete Fourier transform on arbitrary-length inputs.

quant-pharXiv:2512.15349•Physica Scripta•Dec 18, 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

Efficient Quantum Fourier Transforms For Semisimple Algebras

Ben Foxman, Barak Nehoran, Yongshan Ding

The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra $P_n(d)$, Brauer algebra $B_n(d)$, and walled Brauer algebra $B_{r,s}(d)$. These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms. Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter $d$ is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras $A$ from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity $\mathrm{poly}(n,\log d,\log(1/\varepsilon))$ for approximating the Fourier transform to error $(d^{-1/2} + \varepsilon) \cdot \mathrm{poly}(|A|)$. Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.

quant-pharXiv:2605.05337•May 8, 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

Towards an Optimally Distributed Quantum Fourier Transform Circuit

Zachary Vernec, Michael Silver, Hans-Arno Jacobsen

A promising avenue for scaling quantum computing is to connect quantum processing units (QPUs) by generating entanglement between them. This requires circuit partitioning: partially rewriting quantum circuits to run on a distributed quantum system using quantum teleportation protocols, while preserving the unitary operation implemented by the circuit. The key metric to minimize when partitioning is the e-bit count, defined as the number of maximally entangled qubit pairs that must be generated between QPUs. We focus on partitioning the quantum Fourier transform (QFT) circuit, which is widely used as a subroutine in quantum algorithms such as quantum phase estimation and arithmetic circuits. Specifically, we present an optimal gate-packing-based partitioning scheme under bounded communication ancilla constraints, as well as a novel detached-gate-based partitioning scheme that achieves optimal e-bit consumption when ancilla availability is unrestricted. We compare these schemes against prior analytical partitioning approaches for the QFT and evaluate them against partitions produced by general-purpose circuit partitioning algorithms. We further validate our approach by implementing the bounded-ancilla circuits on quantum hardware.

quant-pharXiv:2606.18494•Jun 18, 2026•0 citations

The exact lower bound of CNOT-complexity for fault-tolerant quantum Fourier transform

Qiqing Xia, Huiqin Xie, Yang, Li

The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-$R_k$ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-$R_k$ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.

arXiv:2409.02506•Sep 4, 2024•0 citations
We present an asymptotically improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. Historically, the approximate QFT has been implemented in Θ(nlog⁡n)Θ(n \log n)Θ(nlogn) gates, and the exact in Θ(n2)Θ(n^2)Θ(n2) gates. In this work, we show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits. Specifically, our approach yields an Θ(n(log⁡log⁡n)2)Θ(n(\log \log n)^2)Θ(n(loglogn)2) algorithm for the approximate QFT using Θ(log⁡n)Θ(\log n)Θ(logn) ancillas, and an Θ(n(log⁡n)2)Θ(n(\log n)^2)Θ(n(logn)2) algorithm for the exact QFT requiring Θ(n)Θ(n)Θ(n) ancillas.
We propose a quantum analogue of Bluestein's algorithm (QBA) that implements an exact NNN-point Quantum Fourier Transform (QFT) for arbitrary NNN. Our construction factors the NNN-dimensional QFT unitary into three diagonal quadratic-phase gates and two standard radix-2 QFT subcircuits of size M=2mM = 2^mM=2m (with M≥2N−1M \ge 2N - 1M≥2N−1). This achieves asymptotic gate complexity O((log⁡N)2)O((\log N)^2)O((logN)2) and uses O(log⁡N)O(\log N)O(logN) qubits, matching the performance of a power-of-two QFT on mmm qubits while avoiding the need to embed into a larger Hilbert space. We validate the correctness of the algorithm through a concrete implementation in Qiskit and classical simulation, confirming that QBA produces the exact NNN-point discrete Fourier transform on arbitrary-length inputs.
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 primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra Pn(d)P_n(d)Pn​(d), Brauer algebra Bn(d)B_n(d)Bn​(d), and walled Brauer algebra Br,s(d)B_{r,s}(d)Br,s​(d). These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms. Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter ddd is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras AAA from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity poly(n,log⁡d,log⁡(1/ε))\mathrm{poly}(n,\log d,\log(1/\varepsilon))poly(n,logd,log(1/ε)) for approximating the Fourier transform to error (d−1/2+ε)⋅poly(∣A∣)(d^{-1/2} + \varepsilon) \cdot \mathrm{poly}(|A|)(d−1/2+ε)⋅poly(∣A∣). Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.
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.
A promising avenue for scaling quantum computing is to connect quantum processing units (QPUs) by generating entanglement between them. This requires circuit partitioning: partially rewriting quantum circuits to run on a distributed quantum system using quantum teleportation protocols, while preserving the unitary operation implemented by the circuit. The key metric to minimize when partitioning is the e-bit count, defined as the number of maximally entangled qubit pairs that must be generated between QPUs. We focus on partitioning the quantum Fourier transform (QFT) circuit, which is widely used as a subroutine in quantum algorithms such as quantum phase estimation and arithmetic circuits. Specifically, we present an optimal gate-packing-based partitioning scheme under bounded communication ancilla constraints, as well as a novel detached-gate-based partitioning scheme that achieves optimal e-bit consumption when ancilla availability is unrestricted. We compare these schemes against prior analytical partitioning approaches for the QFT and evaluate them against partitions produced by general-purpose circuit partitioning algorithms. We further validate our approach by implementing the bounded-ancilla circuits on quantum hardware.
The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-RkR_kRk​ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-RkR_kRk​ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.