### Garbage-Free Reversible Multipliers for Arbitrary ConstantsGarbage-Free Reversible Multipliers for Arbitrary Constants

Access Restriction
Subscribed

 Author Mogensen, Torben gidius Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Reversible logic ♦ Constant multiplication Abstract 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 $\textit{n}$ is the number of bits in the constant. These gates will have $O(\textit{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}).$ For some interesting cases, the cost can be reduced to $O(\textit{n})$ gates per bit-slice, reducing the cost to $O(n^{2})$ transistors per bit slice. The quantum cost is still $O(2^{n}),$ as the remaining gates have $O(\textit{n})$ inputs. We also look at an alternative construction that, at the cost of adding $O(\textit{n})$ ancillae, reduces the cost for arbitrary constants to $O(\textit{n})$ gates, $O(n^{2})$ transistors, though still with $O(2^{n})$ quantum cost. ISSN 15504832 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-11-01 Publisher Place New York e-ISSN 15504840 Journal ACM Journal on Emerging Technologies in Computing Systems (JETC) Volume Number 11 Issue Number 2 Page Count 18 Starting Page 1 Ending Page 18

#### Open content in new tab

Source: ACM Digital Library