@inproceedings{a2856ac95ee94d6b84c3a311ebaf7027,
title = "Ricercar: a language for describing and rewriting reversible circuits with ancillae and its permutation semantics",
abstract = "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.",
keywords = "Ancillae, Circuit equivalence, Permutation, Reversible logic, Term rewriting",
author = "Thomsen, {Michael Kirkedal} and Robin Kaarsgaard and Mathias Soeken",
year = "2015",
doi = "10.1007/978-3-319-20860-2_13",
language = "English",
isbn = "978-3-319-20859-6",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "200--215",
editor = "Jean Krivine and Jean-Bernard Stefani",
booktitle = "Reversible Computation",
note = "7th International Conference on Reversible Computation, RC 2015 ; Conference date: 16-07-2015 Through 17-07-2015",
}