⚛️ quantum physics

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

This paper presents improved quantum circuit constructions for both exact and approximate Quantum Fourier Transforms that reduce the gate complexity from $O(q (\log q)^{\alpha+1})$ and $O(q (\log \log(q/\varepsilon))^{\alpha+1})$ to $O(q (\log q)^{\alpha})$ and $O(q (\log \log(q/\varepsilon))^{\alpha})$ , respectively, by leveraging advancements in integer multiplication algorithms.

Original author: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

Published 2026-11-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the realm of quantum computing, machines do not process information in the simple, linear way of the laptops and smartphones we use every day. Instead, they manipulate delicate states of matter that can exist in many configurations simultaneously. To make these machines solve complex problems, scientists rely on a specific mathematical operation called the quantum Fourier transform. Think of this operation as a powerful lens that takes a jumbled mixture of possibilities and sorts them into a clear pattern, revealing hidden structures within the data. This sorting process is the engine behind some of the most famous quantum algorithms, including those designed to crack modern encryption codes or simulate chemical reactions. For decades, the standard way to build this lens in a quantum circuit required a number of physical components that grew very quickly as the problem size increased, making large-scale applications difficult to realize.

A team of researchers has now proposed a way to build this essential lens much more efficiently. By rethinking how the operation is constructed, they have demonstrated that the number of physical components needed can be reduced significantly, provided a specific method for multiplying numbers is used. Their work shows that if one can multiply large numbers using a certain efficient method, the quantum Fourier transform can be built with far fewer steps than previously thought possible. This improvement applies to both the perfect, exact version of the operation and the slightly approximate version that is often used in practice. The researchers achieved this by combining existing techniques with a clever trick involving the copying of quantum states and a final check that ensures the answer is correct every time.

The core of the challenge lies in the sheer number of physical gates required to perform the transform. In the standard approach, the number of gates grows with the square of the number of bits involved, which becomes unmanageable for large problems. A previous generation of researchers improved this by linking the transform to the problem of integer multiplication, reducing the growth rate to a level involving logarithms. However, the new study pushes this boundary even further. The authors show that the number of gates can be reduced to match the efficiency of the multiplication method itself, rather than being one step slower. If the multiplication method is highly efficient, the quantum Fourier transform becomes correspondingly efficient.

To achieve this, the researchers first constructed an exact version of the transform. They started with an approximate circuit, which is easier to build but not perfectly accurate. They then used a technique to copy the quantum state produced by this approximate circuit. By comparing the original state with the copy, they could verify the result. If the result was correct, they amplified its probability until it became certain. This process required a specific, single rotation of a quantum bit, an angle that depends on the size of the problem. While this rotation is not a standard component in all quantum circuits, its inclusion allowed the team to turn an approximate solution into a perfect one without adding a massive number of extra gates.

The team then applied this improved exact circuit to the problem of building an approximate transform, which is often sufficient for real-world applications. They used a recursive method, breaking the large problem into smaller, manageable pieces. In the past, the smallest pieces of this puzzle were solved using older, less efficient methods. By replacing those small pieces with their new, highly efficient exact circuit, the entire structure became much leaner. The result is a circuit that uses significantly fewer gates than any previous design, scaling in a way that closely follows the efficiency of modern integer multiplication algorithms.

This work also addresses the question of how these circuits are built. The researchers note that their design relies on a specific rotation angle that is difficult to calculate quickly using classical computers. Because of this, the family of circuits they describe is not "uniform," meaning there is no single, simple rule that generates every version of the circuit for every problem size without external help. This is a limitation they acknowledge, leaving open the question of whether a fully uniform version can be found that maintains this high level of efficiency. Nevertheless, the findings establish a new, tighter connection between the cost of multiplying numbers and the cost of performing the quantum Fourier transform.

The implications of this discovery are significant for the future of quantum computing. If the recent claims about even faster integer multiplication algorithms hold true, the new construction suggests that the quantum Fourier transform could be built with a number of gates that grows even more slowly than previously imagined. This brings the prospect of running large-scale quantum algorithms, such as those for factoring large numbers, closer to reality. The researchers have not just found a small optimization; they have fundamentally reshaped the theoretical limits of how efficiently this critical operation can be performed, proving that the path to powerful quantum computers may be shorter than the maps we were using before.

Technical Summary: Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

Problem Statement

The Quantum Fourier Transform (QFT) is a fundamental subroutine in quantum algorithms, most notably Shor's factoring algorithm and quantum phase estimation. The standard circuit implementation of the QFT over $F_{2^q}$ requires $O(q^2)$ gates. While Cleve and Watrous (2000) reduced the gate count for exact QFT to $O(q(\log q)^2 \log \log q)$ by leveraging integer multiplication algorithms, and Ahokas, Cleve, and Hales (2003) provided further optimizations for approximate QFT, the authors identify a gap between the complexity of integer multiplication and the resulting QFT circuit complexity.

Specifically, if integer multiplication of $n$ -bit numbers can be performed with $M(n) = O(n(\log n)^\alpha)$ gates, the Cleve-Watrous construction yields an exact QFT with $O(q(\log q)^{\alpha+1})$ gates. The paper addresses the question of whether this overhead can be reduced, aiming to match the multiplication complexity more closely (i.e., achieving $O(q(\log q)^\alpha)$ ) for both exact and approximate QFTs.

Methodology

The authors propose a two-pronged approach to improve the gate complexity of QFT constructions:

1. Exact QFT Construction

The authors combine the "exactification" method of Mosca and Zalka (2003) with the multiplication-based implementation of Cleve and Watrous (2000).

Amplitude Amplification: They utilize a technique to convert an approximate QFT circuit (with success probability $p \geq 3/4$ $p \geq 3/4$ ) into an exact one. This involves:
1. Copying the Fourier State: Using the Cleve-Watrous copying circuit to duplicate the Fourier state, allowing the original to be preserved for verification.
2. Probability Adjustment: Introducing an auxiliary qubit and applying a specific single-qubit rotation $B(\theta_q)$ to adjust the joint success probability of the correct answer and the auxiliary qubit state to exactly $1/4$ .
3. Grover Iteration: Applying a single step of amplitude amplification (a Grover iterate) to boost the success probability to 1.
Gate Set: The construction uses standard gates (Hadamard, CNOT, Phase gates) plus a specific single-qubit rotation $B(\theta_q)$ whose angle depends on $q$ . This non-standard gate is required to set the initial amplitude for the amplification step.

2. Approximate QFT Construction

For the approximate QFT, the authors adapt the recursive construction of Ahokas, Cleve, and Hales (ACH).

Recursive Splitting: The input register is recursively split into upper and lower halves. The construction applies a recursive QFT to the upper register, performs a "product-phase" operation between the registers, applies a recursive QFT to the lower register, and swaps the registers.
Truncation: In the product-phase operation, only the $k = \Theta(\log(q/\varepsilon))$ most significant bits of the inputs are used, where $\varepsilon$ is the approximation error.
Base Cases: The recursion stops when a register size is at most $2k$ . Instead of using the standard Cleve-Watrous exact QFT for these base cases (which costs $O(k(\log k)^{\alpha+1})$ ), the authors substitute their improved exact QFT (costing $O(k(\log k)^\alpha)$ ).
Rotation Approximation: Since the improved exact QFT relies on the non-standard rotation $B(\theta_q)$ , the authors show that for the approximate case, these rotations can be efficiently approximated using standard phase gates $P(2\pi a/2^d)$ without increasing the asymptotic gate count or auxiliary space. Consequently, the final construction for the $\varepsilon$ -approximate QFT uses the same gate set as Cleve and Watrous (Hadamard, controlled-NOT, and exact phase gates).

Key Contributions and Results

1. Improved Gate Complexity

The primary contribution is a reduction in the asymptotic gate count for both exact and approximate QFTs, directly linking them to the complexity of integer multiplication $M(n) = O(n(\log n)^\alpha)$ .

Exact QFT (Theorem 1.1): The authors construct an exact QFT on $q$ $q$ qubits using $O(q(\log q)^\alpha)$ gates. This improves upon the previous best bound of $O(q(\log q)^{\alpha+1})$ $O (q (lo g q)^{α + 1})$ by Cleve and Watrous.
- Note: This construction requires an additional single-qubit rotation $B(\theta_q)$ dependent on $q$ .
Approximate QFT (Theorem 1.2): For an approximation error $\varepsilon$ $ε$ , the authors construct a circuit using $O(q(\log \log(q/\varepsilon))^\alpha)$ gates. This improves upon the previous bound of $O(q(\log \log(q/\varepsilon))^{\alpha+1})$ $O (q (lo g lo g (q / ε))^{α + 1})$ by Ahokas, Cleve, and Hales.
- Note: This construction uses the same gate set as Cleve and Watrous (Hadamard, controlled-NOT, and exact phase gates) by approximating the necessary rotations.

2. Implications of Recent Multiplication Claims

The paper highlights the potential impact of a recent claim by OpenAI regarding integer multiplication with complexity $O(n(\log n)^{1-\kappa})$ for a constant $0 < \kappa < 1$ .

If this claim holds for Boolean circuits, setting $\alpha = 1-\kappa$ yields an exact QFT with $o(q \log q)$ gates and an approximate QFT with $o(q \log \log q)$ gates.
This suggests a path toward QFT circuits that are significantly more efficient than the standard $O(q^2)$ or even the $O(q \log q)$ bounds previously thought achievable without such multiplication advances.

3. Resource Bounds

Auxiliary Qubits: The exact construction uses $O(a(q) + M(q))$ auxiliary qubits (where $a(q)$ is the auxiliary count of the approximate circuit). The approximate construction uses $O(L(\log L)^\alpha)$ auxiliary qubits, where $L = \log(q/\varepsilon)$ .
Uniformity: The authors explicitly state that their circuit families are non-uniform. This is because the angle $\theta_q$ for the rotation $B(\theta_q)$ cannot currently be computed efficiently by a classical algorithm. They identify the efficient generation of these angles as a natural open question.

Significance and Claims

The paper claims to tighten the theoretical connection between the cost of integer multiplication and the cost of the Quantum Fourier Transform. By removing an extra logarithmic factor in the gate complexity, the authors demonstrate that the QFT can be made nearly as efficient as the underlying multiplication algorithm.

The authors are modest regarding the uniformity of their circuits, acknowledging that the dependence on a specific rotation angle prevents the construction from being uniform in the current state of knowledge. They also reiterate the open problem posed by Aaronson (2025) regarding whether an exact QFT on $q$ qubits can be implemented with $O(q)$ gates, noting that their results improve the exponent but do not yet reach linear size.

The work does not propose new experimental implementations or specific applications beyond the general utility of QFT in algorithms like Shor's and phase estimation. Instead, it focuses on the theoretical circuit complexity bounds, offering a refined construction that leverages recent advances in classical integer multiplication to reduce quantum gate overhead.