Strongly universal reversible gate sets

DOI10.1007/978-3-319-40578-0_18zbMATH Open1384.94143arXiv1602.04967OpenAlexW2962891072WikidataQ62045886 ScholiaQ62045886MaRDI QIDQ3186604FDOQ3186604

Authors: Tim Boykett, Jarkko Kari, Ville Salo 

Publication date: 10 August 2016

Published in: Reversible Computation (Search for Journal in Brave)

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: If $A$ is a finite set of odd cardinality then a finite gate set can generate all permutations of $A^n$ for all $n$, without any auxiliary symbols. If the cardinality of $A$ is even then, by the same argument as above, only even permutations of $A^n$ can be implemented for large $n$, and we show that indeed all even permutations can be obtained from a finite universal gate set. 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$.

Full work available at URL: https://arxiv.org/abs/1602.04967

Recommendations

• Finite generating sets for reversible gate sets under general conservation laws
• The classification of reversible bit operations
• On universality of general reversible multiple-valued logic gates
• Minimal universal library for \(n\times n\) reversible circuits
• Universal gates with wires in a row

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Cites Work

• Conservative logic
• Title not available (Why is that?)
• Towards an algebraic theory of Boolean circuits.
• The classification of reversible bit operations
• Solutions of the compatibility conditions for a Wigner quantum oscillator

Cited In (5)

• Universal groups of cellular automata
• Transitive action on finite points of a full shift and a finitary Ryan’s theorem
• The classification of reversible bit operations
• Finite generating sets for reversible gate sets under general conservation laws
• Universal gates with wires in a row

This page was built for publication: Strongly universal reversible gate sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186604)