Journal of Quantum Information Science, 2012, 2, 6165 http://dx.doi.org/10.4236/jqis.2012.23011 Published Online September 2012 (http://www.SciRP.org/journal/jqis) Permutation Algebra for Constructing Reversible Circuits Shah Mohammad Bahauddin, Abu Ashik Md. Irfan Department of Applied Physics, Electronics & Communication Engineering, Faculty of Engineering & Technology, University of Dhaka, Dhaka, Bangladesh Email: bahauddin_omar@ieee.org Received April 17, 2012; revised May 9, 2012; accepted June 4, 2012 ABSTRACT In this paper, we show that the algebra of permutation group is one of the inherent structures of reversible logic for quantum computation. In this venture, we discuss necessary properties of cycle and transposition to reveal the potential of permutation algebra for reversible logic. Then we present an efficient method which naturally interconnects the struc ture of reversible logic with the expression of cycle and corresponding transpositions. Finally we discuss several exam ples which show that the algebra can be effectively used to construct complex gates as well. Keywords: Control NOT; TaffoliFredkin Gate; Full Adder 1. Introduction In recent years, reversible logic has become more and more prominent technology having its applications in quantum computing and other aspects of nanotechnology. Moreover, reversibility can also be a solution to the en ergy dissipation issue in chip level integrated systems. Logically reversible gates are those where the inputs can be inferred from knowledge of the outputs, meaning the logic function implemented by the gate has a unique in verse. In this paper, we present a method which inter connects the structure of reversible logic with permuta tion algebra. By applying the properties of cycle and transposition, we also show that any complex arithmetic circuit such as full adder can be easily achieved and effi ciently constructed. 2. Reversibility & Permutation Group An nbit reversible logic gate is a block which performs a permutation on the 2n possible states of bits that pass through it. Hence it is a onetoone correspondence from a 2n state onto itself. Thus specifying a reversible logic gate is nothing but specifying the mapping that it per forms. In quantum computing, these computational states are represented by quantum mechanical state. For exam ple, let us define an arbitrary finite set S having nele ments (which are in this case well defined quantum me chanical states). Then any reversible logic of such set can be expressed by introducing S where is a one toone mapping of S onto itself. Now, one can represent the set of bits with the set of kets ,ab 0,1 i (such that i = 0, 1, 2, 3) which are the four computational states expressed by two input bits of the measurement gate. This allows us to represent any logic (in this exam ple XOR or more specifically Control NOT) by means of specific basis state as acontrol btarget iinput > acontrol b target ioutput > 0 0 0 0 0 0 0 1 1 0 1 1 1 0 2 1 1 3 1 1 3 1 0 2 A closer examination immediately reveals that this representation can be shown as an element under the permutation S4. Hence we can say CNOT can be repre sented as a onetoone mapping of S4, and in terms of energy state, the above table can now be represented by the permutation. 0123 0132 Since the S4 contains 4! permutations it means that there exists 24 different logic gates for a 4state system. Generalizing the above statements we can say that, any Nlevel quantum system can be permutated in N! com putationally distinct logic sets. In other words, these per mutations of degree N form a group of order N! under composite operation of permutation. This permutation group, SN is the collection of all bijective maps :SS of the interval , with com position maps () as the group operation. We now intend to recall some basic definitions for describing permuta tions [1]. 1,2, 3,S N C opyright © 2012 SciRes. JQIS
S. M. BAHAUDDIN, A. A. MD. IRFAN 62 Cycle of a Permutation: For k > 1, a kcycle is a permutation 12 1 12 1 23 ,, ,, k kk k iii iii i ii i that acts on S in the following way maps 121 12 12 :,,, :,,, k k iii iiiii jjjii i k Here k is called the length of the cycle. Cycles of length 1 are redundant since they reduce to identity. The order of the entries in a cycle matters, but cycle notation is not unique as the following 12 1 23 1 34 12 12 ,, ,, ,, ,, ,, ,,, ,, ,, kk k k kkk iii i ii ii ii iii iii i 1 Transposition: A cycle of length 2 is called a trans position. Every cycle of length k in SN (N > 1) is ex pressible as a product (k − 1) of transpositions in the fol lowing manner, 1211,111312 ,, ,,,,, kkk k iiiiiiiiii ii Since, the inverse of a permutation is the permutation obtained by interchanging the rows between them. This results to state that every transposition is the inverse of its own. 1 ,.,, , kjkjkjk kj ii iiIiiiiii A product of disjoint cycle or transpositions is com mutative. ,, ,, kmnmn jk iiiiii ii An important property which will be particularly in teresting for this paper is that one can decompose a transposition in the following product, ,,,, ljkkljk iiiiii ii 3. Algebra of Reversible Logic Now we show that the algebra of reversible logic can be introduced in terms of permutation group and the concept of cycle works as the building block of reversible gate. Hence, we adopt the following statements, For every nbit reversible logic there exist a unique permutation of degree 2n. This means, the properties and the operations of permutation groups are applicable for reversible logic as well. This statement is discussed in the beginning of the lit erature. Recall that as a subgroup of a symmetric group, all the necessary group axioms are satisfied by permuta tion group; that is it contains the identity permutation, the inverse permutation and the associative and closure property. Since reversible logic mimics a permutation as shown before, the composite operations between permu tations can also be adapted for reversible gates. Since every reversible gate is expressible by corre sponding permutation, hence it is possible to express a reversible gate as a product of disjoint cycles and nec essarily as a product of transpositions. Let us examine the logic of an inverter which is and 1 since it is a single bit logic, the gate can be expressed as a permutation of degree 2 which is 010 NOT 01 0,1 10 It can be seen that the inverter is logically reversible, but unfortunately is not a universal gate in the sense that any arbitrary Boolean logic is not realizable in terms of inverter alone. For quantum computation, we need uni versal reversible gates. One of such gates is the Taffoli Fredkin (TF) gate [2,3] which is necessarily a 3bit gate with 3 inputs (a, b, c) and corresponding outputs (a', b', c'). The relationship between the input and output is the following ' ' ' aa bb cc ab Here denotes the Exclusive OR and denotes the AND function. The variables a and b are control bits where c is called the target bit. As seen from the logic, the control bit suffers from no change while passing through the gate. However the target bit flips if both con trol bits are logic 1. The permutation corresponding to this gate is, TF 000001010011 100101 110111 000001010011100101 111 110 And the corresponding transposition is TF = (110, 111). We can also write the transposition in decimal symbol which would be more convenient for calculation. In case of TF gate, the transposition is (6, 7). The similar treatment can be accounted for more com plex gates. Such a gate is Peres gate [4], which is another reversible and universal one. Peres gate is mainly inter esting due to its combination of TF gate and CNOT gate which makes it an attractive candidate to realize complex logic such as addition, subtraction etc. Peres gate is also a 3bit gate which maintains relationship between the input and output as following, Copyright © 2012 SciRes. JQIS
S. M. BAHAUDDIN, A. A. MD. IRFAN Copyright © 2012 SciRes. JQIS 63 ' ' ' aa bab cc ab = (4, 6)(6, 7)(5, 6) = (4, 6)(5, 7)(5, 7)(6, 7)(5, 7)(5, 7)(5, 6) = (4, 6)(5, 7)(5, 6)(5, 7)(5, 6) = (4, 6)(5, 7)(6, 7) As seen from the logic, the outputs of bit b and c suffer from CNOT and TF operations respectively while bit a remains unchanged. The permutation corresponding to this gate is, Now going from right to left, all we have to do is to sum up the corresponding CNOT gates as per transpositions. Then the decomposition will denote Peres gate through the joining of 3bit CNOT gates as shown below: Peres 000001010011 100101 110111 000 001010 011110111101100 The corresponding cycle has a length of 4 and can be decomposed in 3 transpositions, In the above example, let the CNOT of cycle (6, 7) and (4, 6) (5, 7) are expressed as C1 and C2 respectively. Then clearly C1, C2 are onetoone mapping of 0,1,2,, 7S C onto itself and the Peres gate is merely a composite (12 ) of C1 and C2 which can mathe matically written by (12 )(x) = C1(C2(x)), C CC S . Since this is the closure property of permutation group, it is obvious that Peres 100,110,101,111 100,111100,101100,110 In decimal symbol, the cycle of Peres gate is (4, 6, 5, 7) = (4, 7)(4, 5)(4, 6). 4. Construction of General Gates 12 CC S8. Similarly, for n = 4, we have four options to choose any one as a target bit and for each target bit, there exists 23 – 1 = 7 unique combinations of control bits. Hence there are 7 × 4 = 28 numbers of CNOT gate for n = 4 (Table 1). Again each of the 28 gates can be realized by a unique product of transpositions as shown in Figure 2. We showed earlier, with example, that the product of cycles of a permutation is sufficient to realize any re versible logic. In an extension, let us introduce an n bit CNOT gate. In this case, we can realize the CNOT op eration on any one bit of n while the control bits are the other (n – 1) bits or (n – 2) and so on. If n = 3, then we can choose any one as a target bit out of three and for each target bit, there exist 22 – 1 = 3 unique combinations of control bits. This means there are 9 possible CNOT gate for n = 3 (Figure 1), where each of them can be realized by a unique product of transpositions. At this juncture, let us imagine that we intend to real ize the logic of a full adder, which is evidently irreversi ble. By adding an extra bit, we can make it reversible, which means it would be a 4bit reversible logic. But now the question lies where we want to put that extra bit. Since there were 3 bits in an irreversible full adder, we have different positions of significance (from MSB to LSB) to put that extra bit. In our paper, we have intro duced 3 logics of such reversible Full Adder where the extra bit is set at three different positions of significance starting from LSB. The permutation corresponding to the gates are given below. Here, in all three cases, the output of a full adder logic is realized only when the extra bit is zero. In addition, the least significant two bits of the outputs are the sum and carryout. Now we will utilize the properties of cycles, to prove that any reversible logic can be simulated by a combina tion of elementary gates. In other words, we will prove that the decomposition of reversible logic is possible by exploit ing the properties of cycles under permutation algebra. As an example, we can realize Peres gate in terms of the 3bit CNOT gates Peres = (4, 6, 5, 7) = (6, 5, 7, 4) FA1 0000000100100011 01000101011001111000 10011010 10111100 11011110 1111 00000011 0110010000100001010101111010 1011110111001001 100011111110 FA2 00000001001000110100010101100111 10001001 10101011 11001101 11101111 00000010000100110110010101110100 1110 1101 11111100100110111000 1010 FA3 0000000100100011010001010110011110001001 101010111100110111101111 0000001001100001 01000101001101111010 1001110110111100 1000 1110 1111 Now the corresponding cycles in decimal are, FA3 = (1, 2, 6, 3)(8, 10, 13) FA1 = (1, 3, 4, 2, 6, 5)(8, 10, 13)(9, 11, 12)(14, 15) As we stated before, our intention is to decompose these reversible adder logics by 4bit CNOT gates only. = (1, 2)(4, 6, 7)(8, 14)(9, 13, 11, 12)(10, 15) FA2
S. M. BAHAUDDIN, A. A. MD. IRFAN 64 (6,7)(2,3)(6,7)(5,7)(4,6)(5,7) (4,5)(6,7) (2,6)(3,7) (3,7) (1,3 )(6, 7) (1,5 )(3, 7) Figure 1. Possible permutations and corresponding trans positions of 3bit CNOT gates. Table 1. Transpositions of 4bit CNOT gates correspond ing to Figure 2. Row 1 (target bit at 1st LSB) Row 3 (target bit at 3rd LSB) No. Transpositions No. Transpositions 1 (14,15) 1 (11,15) 2 (6,7)(14,15) 2 (3,7)(11,15) 3 (10,11)(14,15) 3 (9,13)(11,15) 4 (12,13)(14,15) 4 (10,14)(11,15) 5 (8,9)(10,11)(12,13)(14,15) 5 (8,12)(9,13)(10,14)(11,15) 6 (4,5)(6,7)(12,13)(14,15) 6 (2,6)(3,7)(10,14)(11,15) 7 (2,3)(6,7)(10,11)(14,15) 7 (1,5)(3,7)(9,13)(11,15) Row 2 (target bit at 2nd LSB) Row 4 (target bit at MSB) No. Transpositions No. Transpositions 1 (13,15) 1 (7,15) 2 (5,7)(13,15) 2 (3,11)(7,15) 3 (9,11)(13,15) 3 (5,13)(7,15) 4 (12,14)(13,15) 4 (6,14)(7,15) 5 (8,10)(9,11)(12,14)(13,15) 5 (4,12)(5,13)(6,14)(7,15) 6 (4,6)(5,7)(12,14)(13,15) 6 (2,10)(3,11)(6,14)(7,15) 7 (1,3)(5,7)(9,11)(13,15) 7 (1,9)(3,11)(5,13)(7,15) Figure 2. Possible permutations of 4bit CNOT gates. Figure 3. Realization of full adderFA 3 expressed by 26 4bit CNOT gates. Here, we will utilize the expression of different CNOT gates in terms of corresponding transpositions and we will operate permutation algebra on these transpositions according to the lemmas to obtain the logic of reversible adder. So, let us first examine the reversible logic of φFA3 and then decompose it into elementary transpositions which are available for CNOT operation in following manner, FA3 = (1, 2, 6, 3)(8, 10, 13) = (3, 1, 2, 6)(8, 10, 13) = (3, 6)(3, 2)(3, 1)(8, 13)(8, 10) = (3, 7)(6, 7)(3, 7)(2, 3)(1, 3)(12, 13)(8, 12)(12, 13) (8, 10) Now, if we give a closure look at the figures of C NOT gates previously sketched before with their corre sponding product of transpositions, we can immediately reveal that the first transposition (3, 7) cannot be realized alone by any CNOT gate rather it can be construted by a combination of (3, 7) (11, 15) and (11, 15). According to the previous statement, we can say that both of the transpositons (6, 7) and (12, 13) also require a combina tion of two CNOT gates while each of the four transpo sitions (1, 3), (2, 3), (8, 10) and (8, 12) requires a combi nation of four distinct CNOT gates. In summary, we have to add a total of 26 CNOT gates to realize the logic of FA3 (Figure 3). It is now evident that we could also simulate the logic of FA2 (shown in Figure 4) and FA1 (not shown) as well. Our calculation shows that the FA2 can be con structed by 40 CNOT gates while FA1 will be com prised of 53 CNOT gates. 5. Conclusion The decomposition of complex gate by means of the product of transposition and corresponding nbit CNOT gate gives us further opportunity to express the logic in more elementary gates. This is because any nbit CNOT gate and corresponding unitary operations can be ex pressed as a composition of 2 bit CNOT and the TF Figure 4. Realization of full adder expressed by 40 4bit CNOT gates. FA 2 Copyright © 2012 SciRes. JQIS
S. M. BAHAUDDIN, A. A. MD. IRFAN 65 [5]. Moreover, th REFERENCES [1] J. F. Humphre Theory,” 5th Edi anguages and Program gate e number of basic operations to7th Colloquium on Automata, L perform all these steps showed in our examples is mathematically efficient and unique and thus can be eas ily estimated. Hence we conclude that permutation alge bra can be employed as an inherent structure to construct complex reversible circuit for quantum computational networks. ys, “A Course in Group tion, Oxford University Press, Oxford, 1996. [2] T. Taffoli, “Reversible Computing,” Proceedings of the ming, Vol. 85, 1980, pp. 632644. doi:10.1007/3540100032_104 [3] E. Fredkin and T. Taffoli, “Conservative Logic,” Interna tional Journal of Theoretical Physics, Vol. 21, No. 34, 1982, pp. 219253. doi:10.1007/BF01857727 [4] A. Peres, “Reversible Logic and Quantum Computers,” Physical Review A, Vol. 32, No. 6, 1985, pp. 32663276. doi:10.1103/PhysRevA.32.3266 [5] A. Barenco, C. H. Bennett, C. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin and H. Weinfurter, “Elementary Gates for Quantum Computa tion,” Physical Review A, Vol. 52, No. 5, 1995, pp. 3457 3467. doi:10.1103/PhysRevA.52.3457 Copyright © 2012 SciRes. JQIS
