{"id":"arxiv/2611.06341","url":"https://arxiv.org/abs/2611.06341","tags":["quant-ph","cs.CC"],"score":0,"title":"Improved Exact and Approximate Quantum Fourier Transforms from Multiplication","domain":"quant-ph","source":"arxiv","authors":["Chandrima Kayal","Rajat Mittal","Manaswi Paraashar","Nitin Saurabh"],"reviews":0,"subject":"quant-ph","summary":"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(q^2)$ gates (and $O(q)$ qubits) to perform the exact Fourier transform over…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}