Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele · 2026 · arXiv

| 编号 QA012 | 主题 加法与减法 | 链接 arXiv:2603.12917 |

摘要

摘要保留原文（英文）

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

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $\Theta (n)$ and depth of $\Theta (\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor’s factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2{\log }^{2}n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

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