A log-depth in-place quantum Fourier transform that rarely needs ancillas
Gregory D. Kahanamoku-Meyer, John Blue, Thiago Bergamaschi, Craig Gidney, Isaac L. Chuang · 2025
Read A log-depth in-place quantum Fourier transform that rarely needs ancillas by Gregory D. Kahanamoku-Meyer, John Blue, Thiago Bergamaschi, Craig Gidney, Isaac L. Chuang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00701.txt.
Description
Gregory Kahanamoku-Meyer and co-authors built a shortcut quantum Fourier transform in a 2025 paper. The transform is a core step in many quantum algorithms, but a full exact circuit is costly. They note that a circuit that is near-exact on most inputs, not all, can be far cheaper to build.
They give that idea a firm frame, calling such circuits optimistic. A fix-up then upgrades an optimistic circuit to a full one for the rare algorithm that needs it. Their transform runs in place with depth that grows as the log of size, and it rarely needs spare qubits. The savings could ease near-term quantum runs.
Catalog record
| CREATOR | Gregory D. Kahanamoku-Meyer, John Blue, Thiago Bergamaschi, Craig Gidney, Isaac L. Chuang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00701