Timothy Boykett, Jarkko Kari, Ville Salo,
"Finite generating sets for reversible gate sets under general conservation laws"
, in Theoretical Computer Science, Vol. 701, Seite(n) 27-39, 2017, ISSN: 0304-3975
Original Titel:
Finite generating sets for reversible gate sets under general conservation laws
Sprache des Titels:
Englisch
Original Kurzfassung:
It is well-known that the Toffoli gate and the negation gate together yield a universal gate set, in the sense that every even permutation of $\{0,1\}^n$ can be implemented as a composition of these gates. An analogous result holds also on non-binary logic: For any finite set $A$, a finite set of reversible gates can generate all even permutations of $A^n$ for all $n$. This means that a finite gate set can generate all permutations of $A^n$ when the cardinality of $A$ is odd, and that one auxiliary ''borrowed" symbol is necessary and sufficient to obtain all permutations when the cardinality of $A$ is even. We 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 or, more generally, the image of the word under a fixed monoid homomorphism from $A^*$ to a commutative monoid. It turns out that no finite conservative gate set can, for all $n$, implement all conservative even permutations of $A^n$ without borrowed symbols. But we provide a finite gate set that can implement all those conservative permutations that are even within each weight class of $A^n$.