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 gates (and qubits) to perform the exact Fourier transform over . Cleve and Watrous (FOCS 2000) improved this gate count to using the integer multiplication algorithm in time for two -bit integers (best known at that time). Our first main result shows that this gate count can be improved to . In fact, if there is a multiplication circuit, to multiply two -bit integers, with gates; we get a QFT circuit with gates (improving upon ) 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 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 gates, where is the approximating parameter. Our second main result again improves this to 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 , let denote its -qubit computational basis encoding. The QFT is the unitary defined by
By linearity, the action of extends to any -qubit state .
Let be a unitary circuit acting on the -qubit input register and auxiliary qubits initialized to . We say that implements exactly if
for every -qubit state . We say that is an -approximate implementation of if
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+ 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 Hadamard gates and controlled phase gates, giving a total of 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 , where 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 qubits using elementary quantum gates and Approximate QFT using many gates. This improves to assuming the recent integer multiplication algorithm by Harvey and van der Hoeven [16]. Whether exact QFT on -qubits can be implemented by a circuit of size has been posed as an open problem by Aaronson [1].
On the approximate QFT front, Ahokas, Cleve, and Hales [2] gave a construction using elementary gates for approximation error . 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 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 for arbitrary .
There has been work on reducing the number of ancilla qubits too, recently Kahanamoku-Meyer and Yao [17] gave an exact QFT with gates for every fixed , using zero ancillas. Here 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 -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
gates for a fixed constant $\alpha > 0, the construction of [12] gives an exact QFT on qubits using gates. For approximation error $0 < \varepsilon < 1$, the approach of Ahokas, Cleve, and Hales [3 Sections 3.1.1–3.1.2] retains only leading bits of each input to a multiplication. Assuming the multiplication bound in Equation (2), this gives an approximate QFT using gates. Our main results improve these gate bounds to
for exact and -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 . This non-standard gate is described below. For the -approximate QFT, our construction uses the same gate set as in Cleve and Watrous.
Both theorems hold for every integer . The exact construction does not require 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 , the transform has an exact implementation using
All auxiliary qubits return to zero.
The exact implementation uses Hadamard gates, controlled-NOT gates, and phase gates
In addition, it uses a single-qubit rotation
whose angle depends only on .
Theorem 1.2 (Approximate QFT). Assume the multiplication bound in Equation (2). For every integer and every , let
The transform has an -approximate implementation using
The implicit constants may depend on and the multiplication family, but not on or .
The implementation in Theorem 1.2 uses Hadamard, controlled-NOT, and exact phase gates for all (the used can depend on ). Presently we are not able to compute the angle 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 for a fixed constant . 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 in our theorems. Theorem 1.1 then gives an exact QFT using gates, with exact access to the additional rotation specified above. Theorem 1.2 similarly gives an approximate QFT using gates for inverse-polynomial error, without requiring that additional exact rotation. Whether the exact or approximate QFT on qubits admits a circuit of size 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 , 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 additional gates. For -bit integers and , the product-phase operation is
This operation can be implemented using the multiplication-based construction of Cleve and Watrous [12 Section 4], at a cost of gates. Thus, if the approximate circuit costs gates, the exact circuit costs gates.
We choose the approximate circuit of Ahokas, Cleve, and Hales [3 Theorem 3.1]. Under the multiplication assumption in Equation (2), it uses gates at error at most . The resulting exact QFT uses 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 -qubit input, their construction proceeds as follows. Split the input into a lower register of qubits and an upper register of 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 bits of each multiplication input, where . Stop the recursion when a register has at most qubits, and apply an exact QFT to that register.

Figure 1. One recursive step of the ACH construction.
Thus there are base cases and product-phase operations. Each product-phase operation costs gates. Using the exact construction of Cleve and Watrous [12], each base case costs gates. The base cases therefore determine the overall bound of gates.
We replace these base cases by our improved exact QFT, which costs gates per call and the total cost becomes gates. Recall that our improved exact circuit uses an additional single-qubit rotation. We efficiently approximate these rotations using the phase gates defined in Equation (3). Since , the resulting circuit uses 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 , , and . Recall that, for , denotes the computational-basis state whose bits give the binary representation of . Addition and subtraction of register values are performed modulo using 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 qubits uses 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 bits with gates and auxiliary qubits, all returned to zero.
We also use the standard reversible simulation of a Boolean circuit. A circuit with gates, where is at least the number of input and output bits, can be implemented reversibly using 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 and be integers stored in two -qubit registers, and let . The operation
has an exact implementation using gates and auxiliary qubits. All auxiliary qubits return to zero.
Proof. Compute the product into a -qubit auxiliary register initialized to zero, using the reversible circuit for multiplication. Let . Apply to each bit with , and reverse the multiplication. The phase gates multiply the state by
The last equality holds because the terms omitted in 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 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 gates and auxiliary qubits that maps
for every . All auxiliary qubits return to zero.
Proof. Apply Hadamard gates to , then subtract its value from . For a fixed value in , changing variables in the sum gives
Thus the uniform superposition in acquires the phases of . The Hadamard gates and reversible subtraction use 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 and be -qubit registers and a single qubit. There is a unitary satisfying
for all and . Here the exponent is one when both and , and zero otherwise. The operation uses gates and auxiliary qubits. All auxiliary qubits return to zero.
Proof. The idea is to transform so that equality can be tested by computing the OR of its bits, apply the required phase when this OR is zero, and then undo the computation.
First apply the product phase using Lemma 2.1 with , where is the value in and is the computational-basis value in .
For fixed , the action on the three registers is
Thus the product phase subtracts the value from the Fourier label .
Next apply to . If , then is the uniform superposition, so these Hadamard gates map it to . If , the resulting state is orthogonal to , since
Compute the OR of the bits in into an auxiliary qubit and apply a phase of when this qubit is zero and is one. This gives the required phase precisely when and .
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 gates and auxiliary qubits by Lemma 2.1. The Hadamard gates and conditional phase change add gates and auxiliary qubits, so the total cost is . □
The next lemma gives the action of one Grover iterate when the initial probability of the good states is : this choice makes the final probability exactly one.
Lemma 2.4 (One Grover iterate [18 BHMT02]). Let be a unitary on qubits such that
where denotes the all-zero state and and are orthogonal unit vectors. Let be a unitary satisfying
Write . Then
This Grover iterate uses one call each to , , , . The reflection uses gates and auxiliary qubits, all returned to zero.
Proof. Since , . The action of gives
Since and are orthogonal unit vectors, . Therefore
To implement , compute the OR of the bits into an auxiliary qubit, apply a gate to that qubit, and uncompute the OR. This leaves unchanged and multiplies every other computational-basis state by .
Theorem 2.5 (Approximate QFT, [3 Theorem 3.1]). Assume the multiplication bound in Equation (2). For every integer , there is a unitary circuit on qubits such that
where the norm is the operator norm. The circuit uses gates, consisting of the phase gates in Equation (3) and Hadamard and controlled-NOT gates, and auxiliary qubits, all returned to zero. The inverse circuit has the same resource bounds and approximates 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 as in § 1.3. Their construction uses product-phase operations and exact QFTs on at most qubits. By Lemma 2.1 and the Cleve–Watrous exact construction [12 Section 4], these cost and gates, respectively. Their total cost is therefore . The error analysis in [3 Section 3.1.2, Equation (3.5)] shows that choosing a suitable gives approximation error at most . 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 be a unitary circuit on qubits satisfying in operator norm. Suppose can be implemented using gates and auxiliary qubits that are returned to zero. For , define
Thus is the probability of obtaining when is applied to and the output is measured in the computational basis. The quantity is the average of these probabilities over uniformly chosen . Since , the component orthogonal to has squared norm at most . Thus for every , and .
We first modify the circuit so that the probability of the correct answer equals for every . 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 , so we choose the probability of value one to be . Since , this choice is possible. Let
We assume exact access to the rotation defined in Equation (4), at unit cost. The angle depends on and , and is independent of the input . Its inverse has constant cost as well, since .
Lemma 3.1. Under these assumptions, and have exact implementations using
All auxiliary qubits return to zero.
Proof of Lemma 3.1. Let be the input register, initially containing . All auxiliary registers introduced below are initialized to zero.
Preparing a state with success probability . We first modify the approximate circuit so that it produces the correct answer with the same probability for every . Following Mosca and Zalka [18 Section 2.2], we do this by averaging over a uniformly chosen shift of the Fourier label. Introduce a -qubit output register . Apply Lemma 2.2 to copy the Fourier state into , obtaining at a cost of gates. We retain the original Fourier state in to check the answer later. Add another -qubit register and apply the following operations:
Apply Hadamard gates to , preparing a uniform superposition of shifts .
Apply the product phase , where and are the values in and , respectively. Expanding the Fourier state in shows how this shifts its label:
Thus, for each shift , the state in becomes , while the original Fourier state in is unchanged.
Apply to , then add the value in to modulo .
For each shift , the answer in equals precisely when gives on input , which has probability . Thus the probability that contains is
Finally introduce an auxiliary qubit to adjust the success probability to . Apply to , obtaining
For fixed , call a state good when and . The total probability of the good states is , as in Mosca and Zalka [18 Section 4.2].
Let be the circuit consisting of the operations above and denote the state that it prepares by
It uses one call to , one product-phase operation, and other gates, so its cost is .
Making the answer certain. Let be the operation of Lemma 2.3 on , acting trivially on . It multiplies the good-state amplitudes by using gates. Let reflect about the all-zero state of , acting trivially on ; this costs gates by Lemma 2.4.
For an input Fourier state , the Grover iteration acts within the subspace in which register contains . The prepared state lies in this subspace, and each of the operations preserves it. Indeed, the copying circuit of Lemma 2.2 and its inverse preserve in , while the remaining operations in act only on the other registers. The answer test restores after applying the conditional phase, as shown in Lemma 2.3, and does not act on . Within this subspace, the operation reflects about .
Since the good-state probability is , write
where and are the normalized good and bad components. Lemma 2.4 then gives
Hence contains with certainty, while still contains .
Clearing the computation. Let be the circuit that prepares and amplifies the answer. Since its output register contains with certainty, copy into a new -qubit register , initialized to zero, and apply to the original registers. This restores the state
with all other registers zero.
We now clear using the value in . As in the proof of Lemma 2.3, applying the product phase , where is the computational-basis value in , and then Hadamard gates maps to . Swapping and therefore gives
where counts all auxiliary qubits. Since the Fourier states form a basis, linearity shows that this circuit implements exactly. Reversing it gives .
Gate count and auxiliary space. Since uses a constant number of calls to , , , and , it costs gates. Applying and clearing the remaining registers preserves this bound. The construction uses auxiliary qubits, all returned to zero.
Proof of Theorem 1.1. Choose to be the approximate inverse QFT supplied by Theorem 2.5. It has error at most and uses
gates and auxiliary qubits. Applying Lemma 3.1 gives an exact QFT using
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 . 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 gates and 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 . We show that the resulting circuit has error at most without changing the gate or auxiliary-qubit bounds.
Fix and . Choose an integer
with a sufficiently large constant.
Approximate QFT using exact base cases
Consider an -qubit register with . Split it into a lower register of qubits and an upper register of qubits. The full QFT first transforms the upper register, applies
then transforms the lower register and exchanges the two registers. Here is the value in the lower -qubit register and is the value in the upper -qubit register at the time of the product-phase operation. This is the Cleve–Watrous recursion [12 Section 4].
ACH keep only the highest bits of each value when calculating the product phase. Since , both registers have at least qubits. Write their retained values as and . In the phase calculation, replace and by and , respectively, to obtain the shortened operation below
Apply Lemma 2.1 to the two groups of selected qubits, with and . This implements the operation with gates and auxiliary qubits, all returned to zero, and leaves the unselected bits untouched.
When , we apply ExactQFT to the entire -qubit register. The procedure ApproxQFT below gives the complete construction.
Procedure ApproxQFT. Apply the following procedure to an -qubit register, initially with , keeping fixed throughout. All calls share an auxiliary register , initialized to , and return it to zero.
If , apply ExactQFT on these qubits and stop.
Otherwise split the register into its lower qubits and upper qubits, as above.
Apply ApproxQFT to the upper register.
Apply the shortened product-phase operation in Equation (13).
Apply ApproxQFT to the lower register.
Exchange the registers, placing the transformed lower register before the transformed upper register.
Let 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
The omitted part of the phase exponent is
Thus the full and shortened product phases differ by at most in operator norm, using . There are fewer than product-phase operations. Replacing them one at a time and applying the triangle inequality bounds the error of the shortened transform by . Thus, for every input state ,
Gate count and auxiliary space. Suppose first that . The base-case registers partition the input qubits, and each contains between and qubits. There are therefore base cases. The recursion is a binary tree hence there are shortened product-phase operations in Step 4. By Theorem 1.1, each base-case call uses gates. Each shortened product phase uses gates by Lemma 2.1. Together they use
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 swaps.
Each base-case call uses auxiliary qubits by Theorem 1.1, and each product-phase operation uses by Lemma 2.1. These operations run sequentially and return their auxiliary qubits to zero, so they can reuse the same register . Thus auxiliary qubits suffice, and the circuit uses qubits in total. Using , the resulting bounds are
If , there is only one ExactQFT call. Its gate count and auxiliary space are both , where .
Replacing the additional rotations
Recall that ExactQFT uses the circuit and its inverse from § 3. These make calls to the circuit and its inverse, each of which contains one additional rotation or its inverse. Thus ExactQFT uses and its inverse only times. The following lemma bounds the resulting error on the input and auxiliary registers.
Lemma 4.1. Let and let be the unitary implemented by the complete ExactQFT circuit on its input and auxiliary registers. Replacing its additional rotations gives a unitary using only Hadamard gates, controlled-NOT gates, and the phase gates in Equation (3), with
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 and . Direct multiplication gives
Choose an integer such that
and put . Replace by and its inverse by . These use only a constant number of allowed gates, since and are themselves phase gates of the form in Equation (3). Moreover,
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 or gives total operator-norm error at most by the triangle inequality.
Apply Lemma 4.1 to every base-case call in , and denote the resulting circuit by .
Error and resource bounds after replacement. The auxiliary register 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 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 base-case calls, so replacing them one at a time gives
Combining this with Equation (14) gives
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 . 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 by a classical algorithm running in time polynomial in and .
Finally, can the exact QFT on qubits be implemented using 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 , can -approximate QFT be computed by a circuit of size ?
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]Scott Aaronson. Good news for once! a faster quantum fourier transform, January 2025. Shtetl-Optimized, January 23. 2, 4, 14
- [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]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]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]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
- [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
- [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
- [9]Richard Cleve. A note on computing Fourier transforms by quantum programs, 1994. Unpublished manuscript. Author’s PDF.
- [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.
- [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
- [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.
- [13]Ronald de Wolf. Quantum computing: Lecture notes, 2019. Revised August 2026. arXiv:1907.09415v6.arxiv.org/abs/1907.09415
- [14]David Harvey. On the recently proposed o(n log n) integer multiplication algorithm, 2026. Preprint, October 20. Author’s PDF.
- [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
- [17]Gregory D. Kahanamoku-Meyer and Norman Y. Yao. Fast quantum integer multiplication with zero ancillas, 2024. arXiv:2403.18006v4.
- [18]Michele Mosca and Christof Zalka. Exact quantum Fourier transforms and discrete logarithm algorithms, 2003. arXiv:quant-ph/0301093.DOI
- [19]Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition, 2010. doi:10.1017/CBO9780511976667.
- [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
- [21]OpenAI. Integer multiplication below n log n, 2026. Preprint, September 23. Author’s PDF.
- [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