Metraipolis › archive › dc_da2d7ccef8ce

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication — arXiv:2611.06341

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.06341
License (as archived)
CC0-1.0
Archived
2026-11-05T18:32:05.587Z
SHA-256 of the archived text
0a565e50d3d6736aeab8243f65dfcdd92965715e2dcf304c134085f6293bb5b6
Stable URL of this page
https://metraipolis.com/documento/dc_da2d7ccef8ce

How to cite

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication — arXiv:2611.06341 — arXiv (en), https://arxiv.org/abs/2611.06341 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_da2d7ccef8ce (Metraipolis archive dc_da2d7ccef8ce, sha256 0a565e50d3d6736aeab8243f65dfcdd92965715e2dcf304c134085f6293bb5b6)
BibTeX
@misc{dcda2d7ccef8ce,
  title = {Improved Exact and Approximate Quantum Fourier Transforms from Multiplication — arXiv:2611.06341},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06341},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_da2d7ccef8ce; sha256 0a565e50d3d6736aeab8243f65dfcdd92965715e2dcf304c134085f6293bb5b6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06341. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathbb{F}_{2^q}$. Cleve and Watrous (FOCS 2000) improved this gate count to $O(q (\log q)^2 (\log \log q))$ using the integer multiplication algorithm in $O(n (\log n) (\log \log n))$ time for two $n$-bit integers (best known at that time). Our first main result shows that this gate count can be improved to $O(q (\log q))$. In fact, if there is a multiplication circuit, to multiply two $n$-bit integers, with $O(n (\log n)^{\alpha})$ gates; we get a QFT circuit with $O(q (\log q)^{\alpha})$ gates (improving upon $O(q (\log q)^{\alpha + 1})$) 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 $o \left( q (\log q)\right)$ 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 $O \left( q (\log \log(q/\varepsilon))^{\alpha+1} \right)$ gates, where $\epsilon$ is the approximating parameter. Our second main result again improves this to $O \left( q (\log \log(q/\varepsilon))^{\alpha} \right)$ gates.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.06341 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:34.066Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).