Linear-size exact quantum Fourier transform
- Field
- Topic
Problem
Can the exact quantum Fourier transform on \(n\) qubits be implemented with \(O(n)\) one- and two-qubit gates?
Define
Let \(C_{\mathrm{exact}}(n)\) be the minimum size of a uniform circuit that implements the unitary in Eq. (1) exactly on arbitrary inputs. Gates may be arbitrary efficiently specified one- or two-qubit unitaries; clean ancillas may be used but must be restored, and all gates on them count. Is
The target in Eq. (2) concerns exact coherent implementation, not approximate QFT or sampling only.
Source
Aaronson explicitly asks the linear-size exact-QFT question in the cited author-written discussion [Aaronson25]. Cleve and Watrous and Kahanamoku–Meyer and Yao supply the formal circuit results [Cleve00][KMY24].
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
Cleve and Watrous obtained an exact QFT of size \(O(n\log^2 n\log\log n)\) in 2000, together with efficient approximate parallel constructions. Their exact construction uses recursive Fourier transforms and fast multiplication. Thus a subquadratic exact QFT has long been known. [Cleve00]
Kahanamoku–Meyer and Yao subsequently constructed zero-ancilla exact QFT circuits of size \(O\!\left(n^{\log_k(2k-1)}\right)\) for every fixed integer \(k\geq2\). Since \(\log_k(2k-1)\) approaches \(1\) as \(k\) grows, this gives size \(O(n^{1+\varepsilon})\) for every fixed \(\varepsilon>0\). It does not give a single uniform \(O(n)\) construction. [KMY24]
Aaronson explicitly raised the \(O(n)\) exact-size question in January 2025. The construction above improves the upper bound for zero-ancilla exact QFT, but the linear target remains unresolved. [Aaronson25]
Shah withdrew A Faster Quantum Fourier Transform in February 2025 because of lack of novelty. The withdrawal does not bear on whether linear exact size is possible. [Shah25]
Fault-tolerant and architectural results use different metrics. Nam, Su, and Maslov obtained an approximate QFT with \(O(n\log n)\) \(T\) gates, while Lopes studies QFT execution using phase-gradient resources, surface codes, and resource routing. Neither establishes linear exact coherent circuit size in the model above. [Nam20][Lopes26]
Comment
This is a literature-explicit circuit-complexity question. The known exact upper bound is \(O(n^{1+\varepsilon})\) for every fixed \(\varepsilon>0\), whereas no superlinear lower bound is known in the stated arbitrary-gate model. Exact coherent QFT computation is stronger than what bounded-error factoring needs. A resolution must therefore either improve the family of \(O(n^{1+\varepsilon})\) upper bounds to \(O(n)\) or prove that some superlinear growth is unavoidable.
References
- [Cleve00]
- Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. FOCS 2000; See Theorem 2 and the exact-construction recurrence.arXiv
- [KMY24]
- Gregory D. Kahanamoku–Meyer and Norman Y. Yao, Fast quantum integer multiplication with zero ancillas, arXiv:2403.18006v4 (14 November 2024). See the exact QFT construction and its \(O(n^{1+\varepsilon})\) consequence.arXiv
- [Aaronson25]
- Scott Aaronson. Author-written QFT discussion dated January 23, 2025, with subsequent corrections and comments by Richard Cleve. Used for the explicit open question and corrected historical attribution, not as a replacement for [Cleve00].link
- [Shah25]
- Ronit Shah. A Faster Quantum Fourier Transform. withdrawn February 10, 2025 for lack of novelty.arXiv
- [Nam20]
- Yunseong Nam, Yuan Su, and Dmitri Maslov. Approximate Quantum Fourier Transform with \(O(n\log(n))\) T gates. npj Quantum Information 6, 26 (2020).link