English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It is well-known that the Toffoli gate and the negation gate together yield auniversal gate set, in the sense that every permutation of $\{0,1\}^n$ can beimplemented as a composition of these gates. Since every bit operation thatdoes not use all of the bits performs an even permutation, we need to use atleast one auxiliary bit to perform every permutation, and it is known that onebit is indeed enough. Without auxiliary bits, all even permutations can beimplemented. We generalize these results to non-binary logic: For any finiteset $A$, a finite gate set can generate all even permutations of $A^n$ for all$n$, without any auxiliary symbols. This directly implies the previouslypublished 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 necessaryand 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 thatrecords how many times each symbol occurs in the word or, more generally, theimage of the word under a fixed monoid homomorphism from $A^*$ to a commutativemonoid. 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 conservativepermutations that are even within each weight class of $A^n$.

Finite generating sets for reversible gate sets under general conservation laws