Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics

Michael Kirkedal Thomsen, Robin Kaarsgaard, Mathias Soeken

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.

Original languageEnglish
Title of host publicationReversible Computation - 7th International Conference, RC 2015, Proceedings
EditorsJean Krivine, Jean-Bernard Stefani
Publication date2015
ISBN (Print)9783319208596
Publication statusPublished - 2015

Bibliographical note

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.


  • Ancillae
  • Circuit equivalence
  • Permutation
  • Reversible logic
  • Term rewriting


Dive into the research topics of 'Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics'. Together they form a unique fingerprint.

Cite this