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 · arXiv 预印本

| 编号 QQFT022 | 主题 量子傅里叶变换 | 链接 arXiv:2505.00701 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such “optimistic quantum circuits” are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth $O(\log (n/ϵ))$ for tunable error parameter $ϵ$, uses $n$ total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit’s error is bounded by $ϵ$ on all input states except an $O(ϵ)$-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions, the optimistic QFT yields factoring circuits of nearly linear depth using only $2n+O(n/\log n)$ total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of $O(\log (n/ϵ))$ with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.

读法提示

这条结果与本站近似与截断 QFT词条讨论的”逐门截断”是不同的路线：它不是砍掉小角度受控相位，而是放宽误差的定义（只在绝大部分输入上正确），因此”乐观电路”一词里的”乐观”有确切含义。另注意末句：把乐观线路还原成全输入近似的归约要用长程门，但不用测量。

本站词条在引用该文献时，会以 wikilink（sources/QQFT022）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。