Mog18: Toben AEgidius Mogensen. Garbage-Free Reversible Multiplication and Division

• in {lit+ textvar Lit.Lit$:RC18 is undefined or empty}
• Garbage-Free: only forgetting a bit needs energy (Landauers Principle). Thus, don't forget intermediate results, but uncompute them to zero
• garbage-bit: a bit that is computed but not in the final output
• ancilla-bit: a bit with know initial state (for intermediate results). Must be uncomputed to the inital state, otherwise they are garbage!
• additional benefit, that running the circuit reverse, will do the inverse function (because it does not depend on intermediate results!)
• what is the reversible multiplication function
  • (a, b) → a*b is not reversible
  • (a, b) → (a, a*b) is reversible, but reverse computation needs the prerquisite l divides l*r
  • (a, b, r) → (a, a*b+r) with r < a has the reverse (a, p) ==> (a, p div a, p mod a) is used here

using faster components

• log-depth carry-lookahead adder {lit+ textvar Lit.Lit$:DKR06 is undefined or empty} described & implemented Adder