The subject of study of this paper is reversible logic circuits. The irreversibility of computation can lead in the future to significant energy loss during the calculation process. Reversible circuits can be widely used in devices operating under conditions of limited computational resources. Presently, the problem of reversible logic synthesis is widely studied. The task a synthesis algorithm can face with is to reduce the gate complexity of synthesized circuit. One way to solve this problem is to use equivalent replacement tables for the gate compositions. The disadvantage of this approach is that it is necessary to build replacement tables, it takes a long time to find the replacement in the table, and there is no way to build an appropriate universal replacement table for arbitrary reversible circuit. The aim of this paper is to develop the solution for the problem of gate complexity reduction for the reversible circuits without using equivalent replacement tables for the gate compositions. This paper makes a generalization of the k-CNOT gate for the case of zero value at some of the gate control inputs. To describe such gates it suggests using a set of direct control inputs and a set of inverted ones. A definition of the independence of two reversible gates is introduced. Two independent gates standing next to each other in the circuit can be swapped without changing the circuit result transformation. Various conditions of the independence of two reversible gates are considered including conditions imposed to the set of direct control inputs and the set of inverted ones. It is proved that two gates are independent if there is, at least, one common control input, which differs only by the type (direct or inverted). Various equivalent replacements of two k-CNOT gates compositions and its conditions imposed to the set of direct control inputs and to the set of inverted ones are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Operations on the set of direct control inputs and on the set of inverted ones are widely used in the proof. The paper shows that two identical gates being nearby in the circuit can be excluded from it. It also shows that sometimes a composition of two gates can be replaced with the one gate, if the gates differ from each other by only one control input. The part of the equivalent replacements suggests in the paper does not reduce the gate complexity, but allows the new reversible gates to be available. In some cases after applying such replacements a new pair of gates can be found to satisfy the condition of another replacement reducing the gate complexity. The set of equivalent replacements proposed in this paper is significantly expanded comparing to the sets of equivalent replacements described in other papers. The paper describes the algorithm to reduce the reversible circuit gate complexity using the conditions of the gates independence and the proposed equivalent replacements of gate compositions. The algorithm is based on searching the pair of gates, which satisfy a condition of some replacement and which can be moved to each other without changing the circuit resultant transformation (conditions of gates independence proposed in this paper are checked). An example of using this algorithm in some abstract reversible circuit is offered. The advantage of the proposed approach is that it does not require replacement tables to be built, and the gate complexity can be reduced for the arbitrary circuit consisted of k-CNOT gates. Further, an assessment of the time complexity of the proposed algorithm of the gate complexity reduction is supposed to be given.
The subject of study of this paper is reversible logic circuits. The irreversibility of computation can lead in the future to significant energy loss during the calculation process. Reversible circuits can be widely used in devices operating under conditions of limited computational resources. Presently, the problem of reversible logic synthesis is widely studied. The task a synthesis algorithm can face with is to reduce the gate complexity of synthesized circuit. One way to solve this problem is to use equivalent replacement tables for the gate compositions. The disadvantage of this approach is that it is necessary to build replacement tables, it takes a long time to find the replacement in the table, and there is no way to build an appropriate universal replacement table for arbitrary reversible circuit. The aim of this paper is to develop the solution for the problem of gate complexity reduction for the reversible circuits without using equivalent replacement tables for the gate compositions. This paper makes a generalization of the k-CNOT gate for the case of zero value at some of the gate control inputs. To describe such gates it suggests using a set of direct control inputs and a set of inverted ones. A definition of the independence of two reversible gates is introduced. Two independent gates standing next to each other in the circuit can be swapped without changing the circuit result transformation. Various conditions of the independence of two reversible gates are considered including conditions imposed to the set of direct control inputs and the set of inverted ones. It is proved that two gates are independent if there is, at least, one common control input, which differs only by the type (direct or inverted). Various equivalent replacements of two k-CNOT gates compositions and its conditions imposed to the set of direct control inputs and to the set of inverted ones are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Operations on the set of direct control inputs and on the set of inverted ones are widely used in the proof. The paper shows that two identical gates being nearby in the circuit can be excluded from it. It also shows that sometimes a composition of two gates can be replaced with the one gate, if the gates differ from each other by only one control input. The part of the equivalent replacements suggests in the paper does not reduce the gate complexity, but allows the new reversible gates to be available. In some cases after applying such replacements a new pair of gates can be found to satisfy the condition of another replacement reducing the gate complexity. The set of equivalent replacements proposed in this paper is significantly expanded comparing to the sets of equivalent replacements described in other papers. The paper describes the algorithm to reduce the reversible circuit gate complexity using the conditions of the gates independence and the proposed equivalent replacements of gate compositions. The algorithm is based on searching the pair of gates, which satisfy a condition of some replacement and which can be moved to each other without changing the circuit resultant transformation (conditions of gates independence proposed in this paper are checked). An example of using this algorithm in some abstract reversible circuit is offered. The advantage of the proposed approach is that it does not require replacement tables to be built, and the gate complexity can be reduced for the arbitrary circuit consisted of k-CNOT gates. Further, an assessment of the time complexity of the proposed algorithm of the gate complexity reduction is supposed to be given.
Reversible logic computing is an emerging research area due to its high-speed computing abilities and generating the lossless information. Due to the ability of reverse operation and high-speed computing performance, reversible computation is considered as a future alternative to the conventional computing. The rapid progress of reversible computation in the current scenario, the reversible circuit is the way to solve this type of computation. Moreover, the reversible circuit computation is the higher level abstraction of the quantum circuit. The synthesis design of these circuits is an important aspect in the current literature. In this paper, we present our work in the field of synthesis design of a reversible circuit. In this work, we propose a modified transformation-based synthesis design using the FREDKIN/SWAP gate to reduce the quantum cost and minimizing the number of gates. To obtain this synthesis design approach, we have introduced some new templates which are defined by rules of replacing the k-CNOT/FREDKIN/SWAP gates using a template matching approach. Here, we are considering only k-CNOT ( k ≥ 1), FREDKIN and SWAP based gate in our templates. Finally, we provide our experimental results based on different benchmark reversible circuits. The experimental result has shown that the number of quantum cost and gate count are reduced using the FREDKIN/SWAP gate in the transformation-based approach with the help of proposed templates.
An algorithm for reversible logic synthesis is proposed. The task is, for a given n -bit substitution map, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates with m control bits, where m∈{0,…,n−1} . Controlled gates with large m (> 2) are then further decomposed into smaller gates ( m≤2 ). A primary goal in designing the algorithm is to reduce the number of Toffoli gates, which is known to be universal. The main idea is to view an n -bit substitution map as a rank-2 n tensor and to transform it such that the resulting map can be written as a tensor product of a rank-(2 n -2) tensor and the 2× 2 identity matrix. It can then be seen that the transformed map acts nontrivially on n -1 bits only, meaning that the map to be synthesized becomes ( n -1)-bit substitution. This size reduction process is iteratively applied until it reaches a tensor product of only 2× 2 matrices. The time complexity of the algorithm is exponential in n , as most previously known heuristic algorithms for reversible logic synthesis are, but it terminates within reasonable time for not too large n , which may find practical uses. As stated earlier, our primary target is to reduce the number of Toffoli gates in the output circuit. Benchmark results show that the algorithm works well for hard benchmark functions, but it does not seem advantageous when the function is structured. As an application, the algorithm is applied to find reversible circuits for cryptographic substitution boxes, which are often required in quantum cryptanalysis.
In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates are studied. Several asymptotically optimal by the order of magnitude synthesis methods are described. Some circuit's complexity reduction approaches are considered. Implementation of discrete logarithm within a reversible circuit is discussed. The main conclusion in the paper is that the usage of additional inputs (additional memory) in reversible circuits almost always allow to reduce their complexity, depth and weight.
The paper discusses the gate complexity of reversible circuits with the small number of additional inputs consisting of NOT, CNOT and 2-CNOT gates. We study Shannon's gate complexity function L(n,q) for a reversible circuit implementing a Boolean transformation f:Z2n→Z2n with q⩽O(n2) additional inputs. The general bound L(n,q)≍n2n/log2n is proved for this case.
Summary form only given, as follows. With the increasing emphasis on low-power design and quantum computation, research activities in the area of reversible logic synthesis and testing have gained momentum over the last couple of decades. It is expected that reversible logic will provide us with a viable alternative to building ultra-low power circuits and systems in not too distant future. In the classical works for synthesis of reversible circuits, gate libraries comprising of standard reversible gates like NOT, CNOT, TOFFOLI, FREDKIN, etc. are considered. To evaluate the goodness of a synthesized netlist, various metrics such as gate count, quantum cost, and equivalent transistor cost have been considered by various researchers. The synthesis approaches that have been reported can be broadly categorized into three groups: (a) exact synthesis approaches which try to obtain optimal reversible gate netlists, but can be used for small circuits only, (b) heuristic based approaches which try to utilize some domain knowledge intelligently to reduce the complexity of search, and can be used for somewhat larger circuits, and (c) synthesis approaches that rely on higher level functional representations like binary decision diagram (BDD) or exclusive sum-ofproducts (ESOP). The last approach is scalable to larger circuits (with 200 inputs or more), however, the synthesized netlist is not optimal and various rule-based heuristic approaches have been proposed to minimize the cost. There have been works also that report techniques for implementing sequential circuits with reversible properties, which will be useful for building complex systems containing finite-state machines. There are various transformations that are carried out as part of cryptographic algorithms that are inherently reversible in nature. For instance, any block cipher that uses a key K to transform a plaintext P into a ciphertext C during encryption must be reversible, because decryption will be doing just the reverse (C to P). Also, in standard symmetric block ciphers like DES or AES, there is a combinational block called substitution box or S-box which is also reversible in nature. In AES, the S-box has 8 inputs and 8 outputs, and implements a one-to-one onto mapping. The same reversibility requirements hold for stream ciphers and public-key ciphers like RSA. Although not much work has been carried out in the area of reversible implementations of cryptographic algorithms, this can be a very good area for future research. Similar considerations hold for various coding and decoding techniques used in communication, which are also inherently reversible in nature. Some examples of such coding/decoding are Manchester, Differential Manchester, Bipolar AMI, 4B/5B, 8B/10B, Hamming error correcting code, etc. All these techniques can potentially be implemented using reversible logic circuits. Specific case studies of some of the areas as mentioned will be reported, with synthesis results.
The reversible logic can be used in various research areas, e.g. quantum computation, cryptography and signal processing. In the paper we study reversible logic circuits with additional inputs, which consist of NOT, CNOT and C\textsuperscript{2}NOT gates. We consider a set F(n,q) of all transformations Bn→Bn that can be realized by reversible circuits with (n+q) inputs. An analogue of Lupanov's method for the synthesis of reversible logic circuits with additional inputs is described. We prove upper asymptotic bounds for the Shannon gate complexity function L(n,q) and the depth function D(n,q) in case of q>0: L(n,q0)≲2n if q0∼n2n−o(n) and D(n,q1)≲3n if q1∼2n.