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

  • in RC18
  • 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 DKR06 described & implemented Adder