×

Exploiting negative control lines in the optimization of reversible circuits. (English) Zbl 1406.68024

Dueck, Gerhard W. (ed.) et al., Reversible computation. 5th international conference, RC 2013, Victoria, BC, Canada, July 4–5, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38985-6/pbk). Lecture Notes in Computer Science 7948, 209-220 (2013).
Summary: The development of approaches for synthesis and optimization of reversible circuits received significant attention in the past. This is partly due to the increasing emphasis on low power design methodologies, and partly motivated by recent works in quantum computation. While most of them relied on a gate library composed of multiple-control Toffoli (MCT) gates with positive control lines, some initial works also exist which additionally incorporate negative control lines. This usually leads to smaller circuits with respect to the number of gates as well as the corresponding quantum costs. However, despite these benefits, negative control lines have hardly been considered in post-synthesis optimization of reversible circuits so far. In this paper, we address this issue. We are presenting an optimization scheme inspired by template matching which explicitly makes use of negative control lines. Experimental evaluations demonstrate that exploiting negative control lines in fact lead to a reduction in the number of gates and the quantum costs by up to 60% and 25%, respectively.
For the entire collection see [Zbl 1277.68008].

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
81P68 Quantum computation
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Software:

RevKit; RevLib
PDFBibTeX XMLCite
Full Text: DOI