Fast parallel circuits for the quantum Fourier transform

R. Cleve, J. Watrous · 2000 · Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 526–536

| 编号 QQFT010 | 主题 量子傅里叶变换 | 链接 doi:10.1109/SFCS.2000.892140 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。 We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2^n with error bounded by epsilon. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log (n/epsilon)). We also give an upper bound of O(n (log n)^2 log log n) on the circuit size of the exact QFT modulo 2^n, for which the best previous bound was O(n^2). As an application of the above depth bound, we show that Shor’s factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial-size, in combination with classical polynomial-time pre- and post-processing. In the language of computational complexity, this implies that factoring is in the complexity class ZPP^BQNC, where BQNC is the class of problems computable with bounded-error probability by quantum circuits with poly-logarithmic depth and polynomial size. Finally, we prove an Omega(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically optimal (for a reasonable range of values of epsilon).

可确认的信息

标题即结论：为量子傅里叶变换给出快速并行线路。这是”QFT 不必串行执行”的奠基性论证，年代早于本卷收录的所有深度调度类工作。

不要混淆

本页是 Cleve–Watrous 的 FOCS 2000 论文，不是 Beauregard–Brantley–Cleve–Kutin 的”精确 QFT 线路”。后者的编号在本轮检索中未能核实，未收录于本站。

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