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.