A logarithmic-depth quantum carry-lookahead adder

Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, Krysta M. Svore · 2004 · Quantum Inf. Comput. 6(4-5):351-369

| 编号 QA003 | 主题 加法与减法 | 链接 arXiv:quant-ph/0406142 |

摘要

摘要保留原文（英文）

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

We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in $O(\log n)$ depth using $O(n)$ ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo $2^n$ and modulo $2^n-1$. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor’s algorithm.

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