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

arXiv:1309.4037

Statistical distribution of the reversible gates: what percentage of them are self-inverse?

Anirban Pathak

Published Sep 16, 2013• 3 citations
arXivHTMLPDF

Abstract

It is well known that most of the frequently used reversible logic gates (e.g., NOT, CNOT, SWAP, Toffoli, Fredkin) are self-inverse and are represented by square matrices that are unitary and Hermitian. However, with a simple minded argument, it is established that the most of the allowed reversible gates are non-self-inverse (unitary but non-Hermitian) in nature. It is also shown that the % of non-Hermitian gates increases with the dimension. For example, 58.33% of the 2-bit gates, 98.10% of the 3-bit gates and 99.99% of the 4-bit gates are non-Hermitian. As classical reversible gates are essentially permutation gates, above statistics is strictly valid for classical reversible gates, but the argument can be easily extended to include quantum gates and to establish that the majority of the quantum gates are also non-self-inverse. Further, the % of genuinely 2-bit reversible gates (i.e., 2-bit gates that cannot be decomposed as a product of two single bit gates) among all possible gates has been computed as 83.3%, and the applicability of this analysis in the optimization of circuit cost is discussed.

DOI
10.48550/arxiv.1309.4037

Related papers

Non-Hermitian quantum gates are more common than Hermitian quantum gates

Anirban Pathak

Most of the frequently used quantum gates (e.g., NOT, Hadamard, CNOT, SWAP, Toffoli, Fredkin and Pauli gates) are self-inverse (Hermitian). However, with a simple minded argument it is established that most of the allowed quantum gates are non-Hermitian (non-self-inverse). It is also shown that the % of non-Hermitian gates increases with the dimension. For example, 58.33% of the 2-qubit gates, 98.10% of the 3-qubit gates and 99.99% of the 4-qubit gates are non-Hermitian. As classical reversible gates are essentially permutation gates so the above statistics is strictly valid for classical reversible gates. Further, since Hermiticity is not of much interest in context of the classical reversible gate, hence the result implies that most of the allowed classical reversible gates are non-self-inverse.

•Sep 16, 2013•3 citations

General structures of reversible and quantum gates

Kishore Thapliyal, Anirban Pathak

The most general structure (in matrix form) of a single-qubit gate is presented. Subsequently, used that to obtain a set of conditions for testing (a) whether a given 2-qubit gate is genuinely a 2-qubit gate, i.e., not decomposable into two single qubit gates and (b) whether a given single qubit gate is self-inverse? Relevance of the results reported here is discussed in the context of optimization of reversible and quantum circuits, especially for the optimization of quantum cost. A systematic procedure is developed for the identification of the non-decomposable 2-qubit gates. Such a non-decomposable 2-qubit gate along with all possible single qubit gates form a universal quantum gate library. Further, some possible applications of the present work are also discussed.

arXiv:1702.06272•Feb 21, 2017•2 citations

Reversible logic synthesis with Fredkin and Peres gates

James Donald, Niraj Kumar Jha

Reversible logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis tool, to include additional gate types. While classic RMRLS can synthesize functions using NOT, CNOT, and n -bit Toffoli gates, our work details the inclusion of n -bit Fredkin and Peres gates. We find that these additional gates reduce the average gate count for three-variable functions from 6.10 to 4.56, and improve the synthesis results of many larger functions, both in terms of gate count and quantum cost.

ACM Journal on Emerging Technologies in Computing Systems•Mar 1, 2008•85 citations

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•55 citations

Performance evaluation of reversible logic gates

Umesh Kumar, Lavisha Sahu, Uma Kant Sharma

It has been realized that quantum computing is one of the latest technologies using reversible logic. It is observed that increasing growth of transistor density, power consumption will reach their limits in conventional technologies. In conventional Circuits during the logic operations bits of information is erased resulting dissipation of energy in significant amount. Thus, if Circuits are designed so that information bits can be preserved, the power use can be reduced. In case of reversible logic computation, the information bits are not lost. We can use reversible logic technology for minimizing the power consumption, heat dissipation, increasing speed etc. This paper describes various logic gates based on reversible logic like Toffoli, Peres, Fredkin, and Feynman etc. A comparative between classical and quantum logic gates is also given on various parameters along with limitations of conventional computing.

IEEE International Conference on ICT in Business Industry & Government (ICTBIG)•Jan 1, 2016•18 citations

In-depth Comparative Analysis of Reversible Gates for Designing Logic Circuits

Hari Mohan Gaur, Ashutosh Kumar Singh, Umesh Ghanekar

Reversible logic is expanding grounds with its applicability to various upcoming technologies and quantum computation. Numerous reversible gates has also been proposed for designing logic circuits apart of basic quantum controlled Toffoli and Fredkin gates. A comparative study and analysis of a range of reversible gates from the literature is presented in this paper to obtain an optimal solution for designing these circuits. The gates are synthesized and implemented to obtain equivalent quantum circuits and operating cost in terms of number of inputs, gate cost, quantum cost, garbage output and ancilla input. The comparison is done at two subsequent levels i.e. gates structural level and circuit design level, providing a better solution for designing logic circuits. It is calculated that, basic gates are 50% efficient at gate level and 33% at design level analysis in terms of gate cost, as compared to the most efficient gates proposed in the literature.

Procedia Computer Science•Jan 1, 2018•38 citations
It is well known that most of the frequently used reversible logic gates (e.g., NOT, CNOT, SWAP, Toffoli, Fredkin) are self-inverse and are represented by square matrices that are unitary and Hermitian. However, with a simple minded argument, it is established that the most of the allowed reversible gates are non-self-inverse (unitary but non-Hermitian) in nature. It is also shown that the % of non-Hermitian gates increases with the dimension. For example, 58.33% of the 2-bit gates, 98.10% of the 3-bit gates and 99.99% of the 4-bit gates are non-Hermitian. As classical reversible gates are essentially permutation gates, above statistics is strictly valid for classical reversible gates, but the argument can be easily extended to include quantum gates and to establish that the majority of the quantum gates are also non-self-inverse. Further, the % of genuinely 2-bit reversible gates (i.e., 2-bit gates that cannot be decomposed as a product of two single bit gates) among all possible gates has been computed as 83.3%, and the applicability of this analysis in the optimization of circuit cost is discussed.
Most of the frequently used quantum gates (e.g., NOT, Hadamard, CNOT, SWAP, Toffoli, Fredkin and Pauli gates) are self-inverse (Hermitian). However, with a simple minded argument it is established that most of the allowed quantum gates are non-Hermitian (non-self-inverse). It is also shown that the % of non-Hermitian gates increases with the dimension. For example, 58.33% of the 2-qubit gates, 98.10% of the 3-qubit gates and 99.99% of the 4-qubit gates are non-Hermitian. As classical reversible gates are essentially permutation gates so the above statistics is strictly valid for classical reversible gates. Further, since Hermiticity is not of much interest in context of the classical reversible gate, hence the result implies that most of the allowed classical reversible gates are non-self-inverse.
The most general structure (in matrix form) of a single-qubit gate is presented. Subsequently, used that to obtain a set of conditions for testing (a) whether a given 2-qubit gate is genuinely a 2-qubit gate, i.e., not decomposable into two single qubit gates and (b) whether a given single qubit gate is self-inverse? Relevance of the results reported here is discussed in the context of optimization of reversible and quantum circuits, especially for the optimization of quantum cost. A systematic procedure is developed for the identification of the non-decomposable 2-qubit gates. Such a non-decomposable 2-qubit gate along with all possible single qubit gates form a universal quantum gate library. Further, some possible applications of the present work are also discussed.
Reversible logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis tool, to include additional gate types. While classic RMRLS can synthesize functions using NOT, CNOT, and n -bit Toffoli gates, our work details the inclusion of n -bit Fredkin and Peres gates. We find that these additional gates reduce the average gate count for three-variable functions from 6.10 to 4.56, and improve the synthesis results of many larger functions, both in terms of gate count and quantum cost.
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.
It has been realized that quantum computing is one of the latest technologies using reversible logic. It is observed that increasing growth of transistor density, power consumption will reach their limits in conventional technologies. In conventional Circuits during the logic operations bits of information is erased resulting dissipation of energy in significant amount. Thus, if Circuits are designed so that information bits can be preserved, the power use can be reduced. In case of reversible logic computation, the information bits are not lost. We can use reversible logic technology for minimizing the power consumption, heat dissipation, increasing speed etc. This paper describes various logic gates based on reversible logic like Toffoli, Peres, Fredkin, and Feynman etc. A comparative between classical and quantum logic gates is also given on various parameters along with limitations of conventional computing.
Reversible logic is expanding grounds with its applicability to various upcoming technologies and quantum computation. Numerous reversible gates has also been proposed for designing logic circuits apart of basic quantum controlled Toffoli and Fredkin gates. A comparative study and analysis of a range of reversible gates from the literature is presented in this paper to obtain an optimal solution for designing these circuits. The gates are synthesized and implemented to obtain equivalent quantum circuits and operating cost in terms of number of inputs, gate cost, quantum cost, garbage output and ancilla input. The comparison is done at two subsequent levels i.e. gates structural level and circuit design level, providing a better solution for designing logic circuits. It is calculated that, basic gates are 50% efficient at gate level and 33% at design level analysis in terms of gate cost, as compared to the most efficient gates proposed in the literature.