Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
A Logarithmic-depth Quantum Carry-Lookahead Adder

Tom Draper, Samuel Kutin, Eric Rains, and Krysta M. Svore

Abstract

We present an efficient addition circuit, borrowing techniques from the classical carry look-ahead arithmetic circuit. Our quantum carrylookahead (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.

Details

Publication typeArticle
Published inQuantum Information and Computation
Pages351-369
Volume6
Number4-5
PublisherRinton Press
> Publications > A Logarithmic-depth Quantum Carry-Lookahead Adder