Chandrima Kayal of Université Paris Cité, CNRS, and colleagues have established a new upper bound of O(q( log q)) gates for an exact quantum Fourier transform (QFT) circuit. This improves upon the O(q( log q)^2( log log q)) gate count achieved by Cleve and Watrous in 2000.

The work demonstrates that further gains are possible; if OpenAI’s recent claims regarding integer multiplication hold true, a QFT circuit with fewer than O(q( log q)) gates may be achievable. Researchers also refined the best known gate count for approximating the QFT over Z/(2^qZ) to O(q( log log(q/ε))^α) gates, where ε is the approximation parameter.

Multiplying Integers Reduces QFT Gate Complexity

This approach allows for a streamlined QFT circuit, contingent on the efficiency of the underlying multiplication process. The relationship between integer multiplication complexity and QFT gate counts is direct; a multiplication circuit capable of multiplying two n-bit integers with O(n( log n)^α) gates yields a QFT circuit with O(q( log q)^α) gates, improving upon the previous O(q( log q)^(α + 1)) gate requirement. This scaling is particularly relevant given recent developments in classical computation, specifically a claim by OpenAI regarding a more efficient integer multiplication algorithm.

If OpenAI’s algorithm proves effective, it could potentially push the QFT gate count below O(q( log q)), achieving a circuit with o(q( log q)) gates. Beyond exact calculations, this work also informs the construction of approximate QFT circuits.

The new findings demonstrate a reduction in workspace requirements, as the intermediate product of multiplication does not need to be stored in an ancillary register before phase application and uncomputation. “There are at most q base-case calls, so replacing them one at a time gives ‖U_0-U_0‖ ≤ 12π q2^(-k),” the paper states, detailing the mathematical basis for this optimization. Further research aims to achieve the same gate bounds using only Hadamard, controlled-NOT and specific phase gates, potentially simplifying the circuit even further.

Cleve and Watrous’s QFT Construction via Integer Multiplication

The work builds on the 2003 findings of Ahokas, Cleve and Hales, who demonstrated an approximate QFT circuit with O(q( log log(q/ε))^(α + 1)) gates, where ε represents the approximation error. Their first main result shows that this gate count can be improved to O(q( log q)). Their second main result again improves to O(q( log log(q/ε))^α) gates.

QFT Circuit Depth Improvement to O(q log q)^α

The construction of an exact Quantum Fourier Transform (QFT) now requires O(q( log q)^α) gates, a reduction achieved by linking circuit complexity directly to the efficiency of integer multiplication. This improvement, detailed in recent work, builds upon a prior approach that relied on O(M(q)) gates, where M(q) represents the computational cost of multiplying two q-bit integers. By applying this relationship, researchers have effectively lowered the barrier to implementing QFTs for larger qubit numbers.

This advance stems from a refined application of a 2003 approximate QFT circuit developed by Ahokas, Cleve and Hales. This represents a significant optimization over the O(q( log q)^(α + 1)) gate count previously achievable using the original Cleve and Watrous construction. The resulting exact QFT circuit uses O(q( log q)^α) gates and auxiliary qubits, with all auxiliary qubits returning to zero. The work also addresses the implications for approximate QFT circuits.

This gate count represents a refinement over previous constructions, specifically those originating with Cleve and Watrous, and relies on a multiplication circuit to perform the calculation. The work hinges on the assumption that the multiplication circuit is efficient, and the researchers established a bound for approximate QFT implementations.

Impact of OpenAI’s Integer Multiplication Claim

The potential for significantly faster quantum computations moved closer to reality with a newly established link between integer multiplication efficiency and the speed of Quantum Fourier Transforms (QFT). This advance is predicated on the existence of an efficient multiplication circuit, and is now further energized by a recent claim from OpenAI regarding integer multiplication algorithms. Their second main result again improves the established result of Ahokas, Cleve and Hales to O(q( log log(q/ε))^α) gates.

Coppersmith’s Initial Exact and Approximate QFT Circuits

The team’s approach involves using an approximate inverse QFT. Applying Lemma 3, the construction of this exact QFT relies on a single-qubit rotation gate, the angle of which depends on the input size q, to the gate set used by Cleve and Watrous.

A key question remains regarding the efficient generation of these circuits; if multiplication circuits can be generated in classical polynomial time, determining whether the additional rotation angle can be approximated to additive error $2^{- d}$ by a classical algorithm running in time polynomial in q and d would further validate the approach. The team acknowledges that establishing uniformity of these circuit families remains an open area of investigation, but the current results demonstrate a clear path toward more efficient QFT implementations.

QFT Applications in Shor’s Algorithm and Phase Estimation

The efficiency of quantum computation hinges on minimizing the gate count required for core algorithms, and recent work demonstrates a reduction in the number of gates needed for the Quantum Fourier Transform (QFT). This relationship between multiplication and the QFT extends to approximate calculations as well. This builds upon earlier work from Ahokas, Cleve and Hales, but the new findings suggest a path toward even greater speedups.

The implications of these findings are significant for algorithms like Shor’s, which relies heavily on the QFT for factoring and discrete logarithm problems, and for quantum phase estimation, a subroutine used in various quantum algorithms. While the current construction of these optimized circuits is non-uniform, meaning the angle of a single-qubit rotation gate cannot yet be efficiently computed classically, the theoretical groundwork has been laid for further refinement.

Approaches to QFT also focus on reducing gate counts through approximation, accepting a controlled error rate in exchange for computational speed. The presence of this gate prevents them from demonstrating that their circuit families are uniform.

👉 More information
🗞 Improved Exact and Approximate Quantum Fourier Transforms from Multiplication
✍️ Chandrima Kayal, Rajat Mittal, Manaswi Paraashar and Nitin Saurabh
🧠 ArXiv: https://arxiv.org/abs/2611.06341

More like this