Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Classifying reversible logic gates with ancillary bits

Cole Comfort

Published Jul 23, 2019• 2 citations
Publisher

Abstract

In this thesis, two models of reversible computing are classified, and the relation of reversible computing to quantum computing is explored. First, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the controlled-not gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between non-empty finitely-generated commutative torsors of characteristic 2. Next, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the Toffoli gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between finite powers of the two element set. The relation between reversible and quantum computing is also explored. In particular, the category with the controlled-not gate as a generator is extended to be complete for the real stabilizer fragment of quantum mechanics. This is performed by translating the identities to and from the angle-free fragment of the ZX-calculus, and showing that these translations are inverse to each other.

DOI
10.11575/prism/36765

Related papers

Circuit Relations for Real Stabilizers: Towards TOF+H

Cole Comfort

The real stabilizer fragment of quantum mechanics was shown to have a complete axiomatization in terms of the angle-free fragment of the ZX-calculus. This fragment of the ZX-calculus---although abstractly elegant---is stated in terms of identities, such as spider fusion which generally do not have interpretations as circuit transformations. We complete the category CNOT generated by the controlled not gate and the computational ancillary bits, presented by circuit relations, to the real stabilizer fragment of quantum mechanics. This is performed first, by adding the Hadamard gate and the scalar sqrt 2 as generators. We then construct translations to and from the angle-free fragment of the ZX-calculus, showing that they are inverses. We then discuss how this could potentially lead to a complete axiomatization, in terms of circuit relations, for the approximately universal fragment of quantum mechanics generated by the Toffoli gate, Hadamard gate and computational ancillary bits.

arXiv:1904.10614•Apr 24, 2019•1 citation

The Classification of Reversible Bit Operations

Scott Aaronson, Daniel Grier, Luke Schaeffer

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.

arXiv:1504.05155•Leibniz international proceedings in informatics•Apr 20, 2015•33 citations

The Classification of Stabilizer Operations over Qubits

Daniel Grier, Luke Schaeffer

We present a complete classification of quantum stabilizer gates in terms of the functions they generate assuming the ability to swap qubits and use ancillary workspace. Because we view these stabilizer circuits as subroutines of some general quantum computation, we insist that any ancilla qubits used during the computation must not change in an input-dependent manner. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets. The classification uses, at its center, a reinterpretation of the tableau representation of stabilizer gates to give circuit decompositions, from which elementary generators can easily be extracted. There are a total of 57 different stabilizer classes generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.

•Mar 13, 2016•6 citations

Reversible Logic Synthesis with Minimal Usage of Ancilla Bits

Siyao Xu

Reversible logic has attracted much research interest over the last few decades, especially due to its application in quantum computing. In the construction of reversible gates from basic gates, ancilla bits are commonly used to remove restrictions on the type of gates that a certain set of basic gates generates. With unlimited ancilla bits, many gates (such as Toffoli and Fredkin) become universal reversible gates. However, ancilla bits can be expensive to implement, thus making the problem of minimizing necessary ancilla bits a practical topic. This thesis explores the problem of reversible logic synthesis using a single base gate and a few ancilla bits. Two base gates are discussed: a variation of the 3-bit Toffoli gate and the original 3-bit Fredkin gate. There are three main results associated with these two gates: i) the variated Toffoli gate can generate all n-bit reversible gates using 1 ancilla bit, ii) the variated Toffoli can generate all n-bit reversible gates that are even permutations using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative reversible gates using 1 ancilla bit. Prior to this paper, the best known result for general universality requires three basic gates, and the best known result for conservative universality needs 5 ancilla bits. The second result is trivially optimal. For the first and the third result, we explicitly prove their optimality: the variated Toffoli cannot generate all n-bit reversible gates without using any extra input lines, and the Fredkin gate cannot generate all n-bit conservative reversible gates without using extra input lines. We also explore a stronger version of the second converse by introducing a new concept called borrowed bits, and prove that the Fredkin gate cannot generate all n-bit conservative reversible gates without ancilla bits, even with an unlimited number of borrowed bits.

arXiv:1506.03777•Jun 10, 2015•12 citations

Computing with the Square Root of NOT

Alexis De Vos, Jan De Beule, Leo Storme

To the two classical reversible 1-bit logic gates, i.e. the identity gate (a.k.a. the follower) and the NOT gate (a.k.a. the inverter), we add an extra gate, the square root of NOT. Similarly, we add to the 24 classical reversible 2-bit circuits, both the square root of NOT and the controlled square root of NOT. This leads to a new kind of calculus, situated between classical reversible computing and quantum computing.

Serdica Journal of Computing•Jan 11, 2010•10 citations

Creating subgroups of U(2w) for quantum-minus computers

Alexis De Vos, Michiel Boes

Classical reversible computers on w bits are isomorphic to the (finite) symmetric group S 2 w ; quantum computers on w qubits are isomorphic to the (Lie) unitary group U(2 w ). We investigate and classify groups X which represent computers intermediate between classical reversible computers and quantum computers. Such intermediate groups X may exist in three flavours: finite groups of order larger than (2 w )!, infinite but discrete groups, and Lie groups of dimension smaller than (2 w ). For our purpose, we start from 1-qubit transformations, represented by 2 × 2 unitary matrices. We call this group the creator. Its members are called gates and act on one qubit. Controlled gates are quantum circuits acting on w qubits, such that the 1-qubit transformation (applied to a particular qubit) depends on the state of the w − 1 other qubits. The controlled gates generate the group X of 2 w × 2 w matrices, called the creation. We discuss all creators of order up to 8. Additionally a creator of order 16 and one of order 192 are discussed.

Journal of Physics Conference Series•Mar 1, 2011•1 citation
In this thesis, two models of reversible computing are classified, and the relation of reversible computing to quantum computing is explored. First, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the controlled-not gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between non-empty finitely-generated commutative torsors of characteristic 2. Next, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the Toffoli gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between finite powers of the two element set. The relation between reversible and quantum computing is also explored. In particular, the category with the controlled-not gate as a generator is extended to be complete for the real stabilizer fragment of quantum mechanics. This is performed by translating the identities to and from the angle-free fragment of the ZX-calculus, and showing that these translations are inverse to each other.
The real stabilizer fragment of quantum mechanics was shown to have a complete axiomatization in terms of the angle-free fragment of the ZX-calculus. This fragment of the ZX-calculus---although abstractly elegant---is stated in terms of identities, such as spider fusion which generally do not have interpretations as circuit transformations. We complete the category CNOT generated by the controlled not gate and the computational ancillary bits, presented by circuit relations, to the real stabilizer fragment of quantum mechanics. This is performed first, by adding the Hadamard gate and the scalar sqrt 2 as generators. We then construct translations to and from the angle-free fragment of the ZX-calculus, showing that they are inverses. We then discuss how this could potentially lead to a complete axiomatization, in terms of circuit relations, for the approximately universal fragment of quantum mechanics generated by the Toffoli gate, Hadamard gate and computational ancillary bits.
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.
We present a complete classification of quantum stabilizer gates in terms of the functions they generate assuming the ability to swap qubits and use ancillary workspace. Because we view these stabilizer circuits as subroutines of some general quantum computation, we insist that any ancilla qubits used during the computation must not change in an input-dependent manner. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets. The classification uses, at its center, a reinterpretation of the tableau representation of stabilizer gates to give circuit decompositions, from which elementary generators can easily be extracted. There are a total of 57 different stabilizer classes generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.
Reversible logic has attracted much research interest over the last few decades, especially due to its application in quantum computing. In the construction of reversible gates from basic gates, ancilla bits are commonly used to remove restrictions on the type of gates that a certain set of basic gates generates. With unlimited ancilla bits, many gates (such as Toffoli and Fredkin) become universal reversible gates. However, ancilla bits can be expensive to implement, thus making the problem of minimizing necessary ancilla bits a practical topic. This thesis explores the problem of reversible logic synthesis using a single base gate and a few ancilla bits. Two base gates are discussed: a variation of the 3-bit Toffoli gate and the original 3-bit Fredkin gate. There are three main results associated with these two gates: i) the variated Toffoli gate can generate all n-bit reversible gates using 1 ancilla bit, ii) the variated Toffoli can generate all n-bit reversible gates that are even permutations using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative reversible gates using 1 ancilla bit. Prior to this paper, the best known result for general universality requires three basic gates, and the best known result for conservative universality needs 5 ancilla bits. The second result is trivially optimal. For the first and the third result, we explicitly prove their optimality: the variated Toffoli cannot generate all n-bit reversible gates without using any extra input lines, and the Fredkin gate cannot generate all n-bit conservative reversible gates without using extra input lines. We also explore a stronger version of the second converse by introducing a new concept called borrowed bits, and prove that the Fredkin gate cannot generate all n-bit conservative reversible gates without ancilla bits, even with an unlimited number of borrowed bits.
Classical reversible computers on w bits are isomorphic to the (finite) symmetric group S 2 w ; quantum computers on w qubits are isomorphic to the (Lie) unitary group U(2 w ). We investigate and classify groups X which represent computers intermediate between classical reversible computers and quantum computers. Such intermediate groups X may exist in three flavours: finite groups of order larger than (2 w )!, infinite but discrete groups, and Lie groups of dimension smaller than (2 w ). For our purpose, we start from 1-qubit transformations, represented by 2 × 2 unitary matrices. We call this group the creator. Its members are called gates and act on one qubit. Controlled gates are quantum circuits acting on w qubits, such that the 1-qubit transformation (applied to a particular qubit) depends on the state of the w − 1 other qubits. The controlled gates generate the group X of 2 w × 2 w matrices, called the creation. We discuss all creators of order up to 8. Additionally a creator of order 16 and one of order 192 are discussed.