Quantum Addition Circuits and Unbounded Fan-Out

Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro · 2009 · Quantum Inf. Comput. 10(9-10):0872-0890

| 编号 QA006 | 主题 加法与减法 | 链接 arXiv:0910.2530 |

摘要

摘要保留原文（英文）

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

We first show how to construct an $O(n)$-depth $O(n)$-size quantum circuit for addition of two n-bit binary numbers with no ancillary qubits. The exact size is $7n-6$, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an $O(d(n))$-depth $O(n)$-size quantum circuit for addition with $O(n/d(n))$ ancillary qubits for any $d(n)=\Omega (\log n)$. If we are allowed to use unbounded fan-out gates with length $O(n^c)$ for an arbitrary small positive constant $c$, we can modify the method and construct an $O(e(n))$-depth $O(n)$-size circuit with $o(n)$ ancillary qubits for any $e(n)=\Omega ({\log }^{\ast }n)$. In particular, these methods yield efficient circuits with depth $O(\log n)$ and with depth $O({\log }^{\ast }n)$, respectively. We apply our circuits to constructing efficient quantum circuits for Shor’s discrete logarithm algorithm.

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