Quantum Carry-Save Arithmetic
Quantum Carry-Save Arithmetic
复制标题
量子进位保存算法
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Phil Gossett
中科院分区：
文献类型：
--
作者：
Phil Gossett
本文展示了如何使用从经典计算机设计中借用的“进位保存”技术，从量子门中设计高效的算术元素。这允许对 Shor 算法所需的所有算术元素进行位并行评估，包括模算术，将所有进位传播推迟到整个计算结束。这将量子门延迟从 O(N^3) 减少到 O(N log N)，但代价是将所需的量子位数量从 O(N) 增加到 O(N^2)。
This paper shows how to design efficient arithmetic elements out of quantum gates using "carry-save" techniques borrowed from classical computer design. This allows bit-parallel evaluation of all the arithmetic elements required for Shor's algorithm, including modular arithmetic, deferring all carry propagation until the end of the entire computation. This reduces the quantum gate delay from O(N^3) to O(N log N) at a cost of increasing the number of qubits required from O(N) to O(N^2).