@1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 Quantum Gates to Implement the Reversible Logic Circuits Ali H. Khidhir Department of Physics / College of Science / University of Baghdad Received in : 21 September 2011 , Accepted in : 12 February 2012 Abstract Quantum gates which are represented by unitary matrices have potentials to implement the reversible logic circuits. M and M+ gates are two well-known quantum gates which are used to synthesize the reversible logic circuits. In this work, we have used behavioral description of these gates, instead of unitary matrix description, to synthesize reversible logic circuits. By this method, M and M+ gates are shown in the truth table form. Keywords : Reversible Logic Circuits , Quantum Gates , Unitary Matrices . 131 | Physics @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 Introduction In several applications of quantum communication and computation, one has to be able to perform some operations between two-level systems (qubits). For example, any quantum algorithm involves quantum gates between several qubits; in teleportation, on has to perform joint measurements between two qubits; in order to purify states, one also needs these operations. So far, there are very few systems in which we know how to implement arbitrary operations between two qubits [1]. J. F. Poyatos at el. [1] demonstrated a way to implement these operations for a set of ions confined in a trap at zero temperature. It was based in the selective excitation of the center of mass mode of the collective motion using laser light, such that only when two atoms are in a given state, this state changes reversible logic circuit synthesis is an introduction to design of quantum computing-based systems, and nanotechnology-based systems. Since quantum mechanics processes appeared as a good candidate to construct reversible gates and quantum gates [2]. Quantum computation is a fast growing field in quantum information theory. First basic ideas for realization of quantum computation processes have been discussed and experimental efforts have been made, though it is still unknown [3], which method is the most effective and elegant way leading to the first quantum computing machine [3]. Carmen M. Tesch et. al.[3] demonstrated a molecular approach to quantum computing: The vibrational normal mode as of molecules in an ensemble are used to encode qubits systems. In each mode a certain degree of excitation is referred to as |0>, another degree of excitation in the same mode is referred to as |1>. After introduction of the idea of quantum computation it has already been seen that there exists some quantum algorithms [4] which work much faster than their classical counterparts, and these processes which establish quantum computing as a superior future technology involves quantum circuits and quantum gates [2]. As quantum gates and quantum algorithms are more powerful than classical reversible gates [4]. There are some 3×3 classical reversible gates, provided constant inputs are permitted [4]. On the other hand, major of quantum 2×2 gates are universal, without needing the constant inputs [5] Set of M, M+, and Feynman quantum gates is a universal set to implement all reversible logic gates. Since quantum gates are represented in the unitary matrix form, synthesis algorithms for quantum circuits are also based on this form of representation various methods are also presented to synthesize the reversible logic circuits [2,6]. In this work, we introduce a way to represent the quantum M and M+ gates in the truth table form. The M gate is named square root of NOT (√𝑁𝑂𝑇 ) and M+ is the complex conjugate transpose of M gate [2]. The properties of these gates used to construct a truth table for the gates. Reversible Gates, Quantum gates, and Circuits Classical reversible logic gates called reversible gates are ones which act on binary digits or bits. They are implemented in various technologies such as CMOS, optical and nanotechnology techniques. On the other hand, quantum gates act on qubits. A qubits is a unit of quantum information. That information is described by a state vector in a two-level quantum mechanical system which is formally equivalent to a two-dimensional vector space over the complex numbers [4]. Generally quantum gates cannot be implemented using conventional technologies such as CMOS . Reversible Gates and Circuits A function or a circuit is called reversible if there is a one-to-one correspondence between its input and output assignments. That is, in a reversible circuit the outputs can be uniquely determined from the inputs, and the inputs can also be recovered from the outputs. If a reversible function is shown by a truth table, then its output patterns must be the permutation 132 | Physics @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 of its input patterns. This implies that the number of inputs and outputs of a reversible circuit are equal. A reversible gate implements a reversible function. As a result, a reversible gate has an equal number of inputs and outputs. Generally, with 𝑛 inputs, there exists (2n) reversible gates. Logical 1×1 reversible gates are the NOT and BUFFER. The well-known 2×2 Feynman gate which operates as a controlled NOT (CNOT), is shown in Fig.1(a). If the control input of CNOT is set to '0', the gate acts as a BUFFER gate; else, it acts as a NOT gate. Fig.2 shows the Toffoli and the Fredkin 3×3 gates. Each of these gates is universal, i.e. any logical reversible circuit can be implemented using these gates reproduce the function of a universal gate, such as a NAND gate. A Fredkin gate, shown in Fig.2(c), acts as a cross switch. If the control input (A) is '0' then the Q and R outputs are equal to inputs B and C respectively. If the control input is '1' then the Q and R outputs are equal to inputs C and B respectively. The Toffoli gate is generalized to 𝑛 inputs and 𝑛 outputs, named TOFn gate. This gate has 𝑛-1 control inputs. If all control inputs are '1' then the nth output is the NOT of the nth input; else, the nth output is equal to the nth input. The Fredkin gate can be extended to an 𝑛× 𝑛 gate the same way as the Toffoli gate [2,7]. Quantum Gates and Circuits A quantum logic gate called quantum gate, is a basic quantum circuit operating on small number of qubits. They are the analogous for quantum computers to classical logic gates for conventional digital computers. Quantum logic gates are reversible unlike many classical logic gates. They are represented by gates in series are equivalent to a NOT gates; unitary matrices. The most common quantum gates operate on spaces of one or two qubits. This means that quantum gates can be described by 2×2 or 4×4 matrices with orthonormal rows. Some examples of quantum gates are Feynmam, Toffoli, Fredkin, Hadamard, and phase shifter gates. Some reversible logic gates, such as the Feynman, Toffoli, and Fredkin gates are directly mapped onto quantum logic gates [4]. For instance, the Hadamard gate operates on a single qubit. It is represented by the Hadamard matrix (Eq.1). Since, the rows of the matrix are orthogonal. H is a unitary matrix. H = 1 √2 �1 1 1 − 1 � ……………….(1) The controlled-U gate is a gate that operates on two qubits in such a way that the first qubit serves as a control (Eq.2). C(U)=� 1 0 0 0 0 1 0 0 0 0 𝑥00 𝑥01 0 0 𝑥10 𝑥11 �…………(2) It is shown that all classical logic operations can be performed on a universal quantum computer [2,5]. Figure 2 (b) showed a quantum implementation of a 3×3 Toffoli gate. In this Figure, an M gate indicates the state of the qubits is multiplied by a 2×2 matrix (Eq.3), when the control qubits is |1>. M =�0 1 1 0 � 1 2� = 1+𝑖 2 � 1 −𝑖 −𝑖 1 � … … (3) The M gate is also named square root of NOT gate (NOT). M is the Hermitian conjugate of M. The M and M+ quantum gates have some properties that are shown in Eq.4. 133 | Physics @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 M×M=NOT M×M+=M+×M=I ……….(4) M+×M+=NOT Where I is the standard 2×2 identity matrix. These equations show that two M and M+ and two M and M+ in series, are equivalent to an identity or a BUFFER gate. A quantum circuit consists of quantum gates which are interconnected without fanout or feedback by quantum wires. It can be thought of as a classical circuit , with quantum data [5]. Classic reversible logic circuits can be realized using quantum gates. This is useful whenever a classical process is needed in a quantum computer. The set of quantum M, M+, and Feynman gates is a universal set for reversible logic circuits . Behavioral Description of M and M+ Gates Quantum gates have been identified by their unitary matrices, often including complex numbers. Defining the quantum gates using a truth table is not common. On the other hand, the quantum M and M+ gates are necessary for the construction of a set of universal 2×2 gates for synthesis of reversible circuits. To construct a truth table for M and M+ gates properties of these gates are used, proposed by equation 4. This equation shows that two M gates in series are equal to a NOT gate. Two M+ gates in series are also as a NOT gate. One M and one M+ gates in series are equal two identity. We define two intermediate signals r and R for M gate output values and two intermediate signals w and W for M+ gate output values. We assign r value to the M gate output if its input is |0> and R value if its input is |1>. In the same way, we assign w and W values to the output values of a M+ gate, when input values are |0> and|1>, respectively. Now, if the input of M gate is r then the output is |1> because the r value is a result of applying input |0> to an M gate and two series M gates is equal to an M gate results a |0> output. If the input of an M gate is w then its output is |0> because a w signal is a result of applying |0> to an M gate and two M and M+ series gates are equal to an identity or buffer gate. These results we can construct a truth table as shown in Table 1 for M and M+ gates. In this table we used '0' and '1' characters instead of vectors |0> and|1> , respectively. Conclusion In this paper we proposed a method to represent the quantum M and M+ gates based on their properties. Using the behavioral description of quantum gates, the M and M+ gates showed as a truth table form. This behavior can be used to implement the reversible logic circuits using the quantum gates. References 1. Poyatos, J. F. ; Cirac, J. I. and Zoller, P. (2011), Quantum gates with hot trapped ions, IEEE, 40, 18. 2. Mohammadi, M. and Eshghi, M.Behavioral description of quantum V and V gates to design quantum logic circuits", Applied Physics, 23, 5. 3. Carmen, M. Tesch and Regina de Vivie, (2003),Molecular quantum computing applying optimal control theory: Quantum gates and algorithms, IEEE, 40, 10. 4. Phillip,Kaye, Raymond Laflamme, and Michele Mosca, (2007), An introduction to quantum computing, Oxford University Press Jan, , Book-linG. 5. Barenco, A.; Bennett, C. H.; Cleve, R.; Divincenzo, D. P.; Margolus, N.; Shor, P.; Sleator T.; Smolin, J. A. and Weinfurter, H. (1995), Elementary gates for quantum computation", Phys. Rev. A52(5) :3457-3467. 134 | Physics @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 6. Michael Miller, D.; Gerhard Dueck, W. and Dmitri Maslov, (2003), A transformation based algorithms for reversible logic synthesis, Phys. Rev., 48,11,. 7. Fredkin, E. and Toffoli, T.( 1982), Conservative logic, Int. J. Theo. Phys., 21(6):219. Table (1): Truth table of M and M+ gates A(input) Q(M gate) Q(M+ gate) O r W 1 R W r 1 0 R 0 1 w 0 1 W 1 0 B I=B B B A Q=A + B 0 B (a) (b) Fig .(1): (a) Feynman gate , (b) copying a signal by Feynman gate A P=A p B Q=B Q C R= C + A.B (a) (b) Q=A'B+AC R=AB+AC' (c) Fig .(2): (a) Toffoli gate , (b) its equivalent , implemented by quantum gates , (c) Fredkin gate M M M + R 135 | Physics @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 العكسیةالبوابات الكمیة لتنفیذ دوائر المنطق علي حسن خضر جامعة بغداد / كلیة العلوم /قسم الفیزیاء 2012شباط 12، قبل البحث في 2011أیلول 21استلم البحث : الخالصة )، تمكن���ت Unitary Matricesبوس���اطة مص���فوفات الوح���دة ( Quantum Gate)وض���حت البواب���ات الكمی���ة ( ، إذ اس���تعملت بواب���ات كمی���ة معروف���ة مث���ل (Reversible Logic Circuits) م���ن تنفی���ذ ال���دوائر المنطقی���ة العكس���یة لتركی���ب دوائ���ر المنط���ق العكس���یة. ك���ذلك اس���تخدم وص���ف س���لوك ھ���ذه البواب���ات ف���ي ھ���ذا العم���ل ب���دال +Mو Mبواب���ات Truth)م���ن مص���فوفة الوح���دة لتك���وین دوائ���ر المنط���ق العكس���یة ، ث���م وص���فت ھ���ذه البواب���ات بش���كل ج���دول ص���واب Table). ، البوابات الكمیة ، مصفوفات الوحدة . الدوائر المنطقیة العكسیة : الكلمات المفتاحیة 136 | Physics