The classification of reversible bit operations
From MaRDI portal
Abstract: We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable. The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^n*poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace." Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Ruling out the possibility of additional classes, not in the list, requires some arguments about polynomials, lattices, and Diophantine equations.
Recommendations
Cites work
- ALGORITHMIC PROBLEMS IN VARIETIES
- Both Toffoli and Controlled-NOT need little help to universal quantum computing
- Complexity classification of local Hamiltonian problems
- Conservative logic
- Function Algebras on Finite Sets
- scientific article; zbMATH DE number 3692653 (Why is no real title available?)
- Irreversibility and Heat Generation in the Computing Process
- Logical Reversibility of Computation
- Machines, Computations, and Universality
- On universality of general reversible multiple-valued logic gates
- r-Universal reversible logic gates
- Synthesis and optimization of reversible circuits -- a survey
- The classification of reversible bit operations
- The computational complexity of linear optics
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Universal affine classification of Boolean functions
Cited in
(16)- Galois connection for multiple-output operations
- Finite generating sets for reversible gate sets under general conservation laws
- Universal gates with wires in a row
- No Tits alternative for cellular automata
- A classical propositional logic for reasoning about reversible logic circuits
- The group of reversible Turing machines
- Strongly universal reversible gate sets
- Enumeration of reversible functions and its application to circuit complexity
- The category \textsf{TOF}
- Computing with the square root of NOT
- scientific article; zbMATH DE number 1543308 (Why is no real title available?)
- The classification of reversible bit operations
- scientific article; zbMATH DE number 822043 (Why is no real title available?)
- Universal groups of cellular automata
- scientific article; zbMATH DE number 6027046 (Why is no real title available?)
- The group of reversible Turing machines: subgroups, generators, and computability
This page was built for publication: The classification of reversible bit operations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638073)
