CoChat
Sign Up
PreprintCited by 34Quantum Computing Algorithms and ArchitectureQuantum-Dot Cellular AutomataComputability, Logic, AI Algorithms

The Classification of Reversible Bit Operations

Open access
Aaronson, Scott, Grier, Daniel, Schaeffer, Luke·2015·arXiv
DOI 10.48550/arxiv.1504.05155arXiv 1504.05155
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1504.05155

Cites

21 of 21 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Reversible classical channels are fully generated by the set of isometries and auxiliary classical randomness, as they correspond to injective Boolean functions.

    “Furthermore, reversible classical channels are fully generated by the set of isometries and auxiliary classical randomness [53,55,56], as they correspond to injective Boolean functions.”

    From Simple formulation of no-cloning and no-hiding that admits efficient and robust verification (2024) · cites this paper as [55]

    Section 1.1 (p. 4) defines a reversible bit gate as a permutation of bit strings, supporting the injective-function aspect for the gates studied. But Theorem 3 (p. 16) distinguishes all reversible transformations from restricted classes, and Theorem 38 (p. 34) treats isometries as one such class. The paper does not say that isometries and auxiliary classical randomness generate all reversible classical channels. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

1 of the 22 references couldn’t be matched to a known paper.

Research works printed but not linked: 7

  1. [1][1] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing , 9(4):143-252, 2013. Conference version in Proceedings of ACM STOC'2011. ECCC TR10-170, arXiv:1011.3245. - · arXiv
  2. [13][13] P. Kerntopf, M. A. Perkowski, and M. Khan. On universality of general reversible multiplevalued logic gates. In IEEE International Symposium on Multiple-Valued Logic , pages 68-73, 2004. -
  3. [20][20] J. MacWilliams. Orthogonal matrices over finite fields. American Mathematical Monthly , 76(2):152-164, 1969. -
  4. [26][26] Y. Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computation. Quantum Information and Computation , 3(1):84-92, 2002. quant-ph/0205115. - · arXiv
  5. [27][27] I. Strazdins. Universal affine classification of Boolean functions. Acta Applicandae Mathematica , 46(2):147-167, 1997. -
  6. [28][28] T. Toffoli. Reversible computing. In Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP) , pages 632-644. Springer, 1980. -
  7. [29][29] A. De Vos and L. Storme. r-universal reversible logic gates. Journal of Physics A: Mathematical and General , 37(22):5815-5824, 2004.

Cited by

Sorted by citations

Related

Authors
Aaronson, S., Grier, D., & Schaeffer, L.
Affiliations
Massachusetts Institute of Technology (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2015
Volume
22
Pages
34
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1504.05155
arXiv
1504.05155
OpenAlex
W246788058
Cited by
33
References
22
Citations by year
2026: 1 · 2025: 2 · 2023: 4 · 2022: 4 · 2021: 4 · 2020: 6 · 2019: 3 · 2018: 3 · 2017: 3 · 2016: 3
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (submittedVersion, cc-by)
  • arXiv (Cornell University)
  • Leibniz international proceedings in informatics (cc-by)
  • Electronic colloquium on computational complexity
  • Conference on Innovations in Theoretical Computer Science
Funders
National Science Foundation (1122374, 1249349)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Quantum-Dot Cellular Automata
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
Keywords
reversible computation, reversible logic gates, Toffoli gate, Fredkin gate, CNOT gate, affine transformation, circuit compression, decidability, quantum gate sets, Diophantine equations

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review