Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 10, 2017 | Submitted
Report Open

A logarithmic-depth quantum carry-lookahead adder

Abstract

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 2^n and modulo 2^n - 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.

Attached Files

Submitted - 0406142.pdf

Files

0406142.pdf
Files (233.6 kB)
Name Size Download all
md5:585686bc774b735a7302acc853951653
233.6 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
March 5, 2024