Genetic Synthesis of New Reversible/Quantum Ternary Comparator.
Quantum computing [1,2] is very attractive research area and has made huge advances both theoretically and experimentally in recent years. There are many different proposals for the physical implementation of a quantum computer, all of which are specified by the physics of their qubit systems and the nature of the interactions between qubits [1-6]. The circuit is called reversible if it implements bijective mappings of input signals to the output signals set. Two-level quantum systems are mainly used in quantum computing. In recent papers [2-10] it has been indicated that there are many advantages in quantum computers build on multiple-valued physical systems. A three-level logic that on the physical level can be implemented using a three-level quantum system (qutrits) is an optimal for computing. As shown in [4,5,7] qutrits are more efficient base in the processing of quantum information than other quantum digit (qudit) implementations. Synthesis of the reversible logic circuits differs significantly from the synthesis of combinational logic circuits because in a reversible circuit the number of inputs must be equal to the number of outputs, every output can be used only once (i.e., no fan-out is permitted), and must be acyclic. Ternary logic, as the simplest type of multiple-valued logic (MVL), increasingly attract the attention of researchers in recent years [7-16]. Among them cascades of ternary reversible gates like Feynman and Toffoli gates are used to realize ternary logic functions [11,12,17].
An arbitrary ternary function of several input variables can be expressed as the sum of the products corresponding variables on the Galois field . This allows implementing ternary functions with the use of reversible ternary Feynman and Toffoli gates. However, Muthukrishnan and Stroud have demonstrated the realization of MVL for quantum computing using liquid ion-trap quantum technology , which led to the proposal of the Muthukrishnan and Stroud (M-S) gates. It has been showed that an arbitrary MVL operation on any number of multiple valued qudits can be decomposed into elementary logic gates that operate on only two qudits at a time [3,7]. We refer to these elementary two qutrit gates as M-S gates. A brief description of these reversible gates, as well as an introduction to the most basic ternary gates such as the one-qutrit permutative gates is given in the following section.
To solve the problems associated with an unidentified structure many researchers are increasingly turning lately to Soft Computing methods. Among them are genetic algorithms (GAs), based on the principles of natural selection and evolution [18-20]. These advantages make GAs useful for synthesizing ternary reversible/quantum circuits using cascade of Muthukrishnan-Stroud gates [21-24]. The problem of finding such structures is complicated because the structure of the cascades is still unidentified and the search space exponentially increases with the number of inputs. Applying of the GAs to build quantum circuitry has already been investigated [9,11,13,21-30]. However, obtaining optimal digital reversible ternary logic devices remains a challenge. In particular this applies to parameters such as quantum cost of synthesized circuits, the delay time of the signal and the number of constant input (output) lines. The problem is to choose such an evolutionary strategy that would ensure the search for the best solution of the problem and at the same time would be relatively easy to implement. It relates to a method of coding chromosome, generation of initial population, effective ways to implement the main genetic operators (selection, crossover, mutation) etc. Synthesis of optimal fitness-function for evaluation of the adaptability of offspring is incompletely studied issue. The task is further complicated by the additional conditions imposed by the quantum (reversible) character of ternary networks, as well as other well-known problems of evolutionary strategies [18,25]. All this suggests the relevance of the presented studies.
This paper proposes a simple version of the GA, which allows the effective search of optimal solutions for the problem of multi-parameter synthesis of ternary reversible combinational circuits. The proposed method is tested on the synthesis of full ternary reversible/quantum comparators. Synthesized devices have parameters significantly better compared to the conventional counterpart. In this paper we evaluate the quantum cost of a ternary reversible circuit as the number of M-S gates required in its implementation. The MVL reversible circuit with minimal number of garbage outputs, minimal quantum cost and minimum number of constant input ternary digits (ancilla trits) is considered as an efficient design.
The structure of the paper is as follows: Section II explains the basic ternary reversible gates. Section III presents the details of proposed genetic algorithm. Section IV shows the proposed design of the reversible ternary comparators and the analysis of the proposed circuits. Section V provides the conclusions.
II. TERNARY PERMUTATIVE GATES
In this paper we consider the permutable subclass of reversible quantum circuits. These circuits consist of gates described by unitary permutative matrices [7,29].
We describe the transformation of qutrit state using a square 3X3 unitary matrix corresponding to the 1-qutrit quantum gates. There are many such non-trivial 1-qutrit gates. We use only the permutative transforms as shown by permutative matrices of Table I.
The logical equivalent of these 1-qutrit transforms can be expressed using truth tables as shown in Table II. Using reasoning similar to [2,8-11], we assign the gate costs of these 1-qutrit gates to be one.
The important gates for designing ternary quantum circuits are the ternary M-S gates. The diagram of a ternary M-S gate is shown in Table I. Here, input [X.sub.1] is the controlling input and input [X.sub.2] is the controlled input. The output [Y.sub.1] is equal to the input [X.sub.1]. If [X.sub.1] = 2, the other output [Y.sub.2] is the Z-transform of the input [X.sub.2], otherwise [Y.sub.2] = [X.sub.2].
III. PROPOSED GENETIC ALGORITHM
Methods of reversible logic synthesis are quite different compared to traditional irreversible technologies [7-17]. GAs are belong to meta-heuristic algorithms for finding the optimal solution of various kinds of problems including the synthesis of binary systems and are based on the evolutionary ideas of natural selection and genetics[18-20]. The development of evolutionary computation for multilevel systems is at an early stage of research. However, even at this stage it has several advantages over analytical approaches that have been developed only for systems with some qutrits for a limited class of logic functions [9,10,12,14-17]. At the same time, the universality of evolutionary algorithms is not limited to the size of the system or form of logical function, implemented by the reversible/quantum network. With the increasing dimension of the system the space of states, where genetic search is carried out, is growing. Therefore, genetic search for optimal solutions of several parameters must be formulated as easy as possible in order to fit practical implementation of quantum algorithms. This applies to all stages of GA, from the chromosome coding method to final search conditions. On the other hand, the most important requirements to CAD systems for automated design of optimal reversible networks, is the possibility to synthesize an arbitrarily large logic functions in a given basis. Also, these CAD systems have to perform a reduction of quantum cost of received networks and time delay of the digital signals. There are some attempts to create such systems for two-level quantum logic nowadays [19,26,28,30], however, ternary logic CAD software are to be realized. For such complex programs the major problem is a selection of the optimal algorithm. In our opinion, GA is one of the most successful methods for such problem because it is quite simple and is formalized with a good choice of parameters that allows solving the problem with minimal cost. In this paper an improved approach to the synthesis of reversible/quantum ternary comparators based on the use of GAs is proposed. This approach to the reversible logic synthesis is caused by the need to take into account several additional conditions, namely, it is not possible to have a fanout larger than 1(no-cloning theorem ) and the feedback is not allowed. We assume that the required scheme is a definite series-parallel arrangement of logical controlled and uncontrolled primitives which are described above.
We assume that in each vertical column of the circuit there can not be more than one gate (Fig. 1). Information inputs (controlling and controlled) are placed on the top part of the network, while inputs, where stable signals are sent, are placed at the bottom part. As optimization parameters we have choose:
(i) the minimum number of logic errors of output signals according to the truth table of the synthesized ternary reversible device;
(ii) the minimum number of constant (ancilla) inputs;
(iii) the minimum number of circuit elements.
The genetic algorithm is used to automatically search of a chromosome that is a sequence of primitives connection according to a given output truth table of the device and imposed optimization conditions.
A. Problem Encoding
Chromosome is a scheme of the device, and is encoded as an ordered 3-tuples of genes, which correspond to the gate of the column . The gene contains the following information: the number of controlling line, the line number where a gate is located, the type of a gate (Fig. 1(a), bottom row). If the number of controlling line is equal to the number of line on which a gate is placed, the gate is assumed uncontrollable. In Fig. 1(a) an example of chromosome coding (scheme of one-digit ternary comparator) is presented. Three input and output lines are used to simulate one-digit comparator. Informational signals a and b are inputs to the top two lines, constant signal 0 - on the bottom line. At the output, besides repetition of the input signals a and b, the function of full 1-qutrit ternary comparator is obtained on the bottom output line:
[mathematical expression not reproducible] (1)
B. Generation of Initial Population
Initial population of chromosomes, each of which represents a possible solution to the problem of synthesis of reversible device, has been generated randomly. offspring population does not get a copy of the individual from the parent population if the individual is already in the offspring population.
An important feature of GA is evaluation of the fitness-function of each chromosome [11-17]. Fitness-function F used in this paper consists of three fitness components:
F = [k.sub.1]F1 + [k.sub.2]F2 + [k.sub.3]F3. (2)
F1 - fitness component that minimizes the number of logical errors (Error) of output signals according to the truth table of the synthesized device:
F1 = 1/Error + 1, (3)
F2 - fitness component that minimizes the number of gates dG not 0-type of the circuit, if the length of the chromosome, i.e. the number of genes in the chromosome, is dL:
F2 = dL - dG/dL, (4)
F3 - fitness component that minimizes the number of controlled M-S gates:
F3 = dGM/dG, (5)
where dGM - number of 2-qutrit gates; [k.sub.1], [k.sub.2], [k.sub.3] - weights coefficients. To find the correct logic circuits the coefficient [k.sub.1] is always taken equal to 1. other coefficients of fitness function are taken less than one.
D. Genetic Operators
Selection operator is panmixis. Panmixis - the simplest selection operator, according to which each member of the population is assigned a random integer in the interval [1, n], where n - number of individuals in the population. We consider these numbers as the numbers of individuals who takes part in the crossing. A pair of identical members is not considered at this choice. Some members of the population take part in the reproduction process more than once with different individuals in the population. Despite its simplicity, this approach is universal for solving different classes of problems.
The proposed GA uses one-point crossover operation or uniform crossover with probability 0.5. Uniform crossover means that an exchange of genes between individuals-parents with a certain probability [p.sub.C] occurs at each locus. This ensures that offspring will have alternate short lines of individuals-parents.
The mutation occurs in each locus with a certain probability [p.sub.m] and means random change of gene.
E. Offspring Evaluation
Estimation of offspring was carried out on their fitness-function. If offspring are better than the worst individuals of parent population, then they are replaced. otherwise, stagnation counter is increased by one. If changes in the population do not occur, we assume that there is stagnation. When reaching a given number of stagnation GA re-runs with a new seed.
F. Post GA
Post GA is a process of minimizing genetic algorithm circuits obtained by replacing certain parts of chromosomes on equivalent, but shorter on length. The following rules are used [13,28,29]:
(i) if in the same line there are two connected 1-qutrit gates, they are replaced by one according to the adding table;
(ii) similar replacement is done for M-S gates, in the case they have the same controlling line;
(iii) a group of series-connected in one controlled line: 1-qutrit gate, M-S gate, 1-qutrit gate is replaced by a group consisting of one equivalent 1-qutrit gate and consistently M-S gate.
The algorithm terminates when the specified number of working cycles is done or if chromosomes with a fitness-function of equal or greater than unit is obtained. In the case of falling into a local maximum it is much easier to launch another genetic algorithm that tries to fix at least one error and combine the result of its work with the previously found to give an individual with fewer errors escaping from a local maximum at the same time.
IV. TERNARY N-QUTRIT COMPARATOR
Ternary comparators are important elements of quantum/reversible networks as their own, and are part of more complex devices, including ternary Fredkin gates [1,9,24].
Firstly we realized a one-qutrit comparator which truth table is shown in Figure 1(c). It compares two single-digit ternary numbers a, b and sets the output f = 2 (a = b), or f= 1 (a > b), or f = 0 (a < b). Since the network is reversible, the input signals a, b are repeated at the output, the input ancillary qutrit 0 (constant input) is required for formation of the corresponding line of full comparator. Realization of full one-qutrit comparator is shown in Figure 1(a) and requires 10 elementary gate (cost = 10) and one ancilla qutrit. The delay time of the obtained comparator, as shown in Fig.1, equals 7[t.sub.0], where [t.sub.0] is the delay time of a single gate.
In n-qutrit comparator two n-qutrit numbers a = [a.sub.n-1]... [a.sub.1][a.sub.0] and b = [b.sub.n-1]... [b.sub.1][b.sub.0] are compared. For designing of n-qutrit comparator we have introduced a complementary device (CC) which compares output functions f of 1-qutrit comparators according to the truth table Fig. 2(c). Comparison functions of low-order [f.sub.1] and high-order [f.sub.2] digits are inputs. At the output of the device comparison function [f.sub.12] of two-qutrit numbers [a.sub.2][a.sub.1] and [b.sub.2][b.sub.1] is formed. Analytically this function can be written in the form:
[mathematical expression not reproducible] (6)
Realization of the CC device using proposed GA is shown in Fig. 2(a) and requires 8 elementary gate (cost = 8) and one ancilla qutrit (one constant input 0). The delay time of the obtained CC-device, as shown in Fig.2, equals 6[t.sub.0].
As can be seen from Fig. 3 proposed implementation of n-qutrit ternary comparator requires n one-qutrit comparators and (n-1) CC devices, which is quantum cost (QC) of the comparator is equal to:
QC = 10n + 8(n -1) = 18n - 8. Ancilla qutrits = n + n -1 = 2n -1. (7)
As can be seen from the Table III the proposed n-qutrit ternary comparator is more efficient than existing similar devices [21,22]. The delay time of the obtained n-qutrit ternary comparator, as can be seen from Fig. 3, equals
[t.sub.[SIGMA]]= 7[t.sub.0] + 6[t.sub.0](n -1) = (6n +1)[t.sub.0], (8)
where [t.sub.0] is the single gate delay time.
Classical genetic algorithm is applied to the synthesis of reversible/quantum ternary comparators in the basis of permutation 1-qutrit and 2-qutrit Muthukrishnan-Stroud gates. Proposed method for chromosome coding and proper choice of parameters of the algorithm allow obtaining circuits for ternary comparators which are better than other available approaches. We have achieved lower-cost reversible devices built on the elementary M-S gates. An improved genetic algorithm with the use of fitness-function proposed by the authors is realized. Developed fitness-function allows to minimize the number of errors in logic output signals according to the truth table of the synthesized reversible devices, the number of constant (ancilla) inputs and the number of circuit elements (quantum cost). Moreover, the proposed implementation of the genetic algorithm has led to reducing the device delay time and the number of ancilla qutrits to 1 and 2w-1 for one-and w-qutrits full comparators, respectively. For designing of w-qutrit comparator we have introduced a complementary device which compares output functions of 1-qutrit comparators. The use of Post GA allowed further minimization of quantum cost due to the use of certain rules for equivalent replacement of group gates. Obtained one- and w-qutrit ternary comparators have better characteristics of quantum cost (10 for one-qutrit and 18w-8 for w-qutrits full comparators) as compared with other works. Thus, it can be argued that the proposed w-qutrit ternary comparator is more efficient than existing similar devices. Evolutionary method for synthesis of quantum reversible comparators presented in this paper showed a greater flexibility and considerable potential for reversible circuit design in comparison with other multivariable optimization methods.
 M. Nielsen, I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010.
 A. De Vos, M. Bose, S.D. Baerdemacker, "Reversible computation, quantum computation, and computer architectures in between", J. Multiple-Valued Logic and Soft Comput., vol. 18, no. 1, pp. 67-81, 2012.
 A. Muthukrishnan, C. R. Stroud, Jr., "Multivalued logic gates for quantum computation," Physical Review A, vol. 62, no. 5, pp. 052309/1-8, 2000. [Online]. Available: http://dx.doi.org/10.1103/PhysRevA.62.052309.
 A. B. Klimov, R. Guzman, J. C. Retamal, C. Saavedra, "Qutrit quantum computer with trapped ions," Physical Review A, vol. 67, no. 6, 062313/1-7, 2003. [Online]. Available: http://dx.doi.org/10.1103/PhysRevA.67.062313.
 D. McHugh, J. Twamley, "Trapped-ion qutrit spin molecule quantum computer", New J. Physics, vol. 7, No. 1, pp. 174/1-9,2005.
 V. G. Deibuk. I.M. Yuriychuk, R.I. Yuriychuk, "Spin model of full adder on Peres gates," Int. J. Computing, vol. 11, no. 3, pp. 282-292, 2012.
 D. M. Miller, M. A. Thornton. Multiple Valued Logic: Concepts and Representations. Morgan & Claypool Publishers, 2008.
 M. Lukac, M. Perkowski, H. Goi, M. Pivtoraiko, C. H. Yu, K. Chung, H. Jee, B-G. Kim, Y-D. Kim, "Evolutionary approach to Quantum and Reversible Circuits synthesis," Artificial Intelligence Review, vol. 20, no. 3-4, pp. 361-417, 2003. [Online]. Available: http://dx.doi.org/10.1023/B:AIRE.0000006605.86111.79.
 D.M. Miller, D. Maslov, G.W. Dueck, "Synthesis of quantum multiple-valued circuits", J. Multiple-Valued Logic and Soft Comput., vol. 12, no. 5-6, pp. 431-450, 2006.
 D.M. Miller, R. Wille, R. Drechsler, "Reducing reversible circuit cost by adding lines", J. Multiple-Valued Logic and Soft Comput., vol. 19, no. 1-3, pp. 185-201, 2012.
 M. Lukac M. Perkowski and M. Kameyama, "Evolutionary quantum logic synthesis of boolean reversible logic circuits embedded in ternary quantum space using structural restrictions", in Proc. IEEE Congress on Evolutionary Computation (CEC 2010), Barcelona, Spain, 18-23 July 2010, pp. 1-8. [Online]. Available: http://dx.doi.org/10.1109/CEC.2010.5585969
 M. H. A. Khan, M. A. Perkowski, M. R. Khan, and P. Kerntopf, "Ternary GFSOP minimization using Kronecker Decision Diagrams and their synthesis with quantum cascades," J. Multiple-Valued Logic and Soft Comput., vol. 11, no. 5-6, pp. 567-602, 2005.
 R. Khanom, T. Kamal, M. H. A. Khan, "Genetic algorithm based synthesis of ternary reversible / quantum circuits," in Proc. 11th IEEE Int. Conf. on Computer and Information Technology (ICCIT 2008), Khulna, Bangladesh, 25-27 December, 2008, pp. 270-275. [Online]. Available: http://dx.doi.org/10.1109/ICCITECHN.2008.4803043
 X. Li, G. Yang, D. Zheng, "Logic synthesis of ternary quantum circuits with minimal qutrits," J. of Computers, vol. 8, no. 8, pp. 1941-1946, 2013. [Online]. Available: http://dx.doi.org/10.4304/jcp.8.8.1941-1946
 Y.-M. Di, and H.-R. Wie, "Synthesis of multivalued quantum logic circuits by elementary gates," Physical Review A, vol. 87, no. 1, pp. 012325/1-8, 2013. [Online]. Available: http://dx.doi.org/10.1103/PhysRevA.87.012325
 S. B. Mandal, A. Chakrabarti and S. Sur-Kolay, "Quantum Ternary Circuit Synthesis Using Projection Operations," J. Multiple-Valued Logic and Soft Comput., vol. 24, no. 1-4, pp. 73-92, 2015.
 K. Fazel, M. A. Thornton, and J. E. Rice, "ESOP-based Toffoli gate cascade generation," in Proc. IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, (PacRim,2007), Victoria, Canada, 22-24 August, 2007, pp. 206-209. [Online]. Available: http://dx.doi.org/10.1109/PACRIM.2007.4313212.
 R. S. Zebulum, M. C. Pachecco, M. M. Vellasco. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms. CRC Press, 2002.
 L. Spector. Automatic Quantum Computer Programming: A Genetic Programming Approach. Kluwer Academic Publishers, 2004.
 A. E. Eiben, J. E. Smith. Introduction to Evolutionary Computing. Springer-Verlag, 2013.
 M. H. A. Khan, "Design of reversible/quantum ternary comparator circuits," Engineering Letters, vol. 16, no. 2, pp. 178-164, 2008.
 R. P. Zadeh, M. Haghparast, "A new reversible/quantum ternary comparator," Australian J. Basic and Applied Sciences, vol. 5, no. 12, pp. 2348-2355, 2011.
 D. Mukherjee, A. Chakrabarti, D. Bhattacherjee, "Synthesis of quantum circuits using genetic algorithm," Intern. J. of Recent Trends in Engineering, vol. 2, no. 1, pp. 212-216, 2009.
 A.I. Khan, N. Nusrat, S.M. Khan, M. Hasan, M.H.A. Khan, "Quantum realization of some ternary circuits using Muthukrishnan-Stroud gates," in Proc. 37th Intern. Symposium on Multiple-Valued Logic, (ISMVL,2007), Oslo, Norway, 13-16 May 2007, pp. 20. [Online]. Available: http://dx.doi.org/10.1109/ISMVL.2007.45.
 R. Wille, R. Drechsler. Toward a Design Flow for Reversible Logic. Springer Science+Business Media B.V., 2010.
 M Lukac, M Kameyama, M D Miller, M Perkowski, "High speed genetic algorithms in quantum logic synthesis: Low level parallelization vs. representation," J. Multiple-Valued Logic and Soft Comput., vol. 20, no. 1-2, pp. 89-120, 2013.
 V. Deibuk, I. Grytsku, "Optimal synthesis of reversible quantum adders using genetic algorithm," Int. J. Computing, vol. 12, no. 1, pp. 32-41, 2013.
 F. Z. Hadjam, C. Moraga, "RIMEP2: Evolutionary design of reversible digital circuits," ACM J, on Emerging Technologies in Computing Systems, vol. 11, no. 3, pp. 2348-2355, 2014. [Online]. Available: http://dx.doi.org/10.1145/2629534.
 K. Datta, I. Sengupta, H. Rahaman, and R. Drechsler, "An evolutionary approach to reversible logic synthesis using output permutation," in Proc. IEEE Design and Test Symposium (IDT), Doha, Qatar, 16-18 Dec. 2013, pp. 1-6. [Online]. Available: http://dx.doi.org/10.1109/IDT.2013.6727117.
 J. Jegier, P. Kerntopf, M. Szyprowski, "An approach to constructing reversible multi-qubit benchmarks with provably minimal implementations," in Proc. 13th IEEE Conference on Nanotechnology (IEEE-NANO,2013), Beijing, China, 5-8 Aug. 2013, pp. 99-104. [Online]. Available: http://dx.doi.org/10.1109/NANO.2013.6721041.
Vitaly DEIBUK, Andrij BILOSHYTSKYI
Yuriy Fedkovych Chernivtsi National University, 58012,Chernivtsi, Ukraine
TABLE II. 1-QUTRIT TERNARY PERMUTATIVE TRANSFORMS Input A Output A(0)=A A(+1)=A+1 A(+2)=A+2 A(01)=2A+1 A(02)=2A+2 A(12)=2A 0 0 1 2 1 2 0 1 1 2 0 0 1 2 2 2 0 1 2 0 1 TABLE III. COMPARATIVE EXPERIMENTAL RESULTS N-qutrit ternary comparators Ref  Ref  Proposed circuit Quantum Cost 236n - 169 56n + 6 18n - 8 Ancilla qutrits 13n - 7 5n + 3 2n - 1
|Printer friendly Cite/link Email Feedback|
|Author:||Deibuk, Vitaly; Biloshytskyi, Andrij|
|Publication:||Advances in Electrical and Computer Engineering|
|Date:||Aug 1, 2015|
|Previous Article:||Evaluation of Subspace Clustering Using Internal Validity Measures.|
|Next Article:||Characteristics of Overvoltage Protection with Cascade Application of Surge Protective Devices in Low-Voltage AC Power Circuits.|