2016/11/04 by Tim Boykett, Boykett, Tim, Jarkko Kari +3
Computer Science · Materials Science · #Block Copolymer Self-Assembly #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Mathematics #Quantum Computing Algorithms and Architecture #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1611.01523
openalex publication_date 2016/11/04 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
It is well-known that the Toffoli gate and the negation gate together yield a\nuniversal gate set, in the sense that every permutation of 0,1 n can be\nimplemented as a composition of these gates. Since every bit operation that\ndoes not use all of the bits performs an even permutation, we need to use at\nleast one auxiliary bit to perform every permutation, and it is known that one\nbit is indeed enough. Without auxiliary bits, all even permutations can be\nimplemented. We generalize these results to non-binary logic: For any finite\nset A, a finite gate set can generate all even permutations of An for all\nn, without any auxiliary symbols. This directly implies the previously\npublished result that a finite gate set can generate all permutations of An\nwhen the cardinality of A is odd, and that one auxiliary symbol is necessary\nand sufficient to obtain all permutations when the cardinality of A is even.\nWe also consider the conservative case, that is, those permutations of An\nthat preserve the weight of the input word. The weight is the vector that\nrecords how many times each symbol occurs in the word or, more generally, the\nimage of the word under a fixed monoid homomorphism from A^* to a commutative\nmonoid. It turns out that no finite conservative gate set can, for all n,\nimplement all conservative even permutations of An without auxiliary bits.\nBut we provide a finite gate set that can implement all those conservative\npermutations that are even within each weight class of An.\n