We present a method based on Mealy machines for constructing reversible circuitry for multiplying integers by arbitrary integer constants. The circuits generate no garbage and use no ancillae. The circuits are quite compact for small constants and are, in the worst case, bounded by O(n(2)) multi-control Toffoli gates per bit-slice, where n is the number of bits in the constant. These gates will have O(n) inputs, so the total number of pass-transistors needed to implement the circuit is O(n(3)) transistors per bit slice, and the quantum cost (which is exponential in the number of inputs to a Toffoli gate) is O(2(n)).
展开▼
