Asymptotically Efficient Quantum Karatsuba Multiplication

Craig Gidney · 2019 · arXiv quant-ph

| 编号 QM001 | 主题 模运算与乘法 | 链接 arXiv:1904.07356 |

摘要

摘要保留原文（英文）

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

We improve the space complexity of Karatsuba multiplication on a quantum computer from $O(n^{1.427})$ to $O(n)$ while maintaining $O(n^{\lg 3})$ gate complexity. We achieve this by ensuring recursive calls can add their outputs directly into subsections of the output register. This avoids the need to store, and uncompute, intermediate results. This optimization, which is analogous to classical tail-call optimization, should be applicable to a wide range of recursive quantum algorithms.

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