2004/06/20 by Thomas G. Draper, Samuel A. Kutin, Eric M. Rains +1 · 3 citations
Physics and Astronomy · #quant-ph
published as Quant. Inf. Comp. Vol. 6, No. 4-5, pp. 351-369 (2006) · 21 pages, 4 color figures
arxiv created 2004/06/20 · arxiv updated 2013/04/03
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2n and modulo 2n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.