White dots do matter: rewriting reversible logic circuits
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
White dots do matter : rewriting reversible logic circuits. / Soeken, Mathias; Thomsen, Michael Kirkedal.
Reversible Computation: 5th International Conference, RC 2013, Victoria, BC, Canada, July 4-5, 2013. Proceedings. ed. / Gerhard W. Dueck; D. Michael Miller. Springer, 2013. p. 196-208 (Lecture notes in computer science, Vol. 7948).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - White dots do matter
AU - Soeken, Mathias
AU - Thomsen, Michael Kirkedal
N1 - Conference code: 5
PY - 2013
Y1 - 2013
N2 - The increased effort in recent years towards methods for computer aided design of reversible logic circuits has also lead to research in algorithms for optimising the resulting circuits; both with higher-level data structures and directly on the reversible circuits. To obtain structural patterns that can be replaced by a cheaper realisation, many direct algorithms apply so-called moving rules; a simple form of rewrite rules that can only swap gate order.In this paper we first describe the few basic rules that are needed to perform rewriting directly on reversible logic circuits made from general Toffoli circuits. We also show how to use these rules to derive more complex formulas. The major difference compared to existing approaches is the use of negative controls (white dots), which significantly increases the algebraic strength. We show how existing optimisation approaches can be adapted as problems based on our rewrite rules.Finally, we outline a path to generalising the rewrite rules by showing their forms for reversible control-gates. This can be used to expand our method to other gates such as the controlled-swap gate or quantum gates.
AB - The increased effort in recent years towards methods for computer aided design of reversible logic circuits has also lead to research in algorithms for optimising the resulting circuits; both with higher-level data structures and directly on the reversible circuits. To obtain structural patterns that can be replaced by a cheaper realisation, many direct algorithms apply so-called moving rules; a simple form of rewrite rules that can only swap gate order.In this paper we first describe the few basic rules that are needed to perform rewriting directly on reversible logic circuits made from general Toffoli circuits. We also show how to use these rules to derive more complex formulas. The major difference compared to existing approaches is the use of negative controls (white dots), which significantly increases the algebraic strength. We show how existing optimisation approaches can be adapted as problems based on our rewrite rules.Finally, we outline a path to generalising the rewrite rules by showing their forms for reversible control-gates. This can be used to expand our method to other gates such as the controlled-swap gate or quantum gates.
U2 - 10.1007/978-3-642-38986-3_16
DO - 10.1007/978-3-642-38986-3_16
M3 - Article in proceedings
SN - 978-3-642-38985-6
T3 - Lecture notes in computer science
SP - 196
EP - 208
BT - Reversible Computation
A2 - Dueck, Gerhard W.
A2 - Miller, D. Michael
PB - Springer
Y2 - 4 July 2013 through 5 July 2013
ER -
ID: 48909326