betaFeedback

WorksPhysics and Astronomy

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

Abstract

In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs O(q2)O(q^2) gates (and O(q)O(q) qubits) to perform the exact Fourier transform over F2q\mathbb{F}_{2^q}. Cleve and Watrous (FOCS 2000) improved this gate count to O(q(log⁡q)2(log⁡log⁡q))O(q (\log q)^2 (\log \log q)) using the integer multiplication algorithm in O(n(log⁡n)(log⁡log⁡n))O(n (\log n) (\log \log n)) time for two nn-bit integers (best known at that time). Our first main result shows that this gate count can be improved to O(q(log⁡q))O(q (\log q)). In fact, if there is a multiplication circuit, to multiply two nn-bit integers, with O(n(log⁡n)α)O(n (\log n)^α) gates; we get a QFT circuit with O(q(log⁡q)α)O(q (\log q)^α) gates (improving upon O(q(log⁡q)α+1)O(q (\log q)^{α+ 1})) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with o(q(log⁡q))o \left( q (\log q)\right) gates. On approximating the QFT over \ZZ/(2^q \ZZ), the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with O(q(log⁡log⁡(q/ε))α+1)O \left( q (\log \log(q/\varepsilon))^{α+1} \right) gates, where εε is the approximating parameter. Our second main result again improves this to O(q(log⁡log⁡(q/ε))α)O \left( q (\log \log(q/\varepsilon))^α \right) gates.

Introduction

The quantum Fourier transform (QFT) is a fundamental quantum algorithm and it has applications all over quantum computing. In particular, it plays a central role in Shor’s algorithms for factoring and discrete logarithms [22], and in the standard quantum phase-estimation procedure [8]. We refer the reader to [19, 13, 11, 8] for an introduction to the QFT and its applications.

For an integer 0≤x<2q0 \le x < 2^q, let ∣x⟩|x\rangle denote its qq-qubit computational basis encoding. The QFT is the unitary FqF_q defined by

Fq∣x⟩=2−q/2∑y=02q−1e2πixy/2q∣y⟩,for all 0≤x<2q.F_q|x\rangle= 2^{-q/2}\sum_{y=0}^{2^q-1} e^{2\pi ixy/2^q}|y\rangle,\qquad\text{for all } 0 \le x < 2^q.

By linearity, the action of FqF_q extends to any qq-qubit state ∣ψ⟩|\psi\rangle.

Let UU be a unitary circuit acting on the qq-qubit input register and aa auxiliary qubits initialized to ∣0a⟩|0^a\rangle. We say that UU implements FqF_q exactly if

U(∣ψ⟩∣0a⟩)=(Fq∣ψ⟩)∣0a⟩U(|\psi\rangle|0^a\rangle)=(F_q|\psi\rangle)|0^a\rangle

for every qq-qubit state ∣ψ⟩|\psi\rangle. We say that UU is an ϵ\epsilon-approximate implementation of FqF_q if

sup⁡∥ψ∥=1∥U(∣ψ⟩∣0a⟩)−(Fq∣ψ⟩)∣0a⟩∥≤ϵ.(1)\sup_{\|\psi\|=1}\left\|U(|\psi\rangle|0^a\rangle)-(F_q|\psi\rangle)|0^a\rangle\right\|\le\epsilon. \tag*{(1)}

The norm above is the Euclidean norm.

In this paper, we study the complexity of computing QFT in the quantum circuit model. Specifically, we are interested in the following question: how many gates are needed to implement the transform, both exactly as well as approximately?

Why look at approximate QFT? Approximation is a natural part of implementing the QFT. Even in an exact circuit, the required elementary gates may themselves needs to be approximated. For example, fault-tolerant implementations over Clifford+TT must account for the cost of synthesizing these gates [20]. Moreover, QFT is almost exclusively used as a subroutine. In that case an algorithm using the QFT generally requires only enough accuracy from QFT to preserve its overall success probability. Physical noise gives a further reason to study this tradeoff: a longer circuit that more closely approximates the ideal transform need not produce a more accurate final computation. This was demonstrated by Barenco, Ekert, Suominen, and Törmä [5] (building on Coppersmith’s truncated QFT construction [10]) for periodicity estimation under their model of decoherence.

Previous work

There has been a considerable amount of work in making quantum Fourier transform efficient in terms of the number of gates used. The standard circuit of the quantum Fourier transform (QFT), done by Coppersmith [10], is comprised of O(q)O(q) Hadamard gates and O(q2)O(q^2) controlled phase gates, giving a total of O(q2)O(q^2) gates.

In the same paper, Coppersmith [10] introduced the notion of approximate QFT, and obtained the approximate QFT circuit by omitting sufficiently small rotations. This reduces the gate count to O(qlog⁡(q/ϵ))O(q\log(q/\epsilon)), where ϵ\epsilon denotes the approximation error.

To reduce the gate count in exact QFT, Cleve and Watrous [12] developed a different approach by replacing groups of controlled rotations with reversible integer multiplication. Their construction yields an exact QFT on qq qubits using O(q(log⁡q)2log⁡log⁡q)O(q(\log q)^2\log\log q) elementary quantum gates and Approximate QFT using O(qlog⁡(q/ϵ))O(q\log(q/\epsilon)) many gates. This improves to O(q(log⁡q)2)O(q(\log q)^2) assuming the recent integer multiplication algorithm by Harvey and van der Hoeven [16]. Whether exact QFT on qq-qubits can be implemented by a circuit of size O(q)O(q) has been posed as an open problem by Aaronson [1].

On the approximate QFT front, Ahokas, Cleve, and Hales [2] gave a construction using O(q(log⁡log⁡(q/ε))2log⁡log⁡log⁡(q/ε))O(q(\log\log(q/\varepsilon))^2\log\log\log(q/\varepsilon)) elementary gates for approximation error ε\varepsilon. A detailed exposition could be found in Ahokas’s thesis [3 Section 3.1], which also provides an important comparison with [12]: integer multiplication can be used to improve both exact and approximate QFT constructions, with approximation permitting a smaller asymptotic gate count.

The result of Cleve and Watrous [12] discussed above also shows that the QFT can be approximated in depth O(log⁡q)O(\log q) for inverse-polynomial error. For the same error, when unbounded quantum fan-out gates are available, Høyer and Špalek [HŠ05] showed that the QFT can be approximated by constant-depth, polynomial-size circuits. Mosca and Zalka [18] used amplitude amplification to obtain an exact QFT over Z/NZ\mathbb{Z}/N\mathbb{Z} for arbitrary NN.

There has been work on reducing the number of ancilla qubits too, recently Kahanamoku-Meyer and Yao [17] gave an exact QFT with O(q1+δ)O(q^{1+\delta}) gates for every fixed δ>0\delta> 0, using zero ancillas. Here δ\delta controls the complexity exponent and is distinct from the approximation error. Compared with the polylogarithmic-overhead bound of [12], this result emphasizes reduced workspace: the product need not be explicitly stored in an ancillary register before phases are applied and the product is uncomputed.

Our results

Cleve and Watrous [12] showed how to use a classical circuit for integer multiplication to construct an exact QFT circuit. If two nn-bit integers can be multiplied by Boolean circuits over two-input AND and OR gates and single-input NOT gates, with unrestricted fan-out, using

M(n)=O(n(log⁡n)α)(2)M(n) = O\left(n(\log n)^\alpha\right) \tag*{(2)}

gates for a fixed constant $\alpha > 0, the construction of [12] gives an exact QFT on qq qubits using O(q(log⁡q)α+1)O(q(\log q)^{\alpha+1}) gates. For approximation error $0 < \varepsilon < 1$, the approach of Ahokas, Cleve, and Hales [3 Sections 3.1.1–3.1.2] retains only O(log⁡(q/ε))O(\log(q/\varepsilon)) leading bits of each input to a multiplication. Assuming the multiplication bound in Equation (2), this gives an approximate QFT using O(q(log⁡log⁡(q/ε))α+1)O(q(\log\log(q/\varepsilon))^{\alpha+1}) gates. Our main results improve these gate bounds to

O(q(log⁡q)α)andO(q(log⁡log⁡(q/ε))α)O\left(q(\log q)^\alpha\right) \quad\text{and} \quad O\left(q(\log\log(q/\varepsilon))^\alpha\right)

for exact and ε\varepsilon-approximate circuits, respectively. For the exact QFT, we use the same gate set as Cleve and Watrous [12], together with an additional single-qubit rotation gate whose angle depends on qq. This non-standard gate is described below. For the ε\varepsilon-approximate QFT, our construction uses the same gate set as in Cleve and Watrous.

Both theorems hold for every integer q≥64q \ge64. The exact construction does not require qq to be a power of two. The approximate construction allows unequal recursive splits. All logarithms have base two.

Theorem 1.1 (Exact QFT). Assume the multiplication bound in Equation (2). For every integer q≥64q \ge64, the transform FqF_q has an exact implementation using

O(q(log⁡q)α) gates and auxiliary qubits.O\left(q(\log q)^\alpha\right)\ \text{gates and auxiliary qubits.}

All auxiliary qubits return to zero.

The exact implementation uses Hadamard gates, controlled-NOT gates, and phase gates

P(2πa2d)=(100e2πia/2d),a∈Z, d∈Z≥1.(3)P\left(\frac{2\pi a}{2^d}\right)=\begin{pmatrix}1 & 0 \\ 0 & e^{2\pi i a/2^d}\end{pmatrix}, \qquad a\in\mathbb{Z},\ d\in\mathbb{Z}_{\ge1}. \tag*{(3)}

In addition, it uses a single-qubit rotation

B(θq)=(cos⁡θq−sin⁡θqsin⁡θqcos⁡θq),(4)B(\theta_q)=\begin{pmatrix}\cos\theta_q & -\sin\theta_q \\ \sin\theta_q & \cos\theta_q\end{pmatrix}, \tag*{(4)}

whose angle depends only on qq.

Theorem 1.2 (Approximate QFT). Assume the multiplication bound in Equation (2). For every integer q≥64q \ge64 and every 0<ε<10 < \varepsilon< 1, let

L=log⁡(q/ε).L=\log(q/\varepsilon).

The transform FqF_q has an ε\varepsilon-approximate implementation using

O(q(log⁡L)α) gatesandO(L(log⁡L)α) auxiliary qubits.O\left(q(\log L)^\alpha\right)\ \text{gates}\quad\text{and}\quad O\left(L(\log L)^\alpha\right)\ \text{auxiliary qubits}.

The implicit constants may depend on α\alpha and the multiplication family, but not on qq or ε\varepsilon.

The implementation in Theorem 1.2 uses Hadamard, controlled-NOT, and exact phase gates P(2πa/2d)P(2\pi a/2^d) for all a∈Za \in\mathbb{Z} (the aa used can depend on θq\theta_q). Presently we are not able to compute the angle θq\theta_q efficiently using a classical algorithm, thus our construction of the circuit families in both the theorems above are non-uniform. This is a natural open question from this work.

Our results thus improve the connection between the costs of integer multiplication and the QFT. In [21], OpenAI proposed an integer multiplication algorithm with complexity O(n(log⁡n)1−κ)O\left(n(\log n)^{1-\kappa}\right) for a fixed constant 0<κ<10 < \kappa< 1. Harvey [14] gave an exposition of the proposed algorithm and discusses this bound in the Boolean circuit model. Assuming the claimed bound holds for the Boolean circuits specified in Equation (2), we may take α=1−κ\alpha= 1-\kappa in our theorems. Theorem 1.1 then gives an exact QFT using O(q(log⁡q)1−κ)=o(qlog⁡q)O\left(q(\log q)^{1-\kappa}\right)=o(q\log q) gates, with exact access to the additional rotation B(θq)B(\theta_q) specified above. Theorem 1.2 similarly gives an approximate QFT using O(q(log⁡log⁡q)1−κ)=o(qlog⁡log⁡q)O\left(q(\log\log q)^{1-\kappa}\right)=o(q\log\log q) gates for inverse-polynomial error, without requiring that additional exact rotation. Whether the exact or approximate QFT on qq qubits admits a circuit of size O(q)O(q) remains an open question (see [1]).

Proof ideas

To prove Theorem 1.1, we combine the exactification method of Mosca and Zalka [18] with the multiplication-based implementation of the QFT due to Cleve and Watrous [12]. We then use the resulting exact circuit in the approximate construction of Ahokas, Cleve, and Hales [2], [3 Theorem 3.1] to prove Theorem 1.2. The construction is due to Ahokas, Cleve, and Hales [2]. Throughout, we refer to their work for the construction and cite the relevant sections of Ahokas’s thesis [3] for the formal statements of the results we use.

Exact QFT. Mosca and Zalka [18 Section 2] turn an approximate QFT circuit to an exact one by first making its success probability independent of the input Fourier state. An additional single-qubit rotation then reduces the success probability to 1/41/4, so that one step of amplitude amplification produces the correct answer with certainty.

In our construction, we first copy the Fourier state using the circuit of Cleve and Watrous, then apply the approximate inverse QFT to the copy [12 Section 3.2]. This leaves the original Fourier state available for the checking during amplitude amplification.

Besides calls to the approximate circuit and its inverse, the construction requires operations on Fourier states. These are carried out using a constant number of the product-phase operations defined below, together with O(q)O(q) additional gates. For qq-bit integers aa and bb, the product-phase operation is

∣a⟩∣b⟩↦e±2πiab/2q∣a⟩∣b⟩.(5)|a\rangle|b\rangle\mapsto e^{\pm2\pi iab/2^q}|a\rangle|b\rangle. \tag*{(5)}

This operation can be implemented using the multiplication-based construction of Cleve and Watrous [12 Section 4], at a cost of O(M(q))O(M(q)) gates. Thus, if the approximate circuit costs G(q)G(q) gates, the exact circuit costs O(G(q)+M(q))O(G(q)+M(q)) gates.

We choose the approximate circuit of Ahokas, Cleve, and Hales [3 Theorem 3.1]. Under the multiplication assumption in Equation (2), it uses G(q)=O(q(log⁡q)α+1)G(q)=O\left(q(\log q)^{\alpha+1}\right) gates at error at most 1/21/2. The resulting exact QFT uses O(q(log⁡q)α)O\left(q(\log q)^\alpha\right) gates.

Lemma 3.1 and it’s proof idea explains the construction in detail, including the implementation of these operations and their gate costs.

Using the improved exact circuit for approximation. We use the recursive construction of Ahokas, Cleve, and Hales [3 Section 3.1.1] to prove Theorem 1.2. Figure 1 shows one recursive step of this construction. Starting with the qq-qubit input, their construction proceeds as follows. Split the input into a lower register of q/2q/2 qubits and an upper register of q/2q/2 qubits. Apply the construction recursively to the upper register, apply the product-phase operation in Equation (5) between the two registers, and then apply the construction recursively to the lower register. Finally, exchange the two registers to obtain the required output order. For the product-phase operation, multiplication is done only on the highest kk bits of each multiplication input, where k=Θ(log⁡(q/ε))k=\Theta(\log(q/\varepsilon)). Stop the recursion when a register has at most 2k2k qubits, and apply an exact QFT to that register.

One recursive step of the ACH construction

Figure 1. One recursive step of the ACH construction.

Thus there are O(q/k)O(q/k) base cases and O(q/k)O(q/k) product-phase operations. Each product-phase operation costs O(k(log⁡k)α)O(k(\log k)^\alpha) gates. Using the exact construction of Cleve and Watrous [12], each base case costs O(k(log⁡k)α+1)O(k(\log k)^{\alpha+1}) gates. The base cases therefore determine the overall bound of O(q(log⁡k)α+1)O(q(\log k)^{\alpha+1}) gates.

We replace these base cases by our improved exact QFT, which costs O(k(log⁡k)α)O(k(\log k)^\alpha) gates per call and the total cost becomes O(q(log⁡k)α)O(q(\log k)^\alpha) gates. Recall that our improved exact circuit uses an additional single-qubit rotation. We efficiently approximate these rotations using the phase gates P(2πa/2d)P(2\pi a/2^d) defined in Equation (3). Since k=Θ(log⁡(q/ε))k=\Theta(\log(q/\varepsilon)), the resulting circuit uses O(q(log⁡log⁡(q/ε))α)O(q(\log\log(q/\varepsilon))^\alpha) gates.

Section 4 gives the full construction and proves its approximation error, gate count, and auxiliary-space bounds.

Preliminaries

Throughout this paper, we follow the standard notation and conventions of quantum computation. We refer the reader to Nielsen and Chuang [19] for background and further details.

Let N=2qN = 2^q, ω=e2πi/N\omega= e^{2\pi i/N}, and ∣ϕx⟩=Fq∣x⟩\lvert\phi_x\rangle= F_q\lvert x\rangle. Recall that, for 0≤a<N0 \le a < N, ∣a⟩\lvert a\rangle denotes the computational-basis state whose qq bits give the binary representation of aa. Addition and subtraction of register values are performed modulo NN using O(q)O(q) gates [7 Section 4.1].

We use the gate model stated after Theorem 1.1. NOT and Toffoli gates have constant-size implementations in this model [19]. A phase change conditioned on values of qq qubits uses O(q)O(q) gates and auxiliary qubits: compute the conjunction of the required bit values, apply the phase, and uncompute the conjunction. The same construction computes and uncomputes the OR of qq bits with O(q)O(q) gates and auxiliary qubits, all returned to zero.

We also use the standard reversible simulation of a Boolean circuit. A circuit with GG gates, where GG is at least the number of input and output bits, can be implemented reversibly using O(G)O(G) gates and wires. The simulation retains the inputs and clears its temporary registers by copying the output and reversing the computation [4, 19].

The following lemma implements a product-phase operation using integer multiplication.

Lemma 2.1 (Product-phase operation [9][12 Section 4]). Let AA and BB be integers stored in two qq-qubit registers, and let 1≤d≤2q1 \le d \le2q. The operation

∣A⟩∣B⟩⟼e±2πiAB/2d∣A⟩∣B⟩\lvert A\rangle\lvert B\rangle\longmapsto e^{\pm2\pi iAB/2^d}\lvert A\rangle\lvert B\rangle

has an exact implementation using O(M(q))O(M(q)) gates and auxiliary qubits. All auxiliary qubits return to zero.

Proof. Compute the product ABAB into a 2q2q-qubit auxiliary register initialized to zero, using the reversible circuit for multiplication. Let AB=∑j=02q−1pj2jAB = \sum_{j=0}^{2q-1} p_j2^j. Apply P(±2π2j/2d)P(\pm2\pi2^j/2^d) to each bit pjp_j with 0≤j<d0 \le j < d, and reverse the multiplication. The phase gates multiply the state by

∏j=0d−1e±2πipj2j/2d=e±2πi(∑j=0d−1pj2j)/2d=e±2πiAB/2d.\prod_{j=0}^{d-1}e^{\pm2\pi i p_j2^j/2^d} =e^{\pm2\pi i(\sum_{j=0}^{d-1}p_j2^j)/2^d} =e^{\pm2\pi iAB/2^d}.

The last equality holds because the terms omitted in AB/2dAB/2^d sum to an integer and thus do not contribute to the phase. Since the phase gates leave the product unchanged, reversing the multiplication clears every temporary register while preserving the desired phase. The forward and reverse computations cost O(M(q))O(M(q)) gates. □

We will use the following result of [12], which shows that Fourier basis states can be copied efficiently.

Lemma 2.2 (Fourier-state copying [12 Section 3.2]). There is a circuit using O(q)O(q) gates and auxiliary qubits that maps

∣ϕx⟩I∣0q⟩O⟼∣ϕx⟩I∣ϕx⟩O\lvert\phi_x\rangle_I\lvert0^q\rangle_O \longmapsto\lvert\phi_x\rangle_I\lvert\phi_x\rangle_O

for every 0≤x<N0 \le x < N. All auxiliary qubits return to zero.

Proof. Apply Hadamard gates to OO, then subtract its value from II. For a fixed value cc in OO, changing variables in the sum gives

1N∑s=0N−1ωxs∣s−c⟩I∣c⟩O=ωxc∣ϕx⟩I∣c⟩O.(6)\frac{1}{\sqrt{N}}\sum_{s=0}^{N-1}\omega^{xs}\lvert s-c\rangle_I\lvert c\rangle_O =\omega^{xc}\lvert\phi_x\rangle_I\lvert c\rangle_O. \tag*{(6)}

Thus the uniform superposition in OO acquires the phases of ∣ϕx⟩\lvert\phi_x\rangle. The Hadamard gates and reversible subtraction use O(q)O(q) gates and auxiliary qubits, with temporary qubits returned to zero. □

We will also use the following result from [18], which allows us to apply a conditional phase based on whether a Fourier-state label matches a computational-basis label.

Lemma 2.3 (Fourier-state answer test [18 Section 2.1.1]). Let II and OO be qq-qubit registers and EE a single qubit. There is a unitary DD satisfying

D(∣ϕx⟩I∣y⟩O∣b⟩E)=(−1)1{x=y, b=1}∣ϕx⟩I∣y⟩O∣b⟩ED\left(\lvert\phi_x\rangle_I\lvert y\rangle_O\lvert b\rangle_E\right)=(-1)^{\mathbf{1}_{\{x=y,\ b=1\}}}\lvert\phi_x\rangle_I\lvert y\rangle_O\lvert b\rangle_E

for all 0≤x,y<N0\le x,y<N and b∈{0,1}b\in\{0,1\}. Here the exponent is one when both x=yx=y and b=1b=1, and zero otherwise. The operation uses O(M(q))O(M(q)) gates and auxiliary qubits. All auxiliary qubits return to zero.

Proof. The idea is to transform II so that equality x=yx=y can be tested by computing the OR of its qq bits, apply the required phase when this OR is zero, and then undo the computation.

First apply the product phase ω−ys\omega^{-ys} using Lemma 2.1 with d=qd=q, where yy is the value in OO and ss is the computational-basis value in II.

For fixed x,y,bx,y,b, the action on the three registers is

∣ϕx⟩I∣y⟩O∣b⟩E=1N∑s=0N−1ωxs∣s⟩I∣y⟩O∣b⟩E⟼1N∑s=0N−1ωxsω−ys∣s⟩I∣y⟩O∣b⟩E=1N∑s=0N−1ω(x−y)s∣s⟩I∣y⟩O∣b⟩E=∣ϕx−y⟩I∣y⟩O∣b⟩E.\begin{aligned} \lvert\phi_x\rangle_I\lvert y\rangle_O\lvert b\rangle_E &=\frac{1}{\sqrt{N}}\sum_{s=0}^{N-1}\omega^{xs}\lvert s\rangle_I\lvert y\rangle_O\lvert b\rangle_E\\ &\longmapsto\frac{1}{\sqrt{N}}\sum_{s=0}^{N-1}\omega^{xs}\omega^{-ys}\lvert s\rangle_I\lvert y\rangle_O\lvert b\rangle_E\\ &=\frac{1}{\sqrt{N}}\sum_{s=0}^{N-1}\omega^{(x-y)s}\lvert s\rangle_I\lvert y\rangle_O\lvert b\rangle_E\\ &=\lvert\phi_{x-y}\rangle_I\lvert y\rangle_O\lvert b\rangle_E. \end{aligned}

Thus the product phase subtracts the value yy from the Fourier label xx.

Next apply H⊗qH^{\otimes q} to II. If x=yx=y, then ∣ϕx−y⟩=∣ϕ0⟩\lvert\phi_{x-y}\rangle=\lvert\phi_0\rangle is the uniform superposition, so these Hadamard gates map it to ∣0q⟩\lvert0^q\rangle. If x≠yx\ne y, the resulting state is orthogonal to ∣0q⟩\lvert0^q\rangle, since

⟨0q∣H⊗q∣ϕx−y⟩=1N∑s=0N−1ω(x−y)s=0.\langle0^q\lvert H^{\otimes q}\lvert\phi_{x-y}\rangle=\frac{1}{N}\sum_{s=0}^{N-1}\omega^{(x-y)s}=0.

Compute the OR of the bits in II into an auxiliary qubit and apply a phase of −1-1 when this qubit is zero and EE is one. This gives the required phase precisely when x=yx=y and b=1b=1.

Uncompute the OR, the Hadamard gates, and the product phase to restore the input registers and clear all auxiliary qubits while retaining the required phase.

The product phase and its inverse use O(M(q))O(M(q)) gates and auxiliary qubits by Lemma 2.1. The Hadamard gates and conditional phase change add O(q)O(q) gates and auxiliary qubits, so the total cost is O(M(q))O(M(q)). □

The next lemma gives the action of one Grover iterate when the initial probability of the good states is 1/41/4: this choice makes the final probability exactly one.

Lemma 2.4 (One Grover iterate [18 BHMT02]). Let UU be a unitary on mm qubits such that

U∣0⟩=∣sx⟩=12∣gx⟩+32∣hx⟩,(7)U\lvert0\rangle=\lvert s_x\rangle=\frac{1}{2}\lvert g_x\rangle+\frac{\sqrt{3}}{2}\lvert h_x\rangle, \tag*{(7)}

where ∣0⟩|0\rangle denotes the all-zero state and ∣gx⟩|g_x\rangle and ∣hx⟩|h_x\rangle are orthogonal unit vectors. Let DD be a unitary satisfying

D∣gx⟩=−∣gx⟩,D∣hx⟩=∣hx⟩.D|g_x\rangle=-|g_x\rangle,\qquad D|h_x\rangle=|h_x\rangle.

Write R0=2∣0⟩⟨0∣−IR_0=2|0\rangle\langle0|-I. Then

UR0U†D∣sx⟩=∣gx⟩.UR_0U^\dagger D|s_x\rangle=|g_x\rangle.

This Grover iterate uses one call each to DD, U†U^\dagger, R0R_0, UU. The reflection R0R_0 uses O(m)O(m) gates and O(m)O(m) auxiliary qubits, all returned to zero.

Proof. Since U∣0⟩=∣sx⟩U|0\rangle=|s_x\rangle, UR0U†=2∣sx⟩⟨sx∣−IUR_0U^\dagger=2|s_x\rangle\langle s_x|-I. The action of DD gives

D∣sx⟩=−12∣gx⟩+32∣hx⟩.D|s_x\rangle=-\frac{1}{2}|g_x\rangle+\frac{\sqrt{3}}{2}|h_x\rangle.

Since ∣gx⟩|g_x\rangle and ∣hx⟩|h_x\rangle are orthogonal unit vectors, ⟨sx∣D∣sx⟩=−1/4+3/4=1/2\langle s_x|D|s_x\rangle=-1/4+3/4=1/2. Therefore

(2∣sx⟩⟨sx∣−I)D∣sx⟩=∣sx⟩−D∣sx⟩=∣gx⟩.\left(2|s_x\rangle\langle s_x|-I\right)D|s_x\rangle=|s_x\rangle-D|s_x\rangle =|g_x\rangle.

To implement R0R_0, compute the OR of the mm bits into an auxiliary qubit, apply a ZZ gate to that qubit, and uncompute the OR. This leaves ∣0⟩|0\rangle unchanged and multiplies every other computational-basis state by −1-1.

Theorem 2.5 (Approximate QFT, [3 Theorem 3.1]). Assume the multiplication bound in Equation (2). For every integer q≥64q\ge64, there is a unitary circuit WW on qq qubits such that

∥W−Fq∥≤12.\lVert W-F_q\rVert\le\frac{1}{2}.

where the norm is the operator norm. The circuit uses O(q(log⁡log⁡q)α+1)O\left(q(\log\log q)^{\alpha+1}\right) gates, consisting of the phase gates in Equation (3) and Hadamard and controlled-NOT gates, and O(q(log⁡log⁡q)α+1)O\left(q(\log\log q)^{\alpha+1}\right) auxiliary qubits, all returned to zero. The inverse circuit has the same resource bounds and approximates Fq†F_q^\dagger to the same error.

Proof. We apply the multiplication bound in Equation (2) to the ACH construction [3 Sections 3.1.1–3.1.3], described in § 1.3.

Let k=Θ(log⁡q)k=\Theta(\log q) as in § 1.3. Their construction uses O(q/k)O(q/k) product-phase operations and exact QFTs on at most 2k2k qubits. By Lemma 2.1 and the Cleve–Watrous exact construction [12 Section 4], these cost O(k(log⁡k)α)O\left(k(\log k)^{\alpha}\right) and O(k(log⁡k)α+1)O\left(k(\log k)^{\alpha+1}\right) gates, respectively. Their total cost is therefore O(q(log⁡log⁡q)α+1)O\left(q(\log\log q)^{\alpha+1}\right). The error analysis in [3 Section 3.1.2, Equation (3.5)] shows that choosing a suitable k=Θ(log⁡q)k=\Theta(\log q) gives approximation error at most 1/21/2. Furthermore, the circuits return their auxiliary qubits to zero, and the number of auxiliary qubits is bounded by a constant times the gate count. Reversing the circuit preserves these bounds and the operator-norm error.

Proof of Theorem 1.1

Let VV be a unitary circuit on qq qubits satisfying ∥V−Fq†∥≤1/2\lVert V-F_q^\dagger\rVert\le1/2 in operator norm. Suppose VV can be implemented using G(q)G(q) gates and a(q)a(q) auxiliary qubits that are returned to zero. For 0≤x<N0\le x<N, define

px=∣⟨x∣V∣ϕx⟩∣2,p=1N∑x=0N−1px.(8)p_x=\left|\langle x|V|\phi_x\rangle\right|^2,\qquad p=\frac{1}{N}\sum_{x=0}^{N-1}p_x. \tag*{(8)}

Thus pxp_x is the probability of obtaining xx when VV is applied to ∣ϕx⟩|\phi_x\rangle and the output is measured in the computational basis. The quantity pp is the average of these probabilities over uniformly chosen xx. Since ∥V∣ϕx⟩−∣x⟩∥≤1/2\lVert V|\phi_x\rangle-|x\rangle\rVert\le1/2, the component orthogonal to ∣x⟩|x\rangle has squared norm at most 1/41/4. Thus px≥3/4p_x \ge3/4 for every xx, and p≥3/4p \ge3/4.

We first modify the circuit so that the probability of the correct answer equals pp for every xx. To make this answer certain with one Grover iterate, we introduce an extra qubit and require both a correct answer and value one in that qubit. The joint probability must be 1/41/4, so we choose the probability of value one to be 1/(4p)1/(4p). Since p≥3/4p \ge3/4, this choice is possible. Let

θq=arcsin⁡(12p).(9)\theta_q = \arcsin\left(\frac{1}{2\sqrt{p}}\right). \tag*{(9)}

We assume exact access to the rotation B(θq)B(\theta_q) defined in Equation (4), at unit cost. The angle depends on VV and qq, and is independent of the input xx. Its inverse has constant cost as well, since B(θq)†=XB(θq)XB(\theta_q)^\dagger= X B(\theta_q) X.

Lemma 3.1. Under these assumptions, FqF_q and Fq†F_q^\dagger have exact implementations using

O(G(q)+M(q))gatesandO(a(q)+M(q))auxiliary qubits.O(G(q)+M(q)) \quad\text{gates} \quad\text{and} \quad O(a(q)+M(q)) \quad\text{auxiliary qubits}.

All auxiliary qubits return to zero.

Proof of Lemma 3.1. Let II be the input register, initially containing ∣ϕx⟩|\phi_x\rangle. All auxiliary registers introduced below are initialized to zero.

Preparing a state with success probability 1/41/4. We first modify the approximate circuit so that it produces the correct answer with the same probability for every xx. Following Mosca and Zalka [18 Section 2.2], we do this by averaging over a uniformly chosen shift of the Fourier label. Introduce a qq-qubit output register OO. Apply Lemma 2.2 to copy the Fourier state into OO, obtaining ∣ϕx⟩I∣ϕx⟩O|\phi_x\rangle_I|\phi_x\rangle_O at a cost of O(q)O(q) gates. We retain the original Fourier state in II to check the answer later. Add another qq-qubit register SS and apply the following operations:

  1. Apply Hadamard gates to SS, preparing a uniform superposition of shifts rr.

  1. Apply the product phase ω−rs\omega^{-rs}, where rr and ss are the values in SS and OO, respectively. Expanding the Fourier state in OO shows how this shifts its label:

1N∑r=0N−1∣ϕx⟩I∣ϕx⟩O∣r⟩S=1N∑r,s=0N−1ωxs∣ϕx⟩I∣s⟩O∣r⟩S\frac{1}{\sqrt{N}}\sum_{r=0}^{N-1}|\phi_x\rangle_I|\phi_x\rangle_O|r\rangle_S = \frac{1}{N}\sum_{r,s=0}^{N-1}\omega^{xs}|\phi_x\rangle_I|s\rangle_O|r\rangle_S
⟼1N∑r,s=0N−1ωxsω−rs∣ϕx⟩I∣s⟩O∣r⟩S=1N∑r,s=0N−1ω(x−r)s∣ϕx⟩I∣s⟩O∣r⟩S=1N∑r=0N−1∣ϕx⟩I∣ϕx−r⟩O∣r⟩S.\begin{aligned} \longmapsto \frac{1}{N}\sum_{r,s=0}^{N-1}\omega^{xs}\omega^{-rs}|\phi_x\rangle_I|s\rangle_O|r\rangle_S \\ &= \frac{1}{N}\sum_{r,s=0}^{N-1}\omega^{(x-r)s}|\phi_x\rangle_I|s\rangle_O|r\rangle_S \\ &= \frac{1}{\sqrt{N}}\sum_{r=0}^{N-1}|\phi_x\rangle_I|\phi_{x-r}\rangle_O|r\rangle_S. \end{aligned}

Thus, for each shift rr, the state in OO becomes ∣ϕx−r⟩|\phi_{x-r}\rangle, while the original Fourier state in II is unchanged.

  1. Apply VV to OO, then add the value in SS to OO modulo NN.

For each shift rr, the answer in OO equals xx precisely when VV gives x−rx-r on input ∣ϕx−r⟩\lvert\phi_{x-r}\rangle, which has probability px−rp_{x-r}. Thus the probability that OO contains xx is

1N∑r=0N−1px−r=p.\frac{1}{N}\sum_{r=0}^{N-1}p_{x-r}=p.

Finally introduce an auxiliary qubit EE to adjust the success probability to 1/41/4. Apply B(θq)B(\theta_q) to EE, obtaining

B(θq)∣0⟩E=1−14p∣0⟩E+12p∣1⟩E.B(\theta_q)\lvert0\rangle_E=\sqrt{1-\frac{1}{4p}}\lvert0\rangle_E+\frac{1}{2\sqrt{p}}\lvert1\rangle_E.

For fixed xx, call a state ∣ϕx⟩I∣y⟩O∣r⟩S∣b⟩E\lvert\phi_x\rangle_I\lvert y\rangle_O\lvert r\rangle_S\lvert b\rangle_E good when y=xy=x and b=1b=1. The total probability of the good states is p/(4p)=1/4p/(4p)=1/4, as in Mosca and Zalka [18 Section 4.2].

Let UU be the circuit consisting of the operations above and denote the state that it prepares by

∣sx⟩=U(∣ϕx⟩I∣0⟩O,S,E).\lvert s_x\rangle=U\left(\lvert\phi_x\rangle_I\lvert0\rangle_{O,S,E}\right).

It uses one call to VV, one product-phase operation, and O(q)O(q) other gates, so its cost is O(G(q)+M(q))O(G(q)+M(q)).

Making the answer certain. Let DD be the operation of Lemma 2.3 on I,O,EI,O,E, acting trivially on SS. It multiplies the good-state amplitudes by −1-1 using O(M(q))O(M(q)) gates. Let R0R_0 reflect about the all-zero state of O,S,EO,S,E, acting trivially on II; this costs O(q)O(q) gates by Lemma 2.4.

For an input Fourier state ∣ϕx⟩\lvert\phi_x\rangle, the Grover iteration acts within the subspace in which register II contains ∣ϕx⟩\lvert\phi_x\rangle. The prepared state ∣sx⟩\lvert s_x\rangle lies in this subspace, and each of the operations D,U†,R0,UD,U^\dagger,R_0,U preserves it. Indeed, the copying circuit of Lemma 2.2 and its inverse preserve ∣ϕx⟩\lvert\phi_x\rangle in II, while the remaining operations in UU act only on the other registers. The answer test DD restores ∣ϕx⟩\lvert\phi_x\rangle after applying the conditional phase, as shown in Lemma 2.3, and R0R_0 does not act on II. Within this subspace, the operation UR0U†UR_0U^\dagger reflects about ∣sx⟩\lvert s_x\rangle.

Since the good-state probability is 1/41/4, write

∣sx⟩=12∣gx⟩+32∣hx⟩,\lvert s_x\rangle=\frac{1}{2}\lvert g_x\rangle+\frac{\sqrt{3}}{2}\lvert h_x\rangle,

where ∣gx⟩\lvert g_x\rangle and ∣hx⟩\lvert h_x\rangle are the normalized good and bad components. Lemma 2.4 then gives

UR0U†D∣sx⟩=∣gx⟩.(10)UR_0U^\dagger D\lvert s_x\rangle=\lvert g_x\rangle. \tag*{(10)}

Hence OO contains xx with certainty, while II still contains ∣ϕx⟩\lvert\phi_x\rangle.

Clearing the computation. Let T=UR0U†DUT=UR_0U^\dagger DU be the circuit that prepares and amplifies the answer. Since its output register OO contains xx with certainty, copy xx into a new qq-qubit register RR, initialized to zero, and apply T†T^\dagger to the original registers. This restores the state

∣ϕx⟩I∣x⟩R,\lvert\phi_x\rangle_I\lvert x\rangle_R,

with all other registers zero.

We now clear II using the value xx in RR. As in the proof of Lemma 2.3, applying the product phase ω−xs\omega^{-xs}, where ss is the computational-basis value in II, and then Hadamard gates maps ∣ϕx⟩I\lvert\phi_x\rangle_I to ∣0q⟩I\lvert0^q\rangle_I. Swapping II and RR therefore gives

∣ϕx⟩I∣0b⟩R⟼∣x⟩I∣0b⟩R,\lvert\phi_x\rangle_I\lvert0^b\rangle_R\longmapsto\lvert x\rangle_I\lvert0^b\rangle_R,

where bb counts all auxiliary qubits. Since the Fourier states form a basis, linearity shows that this circuit implements Fq†F_q^\dagger exactly. Reversing it gives FqF_q.

Gate count and auxiliary space. Since T=UR0U†DUT = U R_0 U^\dagger D U uses a constant number of calls to UU, U†U^\dagger, DD, and R0R_0, it costs O(G(q)+M(q))O(G(q) + M(q)) gates. Applying T†T^\dagger and clearing the remaining registers preserves this bound. The construction uses O(a(q)+M(q))O(a(q) + M(q)) auxiliary qubits, all returned to zero.

Proof of Theorem 1.1. Choose VV to be the approximate inverse QFT supplied by Theorem 2.5. It has error at most 1/21/2 and uses

G(q)=O(q(log⁡log⁡q)α+1)(11)G(q) = O\left(q(\log\log q)^{\alpha+1}\right) \tag*{(11)}

gates and O(G(q))O(G(q)) auxiliary qubits. Applying Lemma 3.1 gives an exact QFT using

O(M(q)+q(log⁡log⁡q)α+1)=O(q(log⁡q)α)O\left(M(q) + q(\log\log q)^{\alpha+1}\right) = O\left(q(\log q)^\alpha\right)

gates and auxiliary qubits. All auxiliary qubits are returned to zero.

Proof of Theorem 1.2

Let ExactQFT denote the exact QFT circuit constructed in § 3 and let L=log⁡(q/ε)L = \log(q/\varepsilon). We prove Theorem 1.2 in two parts. First, we use ExactQFT in the ACH construction (see § 1.3) to obtain an approximate QFT with O(q(log⁡L)α)O(q(\log L)^\alpha) gates and O(L(log⁡L)α)O(L(\log L)^\alpha) auxiliary qubits. This circuit still uses the additional rotations of the form given in Equation (4). In our second step, we approximate these rotations using Hadamard gates and the phase gates P(2πa/2d)P(2\pi a/2^d). We show that the resulting circuit has error at most ε\varepsilon without changing the gate or auxiliary-qubit bounds.

Fix q≥64q \ge64 and 0<ε<10 < \varepsilon< 1. Choose an integer

k=Θ(L),(12)k = \Theta(L), \tag*{(12)}

with a sufficiently large constant.

Approximate QFT using exact base cases

Consider an nn-qubit register with n>2kn > 2k. Split it into a lower register of r=⌊n/2⌋r = \lfloor n/2\rfloor qubits and an upper register of s=⌈n/2⌉s = \lceil n/2\rceil qubits. The full QFT first transforms the upper register, applies

∣u⟩∣v⟩⟼e2πiuv/2n∣u⟩∣v⟩,|u\rangle|v\rangle\longmapsto e^{2\pi iuv/2^n}|u\rangle|v\rangle,

then transforms the lower register and exchanges the two registers. Here uu is the value in the lower rr-qubit register and vv is the value in the upper ss-qubit register at the time of the product-phase operation. This is the Cleve–Watrous recursion [12 Section 4].

ACH keep only the highest kk bits of each value when calculating the product phase. Since n>2kn > 2k, both registers have at least kk qubits. Write their retained values as u′u' and v′v'. In the phase calculation, replace uu and vv by 2r−ku′2^{r-k}u' and 2s−kv′2^{s-k}v', respectively, to obtain the shortened operation below

∣u⟩∣v⟩⟼e2πiu′v′/22k∣u⟩∣v⟩.(13)|u\rangle|v\rangle\longmapsto e^{2\pi i u'v'/2^{2k}}|u\rangle|v\rangle. \tag*{(13)}

Apply Lemma 2.1 to the two groups of kk selected qubits, with q=kq = k and d=2kd = 2k. This implements the operation with O(M(k))O(M(k)) gates and auxiliary qubits, all returned to zero, and leaves the unselected bits untouched.

When n≤2kn \le2k, we apply ExactQFT to the entire nn-qubit register. The procedure ApproxQFT below gives the complete construction.

Procedure ApproxQFT. Apply the following procedure to an nn-qubit register, initially with n=qn=q, keeping kk fixed throughout. All calls share an auxiliary register AA, initialized to ∣0a⟩\lvert0^{a}\rangle, and return it to zero.

  1. If n≤2kn \le2k, apply ExactQFT on these nn qubits and stop.

  2. Otherwise split the register into its lower rr qubits and upper ss qubits, as above.

  3. Apply ApproxQFT to the upper register.

  4. Apply the shortened product-phase operation in Equation (13).

  5. Apply ApproxQFT to the lower register.

  6. Exchange the registers, placing the transformed lower register before the transformed upper register.

Let U0U_0 denote the circuit implemented by ApproxQFT.

Correctness. The base-case calls implement exact QFTs, so the only error comes from shortening the product phases. To bound one such error, write

u=2r−ku′+a0,v=2s−kv′+b0,0≤a0<2r−k,0≤b0<2s−k.u = 2^{r-k}u' + a_0,\qquad v = 2^{s-k}v' + b_0,\qquad0 \le a_0 < 2^{r-k},\qquad0 \le b_0 < 2^{s-k}.

The omitted part of the phase exponent is

0≤uv2n−u′v′22k=a0v+2r−ku′b02n<2⋅2−k.0 \le\frac{uv}{2^n} - \frac{u'v'}{2^{2k}} = \frac{a_0v + 2^{r-k}u'b_0}{2^n} < 2 \cdot2^{-k}.

Thus the full and shortened product phases differ by at most 4π2−k4\pi2^{-k} in operator norm, using ∣eix−eiy∣≤∣x−y∣\lvert e^{ix} - e^{iy}\rvert\le\lvert x-y\rvert. There are fewer than qq product-phase operations. Replacing them one at a time and applying the triangle inequality bounds the error of the shortened transform by 4πq2−k4\pi q2^{-k}. Thus, for every input state ∣ψ⟩\lvert\psi\rangle,

∥U0(∣ψ⟩∣0a⟩)−(Fq∣ψ⟩)∣0a⟩∥≤4πq2−k.(14)\left\|U_0\left(\lvert\psi\rangle\lvert0^a\rangle\right)-\left(F_q\lvert\psi\rangle\right)\lvert0^a\rangle\right\| \le4\pi q2^{-k}. \tag*{(14)}

Gate count and auxiliary space. Suppose first that q>2kq>2k. The base-case registers partition the qq input qubits, and each contains between kk and 2k2k qubits. There are therefore O(q/k)O(q/k) base cases. The recursion is a binary tree hence there are O(q/k)O(q/k) shortened product-phase operations in Step 4. By Theorem 1.1, each base-case call uses O(k(log⁡k)α)O\left(k(\log k)^\alpha\right) gates. Each shortened product phase uses O(M(k))O(M(k)) gates by Lemma 2.1. Together they use

O(qk(k(log⁡k)α+M(k)))=O(q(log⁡k)α)O\left(\frac{q}{k}\left(k(\log k)^\alpha+ M(k)\right)\right)=O\left(q(\log k)^\alpha\right)

gates.

We postpone the exchanges in Step 6, keeping track of which wire holds each qubit and applying subsequent gates to those wires. This choice of wires is made when constructing the circuit and requires no gates. At the end, one permutation puts all output qubits in the required order using O(q)O(q) swaps.

Each base-case call uses O(k(log⁡k)α)O\left(k(\log k)^\alpha\right) auxiliary qubits by Theorem 1.1, and each product-phase operation uses O(M(k))O(M(k)) by Lemma 2.1. These operations run sequentially and return their auxiliary qubits to zero, so they can reuse the same register AA. Thus a=O(k(log⁡k)α)a = O\left(k(\log k)^\alpha\right) auxiliary qubits suffice, and the circuit uses q+aq+a qubits in total. Using k=Θ(L)k = \Theta(L), the resulting bounds are

O(q(log⁡L)α) gates,O(L(log⁡L)α) auxiliary qubits.O\left(q(\log L)^\alpha\right)\ \text{gates},\qquad O\left(L(\log L)^\alpha\right)\ \text{auxiliary qubits}.

If q≤2kq \le2k, there is only one ExactQFT call. Its gate count and auxiliary space are both O(q(log⁡q)α)O\left(q(\log q)^\alpha\right), where q=O(L)q = O(L).

Replacing the additional rotations

Recall that ExactQFT uses the circuit T=UR0U†DUT = UR_0U^\dagger DU and its inverse from § 3. These make O(1)O(1) calls to the circuit UU and its inverse, each of which contains one additional rotation or its inverse. Thus ExactQFT uses B(θt)B(\theta_t) and its inverse only O(1)O(1) times. The following lemma bounds the resulting error on the input and auxiliary registers.

Lemma 4.1. Let t≥64t \ge64 and let XtX_t be the unitary implemented by the complete ExactQFT circuit on its input and auxiliary registers. Replacing its additional rotations gives a unitary X^t\widehat{X}_t using only Hadamard gates, controlled-NOT gates, and the phase gates in Equation (3), with

∥X^t−Xt∥≤12π2−k(15)\left\|\widehat{X}_t-X_t\right\| \le12\pi2^{-k} \tag*{(15)}

in operator norm. Each rotation replacement uses a constant number of gates and no additional auxiliary qubits.

Proof. The idea is to express the rotation using a phase gate and then round its angle. Set S=P(π/2)S = P(\pi/2) and J=SHJ = SH. Direct multiplication gives

JP(2θt)J†=eiθtB(θt).JP(2\theta_t)J^\dagger= e^{i\theta_t}B(\theta_t).

Choose an integer ata_t such that

φt=2πat2k,∣φt−2θt∣≤2π2−k,\varphi_t = \frac{2\pi a_t}{2^k},\qquad\left|\varphi_t-2\theta_t\right| \le2\pi2^{-k},

and put Ct=JP(φt)J†C_t = JP(\varphi_t)J^\dagger. Replace B(θt)B(\theta_t) by CtC_t and its inverse by Ct†C_t^\dagger. These use only a constant number of allowed gates, since SS and S†S^\dagger are themselves phase gates of the form in Equation (3). Moreover,

∥Ct−eiθtB(θt)∥=∣eiφt−e2iθt∣≤2π2−k.\left\|C_t-e^{i\theta_t}B(\theta_t)\right\| = \left|e^{i\varphi_t}-e^{2i\theta_t}\right| \le2\pi2^{-k}.

The adjoints satisfy the same bound. The scalar phases cause no error in the complete circuit. Replacing these six gates one at a time by CtC_t or Ct†C_t^\dagger gives total operator-norm error at most 6⋅2π2−k6\cdot2\pi2^{-k} by the triangle inequality.

Apply Lemma 4.1 to every base-case call in U0U_0, and denote the resulting circuit by U^0\widehat{U}_0.

Error and resource bounds after replacement. The auxiliary register AA may no longer return exactly to zero after a base-case call. We pass it to the next operation without measuring or resetting it, and include it throughout the error comparison. Lemma 4.1 bounds the change in each complete call by 12π2−k12\pi2^{-k} in operator norm, including its auxiliary registers. This bound applies even when those registers contain errors or are entangled with other registers. There are at most qq base-case calls, so replacing them one at a time gives

∥U^0−U0∥≤12πq2−k.\left\|\widehat{U}_0-U_0\right\| \le12\pi q2^{-k}.

Combining this with Equation (14) gives

∥U^0(∣ψ⟩∣0a⟩)−(Fq∣ψ⟩)∣0a⟩∥≤16πq2−k≤ε.(16)\left\lVert\widehat{U}_0\left(|\psi\rangle|0^a\rangle\right)-\left(F_q|\psi\rangle\right)|0^a\rangle\right\rVert\le16\pi q 2^{-k} \le\varepsilon. \tag*{(16)}

Open problems

Our results leave several questions about the circuit complexity of the QFT. We mention some of them in this section.

Our exact construction uses an additional single-qubit rotation whose angle depends on qq. Can the same gate bound be achieved using only Hadamard, controlled-NOT, and the phase gates in Equation (3)?

We do not establish uniformity of our circuit families in this work. Assuming that the multiplication circuits can be generated in classical polynomial time, can our QFT circuits also be generated efficiently? It would suffice to show that the additional rotation angle, determined by the average success probability of the approximate inverse QFT, can be approximated to additive error 2−d2^{-d} by a classical algorithm running in time polynomial in qq and dd.

Finally, can the exact QFT on qq qubits be implemented using O(q)O(q) one- and two-qubit gates? This question was raised by Aaronson [1]. The analogous question is also natural for approximate QFTs: for a fixed constant 0<ε<1/20 < \varepsilon< 1/2, can ε\varepsilon-approximate QFT be computed by a circuit of size O(q)O(q)?

AI statement. We used GPT-6 Astra, GPT-6.1 Sol, and Claude Opus 5.5 to explore proof strategies, search for related literature, and revise the manuscript. The main proof ideas were generated by these systems. The authors examined these ideas, identified and corrected errors, and significantly simplified the arguments and their presentation. The authors take full responsibility for the correctness and content of the paper.

References

  1. [1]Scott Aaronson. Good news for once! a faster quantum fourier transform, January 2025. Shtetl-Optimized, January 23. 2, 4, 14
  2. [2]Graeme Ahokas, Richard Cleve, and Lisa Hales. The complexity of quantum Fourier transforms and integer multiplication, 2003. Unpublished research abstract, presented at the ERATO Conference on Quantum Information Science, Kyoto, September 2003. Author’s PDF. 3, 4
  3. [3]Graeme Robert Ahokas. Improved algorithms for approximate quantum Fourier transforms and sparse Hamiltonian simulations. M.sc. thesis, University of Calgary, April 2004. 3, 4, 5, 8DOI
  4. [4]Charles H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17(6):525–532, 1973. doi:10.1147/rd.176.0525. 6DOI
  5. [5]Adriano Barenco, Artur Ekert, Kalle-Antti Suominen, and Päivi Törmä. Approximate quantum Fourier transform and decoherence. Physical Review A, 54(1):139–146, 1996. 2DOI
  6. [7]Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit, 2004. arXiv:quant-ph/0410184.DOI
  7. [8]Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):339–354, 1998. doi:10.1098/rspa.1998.0164.DOI
  8. [9]Richard Cleve. A note on computing Fourier transforms by quantum programs, 1994. Unpublished manuscript. Author’s PDF.
  9. [10]Don Coppersmith. An approximate Fourier transform useful in quantum factoring. Research Report RC 19642, IBM Research Division, 1994. Available as arXiv:quant-ph/0201067, uploaded in 2002.
  10. [11]Andrew M. Childs and Wim van Dam. Quantum algorithms for algebraic problems. Reviews of Modern Physics, 82(1):1–52, 2010. doi:10.1103/RevModPhys.82.1.DOI
  11. [12]Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 526–536, 2000. arXiv:quant-ph/0006004.
  12. [13]Ronald de Wolf. Quantum computing: Lecture notes, 2019. Revised August 2026. arXiv:1907.09415v6.arxiv.org/abs/1907.09415
  13. [14]David Harvey. On the recently proposed o(n log n) integer multiplication algorithm, 2026. Preprint, October 20. Author’s PDF.
  14. [16]David Harvey and Joris van der Hoeven. Integer multiplication in time O(n log n). Annals of Mathematics, 193(2):563–617, 2021.DOI
  15. [17]Gregory D. Kahanamoku-Meyer and Norman Y. Yao. Fast quantum integer multiplication with zero ancillas, 2024. arXiv:2403.18006v4.
  16. [18]Michele Mosca and Christof Zalka. Exact quantum Fourier transforms and discrete logarithm algorithms, 2003. arXiv:quant-ph/0301093.DOI
  17. [19]Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition, 2010. doi:10.1017/CBO9780511976667.
  18. [20]Yunseong Nam, Yuan Su, and Dmitri Maslov. Approximate quantum Fourier transform with O(n log n) T gates. npj Quantum Information, 6:26, 2020. doi:10.1038/s41534-020-0257-5.DOI
  19. [21]OpenAI. Integer multiplication below n log n, 2026. Preprint, September 23. Author’s PDF.
  20. [22]Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. doi:10.1137/S0097539795293172. 1DOI

Paper details

vlnc:W_p2mcg9vs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents