Ancilla-free Quantum Adder with Sublinear Depth

Maxime Remaud, Vivien Vandaele · 2025 · RC 2025, LNCS 15716

| 编号 QA011 | 主题 加法与减法 | 链接 arXiv:2501.16802 |

摘要

摘要保留原文（英文）

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

We present the first exact quantum adder with sublinear depth and no ancilla qubits. Our construction is based on classical reversible logic only and employs low-depth implementations for the CNOT ladder operator and the Toffoli ladder operator, two key components to perform ripple-carry addition. Namely, we demonstrate that any ladder of $n$ CNOT gates can be replaced by a CNOT-circuit with $O(\log n)$ depth, while maintaining a linear number of gates. We then generalize this construction to Toffoli gates and demonstrate that any ladder of $n$ Toffoli gates can be substituted with a circuit with $O({\log }^{2}n)$ depth while utilizing a linearithmic number of gates. This builds on the recent works of Nie et al. and Khattar and Gidney on the technique of conditionally clean ancillae. By combining these two key elements, we present a novel approach to design quantum adders that can perform the addition of two $n$-bit numbers in depth $O({\log }^{2}n)$ without the use of any ancilla and using classical reversible logic only (Toffoli, CNOT and X gates). We also present new constructions for incrementing and adding a constant to a quantum register.

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