Halving the cost of quantum addition

Craig Gidney · 2017（期刊 2018）· Quantum 2, 74

| 编号 QQFT025 | 主题 量子傅里叶变换 | 链接 arXiv:1709.06648 |

摘要

摘要保留原文（英文）

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

We improve the number of T gates needed to perform an n-bit adder from $8n+O(1)$ to $4n+O(1)$. We do so via a “temporary logical-AND” construction which uses four T gates to store the logical-AND of two qubits into an ancilla and zero T gates to later erase the ancilla. This construction is equivalent to one by Jones, except that our framing makes it clear that the technique is far more widely applicable than previously realized. Temporary logical-ANDs can be applied to integer arithmetic, modular arithmetic, rotation synthesis, the quantum Fourier transform, Shor’s algorithm, Grover oracles, and many other circuits. Because T gates dominate the cost of quantum computation based on the surface code, and temporary logical-ANDs are widely applicable, this represents a significant reduction in projected costs of quantum computation. In addition to our n-bit adder, we present an n-bit controlled adder circuit with T-count of $8n+O(1)$, a temporary adder that can be computed for the same cost as the normal adder but whose result can be kept until it is later uncomputed without using T gates, and discuss some other constructions whose T-count is improved by the temporary logical-AND.

读法提示

摘要在两处显式提到 QFT：一是把临时逻辑 AND 列为可适用于”rotation synthesis、the quantum Fourier transform、Shor’s algorithm”的通用技术；二是指出临时加法器的结果可以先保留、之后再零 T 门反计算。这一点对 QFT 尤其重要，因为 QFT 的结构里反复出现”算出来再拆掉”的中间态。

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