Universal gates with wires in a row

DOI10.1007/S10801-021-01053-7MaRDI QIDQ2114796zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 15 March 2022

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

reversible gatesLEF groupsrule 57

Mathematics Subject Classification ID

Quantum computation (81P68) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80) Operations and polynomials in algebraic structures, primal algebras (08A40) Networks and circuits as models of computation; circuit complexity (68Q06)

Abstract: We give some optimal size generating sets for the group generated by shifts and local permutations on the binary full shift. We show that a single generator, namely the fully asynchronous application of the elementary cellular automaton 57 (or, by symmetry, ECA 99), suffices in addition to the shift. In the terminology of logical gates, we have a single reversible gate whose shifts generate all (finitary) reversible gates on infinitely many binary-valued wires that lie in a row and cannot (a priori) be rearranged. We classify pairs of words $u,v$ such that the gate swapping these two words, together with the shift and the bit flip, generates all local permutations. As a corollary, we obtain analogous results in the case where the wires are arranged on a cycle, confirming a conjecture of Macauley-McCammond-Mortveit and Vielhaber.

Recommendations

• Finite generating sets for reversible gate sets under general conservation laws
• Strongly universal reversible gate sets
• Universal groups of cellular automata
• The classification of reversible bit operations
• Universal pattern generation by cellular automata

Cites work

• Cellular automata and groups
• Closed Systems of Invertible Maps
• Computing by temporal order: asynchronous cellular automata
• Dynamics groups of asynchronous cellular automata
• Solution of Two Conjectures in Symbolic Dynamics
• Statistical mechanics of cellular automata
• Strongly universal reversible gate sets
• The classification of reversible bit operations
• The group of reversible Turing machines
• Towards an algebraic theory of Boolean circuits.

Cited in

(6)

• The category \textsf{CNOT}
• Liftings of automorphisms of hypermaps
• Finite generating sets for reversible gate sets under general conservation laws
• On the action of the toggle group of the Dynkin diagram of type \(A\)
• Strongly universal reversible gate sets
• Gate lattices and the stabilized automorphism group

This page was built for publication: Universal gates with wires in a row

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