Ricercar: a language for describing and rewriting reversible circuits with ancillae and its permutation semantics
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Ricercar : a language for describing and rewriting reversible circuits with ancillae and its permutation semantics. / Thomsen, Michael Kirkedal; Kaarsgaard, Robin; Soeken, Mathias.
Reversible Computation: 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings. red. / Jean Krivine; Jean-Bernard Stefani. Springer, 2015. s. 200-215 (Lecture notes in computer science, Bind 9138).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Ricercar
T2 - 7th International Conference on Reversible Computation, RC 2015
AU - Thomsen, Michael Kirkedal
AU - Kaarsgaard, Robin
AU - Soeken, Mathias
PY - 2015
Y1 - 2015
N2 - Previously, Soeken and Thomsen presented six basic semantics-preserving rules for rewriting reversible logic circuits, defined using the well-known diagrammatic notation of Feynman. While this notation is both useful and intuitive for describing reversible circuits, its shortcomings in generality complicates the specification of more sophisticated and abstract rewriting rules. In this paper, we introduce Ricercar, a general textual description language for reversible logic circuits designed explicitly to support rewriting. Taking the not gate and the identity gate as primitives, this language allows circuits to be constructed using control gates, sequential composition, and ancillae, through a notion of ancilla scope. We show how the above-mentioned rewriting rules are defined in this language, and extend the rewriting system with five additional rules to introduce and modify ancilla scope. This treatment of ancillae addresses the limitations of the original rewriting system in rewriting circuits with ancillae in the general case. To set Ricercar on a theoretical foundation, we also define a permutation semantics over symmetric groups and show how the operations over permutations as transposition relate to the semantics of the language.
AB - Previously, Soeken and Thomsen presented six basic semantics-preserving rules for rewriting reversible logic circuits, defined using the well-known diagrammatic notation of Feynman. While this notation is both useful and intuitive for describing reversible circuits, its shortcomings in generality complicates the specification of more sophisticated and abstract rewriting rules. In this paper, we introduce Ricercar, a general textual description language for reversible logic circuits designed explicitly to support rewriting. Taking the not gate and the identity gate as primitives, this language allows circuits to be constructed using control gates, sequential composition, and ancillae, through a notion of ancilla scope. We show how the above-mentioned rewriting rules are defined in this language, and extend the rewriting system with five additional rules to introduce and modify ancilla scope. This treatment of ancillae addresses the limitations of the original rewriting system in rewriting circuits with ancillae in the general case. To set Ricercar on a theoretical foundation, we also define a permutation semantics over symmetric groups and show how the operations over permutations as transposition relate to the semantics of the language.
KW - Ancillae
KW - Circuit equivalence
KW - Permutation
KW - Reversible logic
KW - Term rewriting
U2 - 10.1007/978-3-319-20860-2_13
DO - 10.1007/978-3-319-20860-2_13
M3 - Article in proceedings
AN - SCOPUS:84949973157
SN - 978-3-319-20859-6
T3 - Lecture notes in computer science
SP - 200
EP - 215
BT - Reversible Computation
A2 - Krivine, Jean
A2 - Stefani, Jean-Bernard
PB - Springer
Y2 - 16 July 2015 through 17 July 2015
ER -
ID: 160017697