Thumbnail
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

   Open content in new tab
Source: ACM Digital Library