Reversible Logic Synthesis Benchmarks Page

you are in... Main\adders

Function nbitadder has 2n inputs and n+1 outputs. Its input is a set of two integer numbers A and B written in binary. Its output is the sum A+B.

nbitadders are particularly relevant for quantum computation. Most importantly, they are used in the modular exponentiation part of Shor's integer factoring algorithm. Due to the efficiency of the quantum Fourier transform, complexity of the modular exponentiation defines the overall complexity of the Shor's integer factoring algorithm.

nbitadders are closely related to modulo adders. ModNadder could be used to find the integer sum as long as it is less than N-1. For instance, using the modNadder circuit it is possible to add integer numbers with [log (N/2)] digits. Conversely, an nbitadder could be adapted to act as a mod2kadder as long as k<n.