Approximate Quantum Fourier Transform in Logarithmic Depth on a Line
Elisa Bäumer ,, David Sutter, Stefan Woerner · 2025
Read Approximate Quantum Fourier Transform in Logarithmic Depth on a Line by Elisa Bäumer ,, David Sutter, Stefan Woerner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20832.txt.
Introduction
Elisa Baumer, David Sutter, and Stefan Woerner cut the cost of a key quantum algorithm in a 2025 paper. The approximate quantum Fourier transform is a basic building block of quantum computing. A known design runs it in logarithmic depth, but needs many qubits wired to all others, which real hardware struggles to provide.
Using dynamic circuits, with measurements and feed-forward during the run, the team achieves the same depth on a simple line of qubits. They need half as many qubits as the older design, and fewer still for structured states. Line layouts match how many quantum chips are actually built.
Catalog record
| CREATOR | Elisa Bäumer ,, David Sutter, Stefan Woerner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-20832
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximate Quantum Fourier Transform in Logarithmic Depth on a Line Elisa Bäumer ,, David Sutter, Stefan Woerner Abstract The approximate quantum Fourier transform (AQFT) on n n qubits can be implemented in logarithmic depth using 8 n 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 4 n 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 2 n 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. 1 Introduction It is widely believed that quantum computers can solve problems that no classical algorithm can solve in a reasonable amount of time. Arguably, the most prominent example is Shor’s algorithm [ 1 ] to factor an arbitrary integer in polynomial time, whereas the most efficient known classical factoring algorithms have a sub-exponential runtime [ 2 ] . To quantify the cost of implementing a quantum algorithm represented by a quantum circuit, typically three quantities are considered: (i) the width, i.e., the number of qubits, (ii) the depth, i.e., the number of consecutive time steps necessary to execute the circuit, where a time step is a single application of the maximum number of gates such that all applied gates can be executed simultaneously, and (iii) the size, i.e., the total number of gates. Width and depth are arguably the most operationally relevant metrics, as they quantifiy the required number of qubits and resulting runtime of an algorithm. While occasionally only the size and width of an algorithm are analyzed, this only gives a lower bound on the depth. In contrast, analyzing the width and depth directly results in an upper bound on the size. Here, we assume that gates on distinct subsets of qubits that are applied in the same time slice can be executed in parallel. One crucial building block in Shor’s algorithm is the quantum Fourier transform (QFT). In [ 3 ] , Cleve and Watrous showed that the approximate quantum Fourier transform (AQFT) on n qubits can be implemented in depth O(\log n) with all-to-all connectivity between the qubits and O(n\log n) ancilla qubits. They also reduced the circuit size of the exact QFT from O(n^{2}) to O(n(\log n)^{2}\log\log n) , still with a depth of O(n) though. Later in [ 4 ] , Hales showed that the AQFT can be implemented in the same depth, however, requiring only 8n qubits. There have been further improvements regarding the size of the AQFT but with linear depth [ 5 ] . The depth can be further reduced to constant when using O(n^{3}\log n) qubits and all-to-all connectivity [ 6 , 7 ] . Here, we focus on logarithmic depth constructions that require only O(n) qubits on a line. A natural question is whether the width or connectivity requirements to implement the AQFT can be further improved while preserving logarithmic depth. In this work, we show that (1) we can relax the connectivity requirements from all-to-all to a minimum, i.e., to a line of qubits with nearest-neighbor connectivity (see Table 1 ). (2) we can reduce the number of qubits to 4n for a line of qubits with nearest-neighbor connectivity and to 3n for an all-to-all connectivity (see Table 2 ). We refer to Theorem 1.2 for the mathematically rigorous statement. Our algorithm builds on the results from [ 4 ] and we use the power of dynamic circuits, i.e., mid-circuit measurements and feed-forward operations, to implement the circuits on a line without increasing the required depth. In particular, we show how to implement a quantum adder in logarithmic depth on a line of qubits using dynamic circuits, enabling our main result. For states with specific structure, we do not even require dynamic circuits and can implement the AQFT on a line of only 2n qubits. 1.1 Main results Let N:=2^{n} , where n\in\mathbb{N} is the number of qubits. Furthermore, let \omega_{N}:=\mathrm{e}^{\frac{2\pi\mathrm{i}}{N}} be the N -the root of unity. We denote the quantum Fourier state corresponding to the computational basis state |j\rangle , j\in\{0,\ldots,N{-}1\} , by \displaystyle|\phi(j)\rangle:=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_{N}^{jk}|k\rangle\,. (1) Note that |\phi(0)\rangle=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle=H^{\otimes n}|0\rangle , i.e., we can switch between |\phi(0)\rangle and |0\rangle by applying a layer of Hadamard gates. The QFT mapping performs the operation \displaystyle|j\rangle_{A}|0\rangle_{B}\overset{\textnormal{QFT}_{AB}}{\longrightarrow}|\phi(j)\rangle_{A}|0\rangle_{B}\,, (2) where A denotes the n -qubit target register and B is an n -qubit ancilla register that is required by the construction used below. Note that the resulting order of qubits in A is reversed. The AQFT is a unitary that is close to the exact QFT. More precisely, for \varepsilon>0 , an AQFT acting on an n -qubit register A , as well as an n -qubit ancilla register B , is defined as an isometry \mathrm{QFT}^{(\varepsilon)}_{AB} , such that \displaystyle\mathrm{dist}_{\mathcal{S}}(\mathrm{QFT}_{AB},\mathrm{QFT}^{(\varepsilon)}_{AB})\leq\varepsilon\,, (3) where \mathrm{dist}_{\mathcal{S}}(\cdot,\cdot) will be defined formally in Section 2.1 , \mathrm{QFT}_{AB} denotes the quantum Fourier transform unitary defined in Equation 2 and \mathcal{S} is the set of arbitrary states in A and E with \dim(E)=M\geq 2^{2n} and |0\rangle on an n -qubit ancilla register B , i.e., \displaystyle\mathcal{S}:=\Big\{|\psi\rangle_{ABE}\in\mathcal{H}_{ABE}:|\psi\rangle_{ABE}=\sum_{j=0}^{N-1}\sum_{m=0}^{M-1}\alpha_{j,m}|j\rangle_{A}|0\rangle_{B}|m\rangle_{E}\Big\}\,, (4) where |\psi\rangle_{ABE}\in\mathcal{H}_{ABE} denotes the set of normalized, pure quantum states on a tripartite Hilbert space \mathcal{H}_{ABE} . Before explaining the AQFT operation in full generality, we consider a restricted version thereof that assumes input states that have a certain structure. More precisely, we focus on input states from the following set \displaystyle\mathcal{S}_{\mathrm{uni}}^{(p)}:=\Big\{|\psi\rangle_{ABE}\in\mathcal{H}_{ABE}:|\psi\rangle_{ABE}=\sum_{j=0}^{N-1}\sum_{m=0}^{M-1}\beta_{j,m}|j\rangle_{A}|0\rangle_{B}|m\rangle_{E}\,,|\sum_{m=0}^{M-1}\beta_{j,m}\beta_{\ell,m}^{\ast}|\leq\frac{p(n)}{N}\delta_{j,\ell}\;\forall j,\ell\Big\}\,, (5) with some environment E with dimension \dim(E)=M\geq 2^{2n} , where \delta_{j,\ell} denotes a Kronecker delta, and p(n) denotes a polynomial in n with fixed degree independent of n , i.e., states with amplitudes that are somewhat uniformly distributed in A . If we choose the polynomial p(n) in Equation 5 to be the constant 1 we obtain the set \mathcal{S}_{\mathrm{uni}}^{(1)} . Note that clearly \mathcal{S}_{\mathrm{uni}}^{(p)}\subseteq\mathcal{S} . For \varepsilon>0 the AQFT acting on states in \mathcal{S}_{\mathrm{uni}}^{(p)} , is defined as a unitary \mathrm{QFT}_{\mathrm{uni}}^{(\varepsilon)} , such that \displaystyle\mathrm{dist}_{\mathcal{S}_{\mathrm{uni}}^{(p)}}(\mathrm{QFT},\mathrm{QFT}_{\mathrm{uni}}^{(\varepsilon)})\leq\varepsilon\,. (6) Lemma 1.1 (AQFT for uniform inputs) . Let n\in\mathbb{N} , \frac{1}{\mathrm{poly}(n)}\leq\varepsilon<1 and \mathcal{S}_{\mathrm{uni}}^{(p)} as defined in Equation 5 . A unitary \mathrm{QFT}^{(\varepsilon)}_{\mathrm{uni}} acting on \mathcal{S}_{\mathrm{uni}}^{(p)} satisfying Equation 6 can be implemented on a line of 2n qubits with nearest-neighbor connectivity with depth O(\log\frac{np(n)}{\varepsilon^{2}}) . Specifically, if acting on states in \mathcal{S}_{\mathrm{uni}}^{(1)} , it can be implemented in depth O(\log\frac{n}{\varepsilon^{2}}) . The proof is given in Section A.3 . While it is guaranteed to work for uniform inputs of the form Equation 5 , it also works for most random input states |\psi\rangle_{ABE}\in\mathcal{S} (see Remark A.1 ). Thus, implementing \mathrm{QFT}^{(\varepsilon)}_{\mathrm{uni}} may be very relevant in practice, as it can always be the first try if the result is verifiable, such as for Shor’s algorithm (see Section 4 for more details). We want to emphasize that our proof uses the ideas introduced in [ 4 ] , maps the algorithm to a line of qubits and reduces its