  Most of the work on implementing arithmetic on a quantum computer has
borrowed from results in classical reversible computing (e.g. [VBE95], [BBF02],
[DKR04]). These quantum networks are inherently classical, as they can be
implemented with only the Toffoli gate. Draper [D00] has proposed an inherently
"quantum" network for addition based on the quantum Fourier transform. His
approach has the advantage that it requires no carry qubits (the previous
approaches required O(n) carry qubits). The network in [D00] uses quantum
rotation gates, which must either be implemented with exponential precision, or
else be approximated. In this paper I give a network of O(n^3) Toffoli gates
for reversibly performing in-place addition with only a single ancillary bit,
demonstrating that inherently quantum techniques are not required to achieve
this goal (provided we are willing to sacrifice quadratic circuit depth). After
posting the original version of this note it was pointed out to me by C. Zalka
that essentially the same technique for addition was used in [BCD+96]. The
scenario in that paper was different, but it is clear how the technique they
described generalizes to that in this paper.
