Garbage-free reversible multipliers for arbitrary constants

TY - JOUR

T1 - Garbage-free reversible multipliers for arbitrary constants

AU - Mogensen, Torben Ægidius

PY - 2014/10/1

Y1 - 2014/10/1

N2 - 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(n2) multi-control Toffoli gates per bit-slice, where nis 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(n3) transistors per bit slice, and the quantum cost (which is exponential in the number of inputs to a Toffoli gate) is O(2n). For some interesting cases, the cost can be reduced to O(n) gates per bit-slice, reducing the cost to O(n2) transistors per bit slice. The quantum cost is still O(2n), as the remaining gates have O(n) inputs. We also look at an alternative construction that, at the cost of adding O(n) ancillae, reduces the cost for arbitrary constants to O(n) gates, O(n2) transistors, though still with O(2n) quantum cost.

AB - 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(n2) multi-control Toffoli gates per bit-slice, where nis 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(n3) transistors per bit slice, and the quantum cost (which is exponential in the number of inputs to a Toffoli gate) is O(2n). For some interesting cases, the cost can be reduced to O(n) gates per bit-slice, reducing the cost to O(n2) transistors per bit slice. The quantum cost is still O(2n), as the remaining gates have O(n) inputs. We also look at an alternative construction that, at the cost of adding O(n) ancillae, reduces the cost for arbitrary constants to O(n) gates, O(n2) transistors, though still with O(2n) quantum cost.

U2 - 10.1145/2629515

DO - 10.1145/2629515

M3 - Journal article

SN - 1550-4832

VL - 11

JO - ACM Journal on Emerging Technologies in Computing Systems

JF - ACM Journal on Emerging Technologies in Computing Systems

IS - 2

M1 - 12

ER -