A4 Refereed article in a conference publication

Strongly Universal Reversible Gate Sets




AuthorsBoykett T, Kari J, Salo V

EditorsSimon Devitt, Ivan Lanese

Conference nameInternational Conference on Reversible Computation

PublisherSPRINGER INT PUBLISHING AG, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

Publication year2016

Book title Reversible Computation: 8th International Conference, RC 2016, Bologna, Italy, July 7-8, 2016, Proceedings

Journal name in sourceREVERSIBLE COMPUTATION, RC 2016

Journal acronymLECT NOTES COMPUT SC

Series titleLecture Notes in Computer Science

Volume9720

First page 239

Last page254

Number of pages16

ISBN978-3-319-40577-3

eISBN978-3-319-40578-0

ISSN0302-9743

DOIhttps://doi.org/10.1007/978-3-319-40578-0_18(external)

Web address http://link.springer.com/chapter/10.1007/978-3-319-40578-0_18(external)

Self-archived copy’s web addresshttps://arxiv.org/abs/1602.04967(external)


Abstract
It is well-known that the Toffoli gate and the negation gate together yield a universal gate set, in the sense that every permutation of {0, 1}(n) can be implemented as a composition of these gates. Since every bit operation that does not use all of the bits performs an even permutation, we need to use at least one auxiliary bit to perform every permutation, and it is known that one bit is indeed enough. Without auxiliary bits, all even permutations can be implemented. We generalize these results to non-binary logic: For any finite set A, a finite gate set can generate all even permutations of A(n) for all n, without any auxiliary symbols. This directly implies the previously published result that a finite gate set can generate all permutations of A(n) when the cardinality of A is odd, and that one auxiliary symbol is necessary and sufficient to obtain all permutations when the cardinality of A is even. We also consider the conservative case, that is, those permutations of A(n) that preserve the weight of the input word. The weight is the vector that records how many times each symbol occurs in the word. It turns out that no finite conservative gate set can, for all n, implement all conservative even permutations of A(n) without auxiliary bits. But we provide a finite gate set that can implement all those conservative permutations that are even within each weight class of A(n).



Last updated on 2024-26-11 at 21:18