Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2501.12414 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915144272969728 |
|---|---|
| author | Shah, Ronit |
| author_facet | Shah, Ronit |
| contents | We present an asymptotically improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. Historically, the approximate QFT has been implemented in $Θ(n \log n)$ gates, and the exact in $Θ(n^2)$ gates. In this work, we show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits. Specifically, our approach yields an $Θ(n(\log \log n)^2)$ algorithm for the approximate QFT using $Θ(\log n)$ ancillas, and an $Θ(n(\log n)^2)$ algorithm for the exact QFT requiring $Θ(n)$ ancillas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12414 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Faster Quantum Fourier Transform Shah, Ronit Quantum Physics We present an asymptotically improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. Historically, the approximate QFT has been implemented in $Θ(n \log n)$ gates, and the exact in $Θ(n^2)$ gates. In this work, we show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits. Specifically, our approach yields an $Θ(n(\log \log n)^2)$ algorithm for the approximate QFT using $Θ(\log n)$ ancillas, and an $Θ(n(\log n)^2)$ algorithm for the exact QFT requiring $Θ(n)$ ancillas. |
| title | A Faster Quantum Fourier Transform |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2501.12414 |