Reversible Logic Synthesis with Cascades of New Gate Family



Ternary GFSOP Minimization using Kronecker Decision Diagrams and Their Synthesis with Quantum Cascades

Mozammel H. A. Khan$, Marek A. Perkowski*, Mujibur R. Khan$, and Pawel Kerntopf+

$Department of Computer Science and Engineering, East West University, 43 Mohakhali, Dhaka 1212, BANGLADESH. mhakhan@ewubd.edu and mrkhan@ewubd.edu

*Department of Electrical and Computer Engineering, Portland State University, 1900 SW 4th Avenue, Portland, OR 97201, USA. mperkows@ee.pdx.edu

+Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, POLAND. pke@ii.pw.edu.pl

Abstract

Ternary Galois Field Sum of Products (TGFSOP) expressions are found to be a good choice for ternary reversible logic and particularly for quantum cascaded realization of ternary functions. In this paper, we propose 5 ternary shift operations and various basic and composite ternary literals for defining TGFSOP expression. We propose 16 Ternary Galois Field Expansions (TGFE) using these literals and three new types of Ternary Galois Field Decision Diagrams (TGFDD) using the proposed expansions. We also propose a heuristic for creating optimal Kronecker TGFDD and methods for flattening the TGFDDs for determining near-minimum TGFSOP expressions. Besides, we propose quantum realizations for the 5 ternary shift gates and a ternary swap gate. We also propose a new generalization of ternary Toffoli gates with their implementation from truly realizable 2-qudit quantum primitives. Further, we propose a method of synthesizing multi-output TGFSOP using cascade of ternary shift gates, swap gate, and generalized Toffoli gate. Finally, we present experimental results to show the complexity of the decision diagrams, the resultant TGFSOP expressions, and the new quantum cascade for some ternary benchmark functions.

1. Introduction

Multiple-valued reversible logic and especially quantum logic synthesis methods are still very immature, though a number of works have been done [3-6, 33, 34, 65]. In general, quantum gates and circuits are described by unitary matrices of arbitrary type [66]. A subset of quantum gates corresponds to multiple-valued gates and these gates are described by unitary matrices that are in addition permutative [33]. Other MV quantum gates such as Chrestenson (that generalizes the binary quantum Hadamard gate) also exist, but in this paper we will be concerned only with designing a subcircuit of a quantum circuit that can be described by a permutative matrix. An original non-permutative matrix is decomposed to Kronecker and standard multiplications of smaller unitary matrices in order to have as much of the circuit described with permutative matrices. Synthesis for such matrices is much easier. It results from the above mentioned works that Galois Field Sum of Products (GFSOP) logic can be rather easily adapted for multiple-valued reversible logic synthesis. This is due to linear properties of such circuits and an analogy of Galois Addition operator to EXOR which is the base gate component in binary reversible logic. It has been also shown in [65] that Ternary Galois Field Sum of Products (TGFSOP) expressions are a natural choice for multiple-valued quantum logic synthesis. This is mostly due to easy realization of modulo-three addition in quantum hardware which makes this logic more natural than adaptations of the Min/Max type of logics. Therefore, efficient methods for representing and minimizing TGFSOP expressions are very important, as they can lead to first practical synthesis methods of MV quantum circuits with more than 3 qudits. Such expressions can be either realized directly in quantum cascades or become a starting point of factorization processes leading to factorized cascades [33, 65]. In this paper, we focus on minimization and quantum cascaded realization of TGFSOP.

The unit of memory (information) for binary quantum computation is a qubit, the simplest quantum system that exists in a linear superposition of two computational basis states labeled [pic] and [pic]. In 1996, Mattle et al [29] used the term trit for a ternary equivalent of qubit (however, qutrit is appropriate). In 1997, Chau [11] introduced the concept of a qudit, a d-dimensional quantum system that generalizes a qubit and has basis states [pic]. Subsequently, limited work was done in multi-valued quantum logic. The works of Chau [11], Rains [37] and Ashikhmin and Knill [7], extended quantum error-correcting codes to multi-valued logic for correcting codes in single and multiple qudits. Gottesman [19] and Aharonov and Ben-Or [2] developed fault-tolerant procedures for implementing two-qudit and three-qudit analogues of universal binary gates. Burlakov [10] proposed to use correlated photon pair to represent a qutrit. Since year 2000 the works have got momentum. Muthukrishnan and Stroud [32] developed multi-valued logic for multi-level quantum computing systems and showed their realizability in linear ion trap devices. However, this approach produces circuits of too large dimensions. Universality of n-qudit gates was discussed in [9, 32] but no design algorithms were given. Picton [35] presented an approach called Universal Architecture for multi-valued reversible logic but this approach produces circuits that are far from minimum and have no relation to quantum realization. Since 2001 Al-Rabadi et al proposed Galois Field approach to quantum logic synthesis (see [3-6, 34]). In this work Galois quantum matrices were proposed for swap and Toffoli gates, but without the proof that they can be built from only 1*1 and 2*2 gates. Several regular structures for multi-valued quantum logic were also proposed, including cascades, but these cascades do not allow realization of powers of GFSOP and are thus non-universal. This work was based on previous works on GFSOPs and similar forms of Galois and similar logic [1, 8, 12, 14-18, 20-25, 27, 31, 33, 36, 38-41], in which canonical expansions of Post literals and arbitrary functions were shown. However, no constructive methods for GFSOP and cascade minimization were given, nor programs were written for them. De Vos proposed two ternary 1*1 gates and two ternary 2*2 gates [13], but no synthesis method was proposed. New efficient reversible multi-valued gates were proposed in [26] and quantum realizations of multi-valued Toffoli gate in [33]. However, very little has been published on synthesis algorithms for multi-output multi-valued quantum circuits. Multiple-Valued Decision Diagrams (MDD) for many functions over multiple-valued domains are presented in the literature [16, 28, 30, 42 - 63]. These decision diagrams are mainly based on Reed-Muller like multiple-valued expressions and other algebraic forms. However, the TGFSOP expressions introduced in this paper require a special form of multiple-valued decision diagram because of the requirement of reversible realization of literals. Therefore, it is very important to look for efficient methods for representing, minimizing, and synthesizing multi-output TGFSOP functions.

The remaining of the paper is organized as follows. In Section 2 the ternary Galois field logic is introduced. In Section 3 a total of 16 Ternary Galois Field Expansions (TGFE) are proposed. In Section 4 we propose three new types of Ternary Galois Field Decision Diagrams (TGFDD) that use the expansions of Section 3. In Section 5 a heuristic for creating optimal Kronecker Ternary Galois Field Decision Diagram (KTGFDD) is presented. In Section 6 we discuss methods for flattening the Ternary Galois Field Decision Diagrams. Section 7 introduces multiple-valued quantum logic. In Section 8 we introduce some ternary permutation gates. In Section 9 quantum realizations of ternary shift gates are proposed, while Section 10 proposes quantum realization of ternary swap gate. In Section 11 a new generalization of ternary Toffoli gate is proposed with its true quantum realization. In Section 12 synthesis method for multi-output ternary GFSOP with quantum cascade of new generalized Toffoli gates is introduced. In Section 13 experimental results are presented. Section 14 gives conclusions about the paper and future research guidelines. In Section 15 acknowledgements are stated. In Section 16 references are given. Finally, in Section 17, some ternary benchmark functions are given as an appendix.

2. Ternary Galois Field Logic

Ternary Galois Field (TGF) consists of the set of elements [pic] and two basic binary operations – addition (denoted by +) and multiplication (denoted by ( or absence of any operator) as defined in Table 1. GF3 addition and multiplication are closed, i. e., for [pic], [pic] and [pic]. GF3 addition and multiplication are also commutative and associative, i. e., [pic] and [pic] (commutative), and [pic] and [pic] (associative). GF3 multiplication is distributive over addition, i. e., [pic].

Table 1. Ternary Galois Field (TGF) operations.

|+ |0 |1 |2 | |[pic] |0 |1 |2 |

|0 |0 |1 |2 | |0 |0 |0 |0 |

|1 |1 |2 |0 | |1 |0 |1 |2 |

|2 |2 |0 |1 | |2 |0 |2 |1 |

There are six reversible ternary unary operations corresponding to six possible permutations of 0, 1, and 2. These unary operations are called reversible ternary shift operations. We propose names of these six shift operations, their operator symbols and equations in Table 2. Among these six shift operations only single-shift, dual-shift (both also called Post cycles [28] and cyclic negations [30]), and self-dual-shift (also called inverse [16]) were previously used in the context of quantum computation. All these six shift operators can be built as reversible ternary gates. We propose gate symbols for these shift gates in Figure 1.

Table 2. Reversible ternary shift operations.

| |Operator Names, Symbols and Equations |

|Input |Buffer |Single-Shift |Dual-Shift |Self-Shift |Self-Single-Shift |Self-Dual-Shift |

|[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |

|0 |0 |1 |2 |0 |1 |2 |

|1 |1 |2 |0 |2 |0 |1 |

|2 |2 |0 |1 |1 |2 |0 |

Figure 1. Gate symbols for shift gates.

A ternary signal can be converted to one of the six forms using one of the reversible ternary shift gates as shown in Figure 2. We have used this technique in our cascades to change signal form.

Figure 2. Conversion of one shift form to another shift form using ternary shift gates.

Literals of a ternary variable x can be defined as follows:

Constant literals: Ternary constants 1 = (111) and 2 = (222) may be used as literals of a ternary variable [pic].

Basic literals: There are six basic literals of a ternary variable [pic] corresponding to six possible permutations of the elements 0, 1, and 2, which are reversible in nature:

[pic] Normal literal

[pic] Single-Shift literal

[pic] Dual-Shift literal

[pic] Self-Shift literal

[pic] Self-Single-Shift literal

[pic] Self-Dual-Shift literal

Self-Shift of a basic ternary literal (a basic literal multiplied by 2) yields another basic ternary literal as follows (can be verified from Table 1):

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

1-Reduced Post literals: 1-Reduced Post literal (1-RPL) of a variable [pic] is defined as follows:

[pic] (1)

For ternary Galois field the 1-Reduced Post literals of a variable x are [pic], [pic], and [pic]. These 1-Reduced Post literals are related with the basic literals as follows (can be verified from Table 1):

[pic] (2.a)

[pic] (2.b)

[pic] (2.c)

[pic] (2.d)

[pic] (2.e)

[pic] (2.f)

[pic] (3.a)

[pic] (3.b)

[pic] (3.c)

[pic] (3.d)

[pic] (3.e)

[pic] (3.f)

[pic] (4.a)

[pic] (4.b)

[pic] (4.c)

[pic] (4.d)

[pic] (4.e)

[pic] (4.f)

Composite literals: There are some other literals, which are products of two basic literals each, as below:

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

A product term is a TGF product of: a constant, basic literals, and composite literals of ternary variables. For example, [pic] is a product term. Ternary Galois Field sum of products (TGFSOP) expression is TGF sum of some product terms. For example, [pic] is a TGFSOP.

3. Ternary Galois Field Expansions

A ternary function f has the following cofactors:

[pic] cofactor of f with respect to [pic]

[pic] cofactor of f with respect to [pic]

[pic] cofactor of f with respect to [pic]

We propose the concept of Galois Difference (GD) as the Galois sum of two or more cofactors of a function. The various Ternary Galois Differences (TGD) of a ternary function f are:

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

Any ternary function can be expanded using the following Shannon Ternary Galois Field Expansion (STGFE):

Theorem 1: A ternary function f can be expanded with respect to the variable x as follows:

[pic] (TGFE 1) (5)

Proof. The theorem is proved using perfect induction. If [pic], then [pic], [pic], and [pic]. In that case (5) becomes [pic]. If [pic], then [pic], [pic], and [pic]. In that case (5) becomes [pic]. Finally, if [pic], then [pic], [pic], and [pic]. In that case (5) becomes [pic]. Thus, we have (5). QED

Eight different versions of this expansion are possible by substituting the equivalent composite literals, [pic], [pic], and [pic].

Any ternary function can be expanded using any of the following 9 Pseudo-Davio Ternary Galois Field Expansions (PDTGFE):

Theorem 2: A ternary function f can be expanded with respect to the variable x as follows:

[pic] (TGFE 2) (6)

[pic] (TGFE 3) (7)

[pic] (TGFE 4) (8)

[pic] (TGFE 5) (9)

[pic] (TGFE 6) (10)

[pic] (TGFE 7) (11)

[pic] (TGFE 8) (12)

[pic] (TGFE 9) (13)

[pic] (TGFE 10) (14)

Proof. By substituting (2.a), (3.a), and (4.a) in (5), we have

[pic]

Thus we have (6).

[pic]

Thus we have (7).

[pic]

Thus we have (8).

[pic]

Thus we have (9).

[pic]

Thus we have (10).

[pic]

Thus we have (11).

[pic]

Thus we have (12).

[pic]

Thus we have (13).

[pic]

Thus we have (14). QED

Four different versions of (6) are possible by substituting equivalent composite literals, [pic] and [pic]. Four different versions of (7) are possible by substituting equivalent composite literals, [pic] and [pic]. Four different versions of (8) are possible by substituting equivalent composite literals, [pic] and [pic]. Four different versions of (9) are possible by substituting equivalent composite literals, [pic] and [pic]. Four different versions of (10) are possible by substituting equivalent composite literals, [pic] and [pic]. Four different versions of (11) are possible by substituting equivalent composite literals, [pic] and [pic]. Two different versions of (12) are possible by substituting equivalent composite literals, [pic]. Two different versions of (13) are possible by substituting equivalent composite literals, [pic]. Two different versions of (14) are possible by substituting equivalent composite literals, [pic].

Any ternary function can be expanded using one of the following 6 Davio Ternary Galois Field Expansions (DTGFE):

Theorem 3: A ternary function f can be expanded with respect to the variable x as follows:

[pic] (TGFE 11) (15)

[pic] (TGFE 12) (16)

[pic] (TGFE 13) (17)

[pic] (TGFE 14) (18)

[pic] (TGFE 15) (19)

[pic] (TGFE 16) (20)

Proof. By substituting (2.a), (3.a), and (4.a) in (5), we have

[pic]

Thus we have (15).

By substituting (2.d), (3.d), and (4.d) in (5), we have

[pic]

Thus we have (16).

By substituting (2.c), (3.c), and (4.c) in (5), we have

[pic]

Thus we have (17).

By substituting (2.e), (3.e), and (4.e) in (5), we have

[pic]

Thus we have (18).

By substituting (2.b), (3.b), and (4.b) in (5), we have

[pic]

Thus we have (19).

By substituting (2.f), (3.f), and (4.f) in (5), we have

[pic]

Thus we have (20). QED

4. Ternary Galois Field Decision Diagrams

We propose three new types of ternary decision diagrams useful for reversible logic design - the Kronecker Ternary Galois Field Decision Diagram (KTGFDD), the Pseudo-Kronecker Ternary Galois Field Decision Diagram (PKTGFDD), and the Free Kronecker Ternary Galois Field Decision Diagram (FKTGFDD).

In KTGFDD the nodes of the same level have the same variable and the same TGFE. For example, the decision diagram of Figure 3.a is a KTGFDD. In a Kronecker Ternary Galois Field Decision Tree (KTGFDT) for an n-variable function f, the number of possible variable ordering is [pic]. In each level we can choose one of the 16 TGFEs. So, we have [pic] possible choices of TGFEs for n levels. Therefore, the total number of possible KTGFDTs for the function f is [pic]. For [pic] we have 24,576 KTGFDTs. The number of KTGFDDs will also be of the same exponential order. Therefore, finding an optimal KTGFDD based on any optimality criteria is an NP-hard problem.

In PKTGFDD the nodes of the same level have the same variable, but each of the nodes may have one of the 16 TGFEs. For example, the decision diagram of Figure 3.b is a PKTGFDD. In general, a PKTGFDD requires fewer nodes than a KTGFDD. The number of paths terminating at constant 1-leaf and 2-leaf of a PKTGFDD is also, in general, less than that of KTGFDD. In a Pseudo-Kronecker Ternary Galois Field Decision tree (PKTGFDT) for an n-variable function f, the number of possible variable orderings is [pic]. However, the total number of possible choices of TGFEs is [pic] for [pic] nodes. Therefore, the total number of possible PKTGFDTs for the function f is [pic]. For [pic] we have 27,021,597,764,222,976 PKTGFDTs. The number of PKTGFDDs is also of the same exponential order and finding an optimal PKTGFDD is also a NP-hard problem.

In FKTGFDD each of the paths may have a different variable ordering and each of the nodes may have one of the 16 TGFEs. For example, the decision diagram of Figure 3.c is a FKTGFDD. In general, a FKTGFDD requires fewer nodes than a PKTGFDD. The number of paths terminating at constant 1-leaf and 2-leaf is also, in general, less than that of PKTGFDD. In a Free-Kronecker Ternary Galois Field Decision Tree (FKTGFDT) for an n-variable function f, the number of possible variable orderings is [pic]. The total number of possible choices of TGFEs is [pic] for [pic] nodes. Therefore, the total number of possible PKTGFDTs for the function f is [pic]. For [pic] we have 108,086,391,056,891,904 PKTGFDTs. The number of FKTGFDDs is also of the same exponential order and finding an optimal FKTGFDD is a NP-hard problem.

Figure 3. Three types of Ternary Galois Field Decision Diagrams - (a) KTGFDD, (b) PKTGFDD, and (c) FKTGFDD for the function [pic].

5. Creating Optimal Kronecker Ternary Galois Field Decision Diagram

We create a Kronecker Ternary Galois Field Decision Diagram (KTGFDD) in which the number of nodes as well as the number of paths terminating at constant 1-leaf and 2-leaf is minimum so that after flattening of the decision diagram the number of product terms in the resultant GFSOP is the minimum. For this purpose we propose a heuristic in which we minimize the number of 1s and 2s (conversely maximize the number of 0s) in the truth vectors of each sub-function at every level of the KTGFDD with the hope that local optimization will lead to global optimization. For the requirement of the heuristic we propose the following weight functions.

Definition 1: Given an n-variable ternary function f represented as a truth vector, where the locations are designated from 0 to [pic]. For [pic]

[pic]= number of occurrences of [pic] consecutive 0s starting from [pic] location

[pic]= number of occurrences of [pic] consecutive 1s starting from [pic] location

[pic] = number of occurrences of [pic] consecutive 2s starting from [pic] location

where, [pic].

For example, let [pic]. Then [pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], and [pic].

The proposed heuristic is as follows:

1. If [pic], where m is the number of outputs, then use TGFEs 1 and 11 to 16, otherwise use all TGFEs. The reason behind this selection is that if the truth vector contains less than one-third 0s, then using TGFEs 11 to 16 will produce more 0s because of the use of the Galois differences [pic], [pic], [pic], [pic], [pic], [pic], and [pic].

2. For each of the n variables, find expansion for the TGFEs selected in step 1. For each expansion compute [pic] to [pic]and [pic] to [pic].

3. Find the expansion with highest [pic]. The reason behind this selection is that one or more cofactors will be straight constant 0. In case of a tie, break it using highest values of [pic] up to [pic]. This selection will produce constant 0 cofactors in the later levels in the KTGFDD. For further tie, break it by using highest values of [pic] up to [pic]. This selection will produce a constant 0 or 1 or 2 cofactors in the later levels in the KTGFDD. For further tie, break it arbitrarily. The selected expansion is the expansion for the root of the KTGFDD.

4. For the next level of the KTGFDD, repeat the steps 1 to 3 for the remaining [pic] variables.

5. Repeat steps 1 to 4 until all the variables are exhausted.

The heuristic is illustrated using a 2-input 2-output ternary function [pic] and [pic]. Here [pic]. So we used TGFEs 1 and 11 to 16 for both the variables x and y. The weights are shown in Table 3. There are four ties as shown bold. We select variable y with TGFE 14 arbitrarily as the expansion for the roots. Then the resulting six sub-functions are [pic], [pic], [pic], [pic], [pic], and [pic]. Here [pic]. So, we used TGFEs 1 to 16. The weights are also shown in Table 3. There are two ties and we break it arbitrarily by selecting TGFE 10. The created optimal KTGFDD is shown in Figure 4.

Table 3. Weights of various expansions for the example function.

| |Level 1 |Level 2 |

|TGFE |x |y |x |

| |[pic] |[pic] |[pic] |

|1 |0, 4, 2, 14 |0, 4, 2, 14 |10, 8 |

|2 | | |10, 8 |

|3 | | |9, 9 |

|4 | | |11, 7 |

|5 | | |11, 7 |

|6 | | | 9, 9 |

|7 | | |10, 8 |

|8 | | |13, 5 |

|9 | | |12, 6 |

|10 | | |13, 5 |

|11 |2, 10, 0, 8 |2, 9, 1, 9 |11, 7 |

|12 |2, 10, 0, 8 |2, 9, 1, 9 |11, 7 |

|13 |2, 9, 1, 9 |2, 10, 0, 8 |12, 6 |

|14 |2, 9, 1, 9 |2, 10, 0, 8 |12, 6 |

|15 |2, 9, 1, 9 |2, 9, 1, 9 |11, 7 |

|16 |2, 9, 1, 9 |2, 9, 1, 9 |11, 7 |

Figure 4. Optimal KTGFDD for the 2-input 2-output function [pic] and [pic].

6. Flattening of Ternary Galois Field Decision Diagrams

Flattening a Ternary Galois Field Decision Diagram (TGFDD) yields a ternary Galois Field Sum of Products (TGFSOP) expressions for the function represented by the TGFDD.

Different possible types of edges for TGFE1 in a TGFDD are shown in Figure 5. The literal associated with each of the edge types is given below:

Figure 5. Different types of edges for TGFE1.

Edge Types for TGFE1

Edge-0: [pic]

Edge-1: [pic]

Edge-2: [pic]

Edge-0,1: [pic]

Edge-0,2: [pic]

Edge-1,2: [pic]

In a similar way different types of edges and their corresponding literals (or sum of literals) for TGFE2 to TGFE16 can be determined and are given below:

Edge Types for TGFE2

Edge-01: [pic]

Edge-1: [pic]

Edge-2: [pic]

Edge-01,1: [pic]

Edge-01,2: [pic]

Edge-1,2: [pic]

Edge Types for TGFE3

Edge-0: [pic]

Edge-01: [pic]

Edge-2: [pic]

Edge-0,01: [pic]

Edge-0,2: [pic]

Edge-01,2: [pic]

Edge Types for TGFE4

Edge-02: [pic]

Edge-1: [pic]

Edge-2: [pic]

Edge-02,1: [pic]

Edge-02,2: [pic]

Edge-1,2: [pic]

Edge Types for TGFE5

Edge-0: [pic]

Edge-1: [pic]

Edge-02: [pic]

Edge-0,1: [pic]

Edge-0,02: [pic]

Edge-1,02: [pic]

Edge Types for TGFE6

Edge-0: [pic]

Edge-12: [pic]

Edge-2: [pic]

Edge-0,12: [pic]

Edge-0,2: [pic]

Edge-12,2: [pic]

Edge Types for TGFE7

Edge-0: [pic]

Edge-1: [pic]

Edge-12: [pic]

Edge-0,1: [pic]

Edge-0,12: [pic]

Edge-1,12: [pic]

Edge Types for TGFE8

Edge-0: [pic]

Edge-1: [pic]

Edge-012: [pic]

Edge-0,1: [pic]

Edge-0,012: [pic]

Edge-1,012: [pic]

Edge Types for TGFE9

Edge-0: [pic]

Edge-012: [pic]

Edge-2: [pic]

Edge-0,012: [pic]

Edge-0,2: [pic]

Edge-012,2: [pic]

Edge Types for TGFE10

Edge-012: [pic]

Edge-1: [pic]

Edge-2: [pic]

Edge-012,1: [pic]

Edge-012,2: [pic]

Edge-1,2: [pic]

Edge Types for TGFE11

Edge-0: [pic]

Edge-112: [pic]

Edge-012: [pic]

Edge-0,112: [pic]

Edge-0,012: [pic]

Edge-112,012: [pic]

Edge Types for TGFE12

Edge-0: (111)=1

Edge-122: [pic]

Edge-012: [pic]

Edge-0,122: [pic]

Edge-0,012: [pic]

Edge-122,012: [pic]

Edge Types for TGFE13

Edge-1: [pic]

Edge-022: [pic]

Edge-012: [pic]

Edge-1,022: [pic]

Edge-1,012: [pic]

Edge-022,012: [pic]

Edge Types for TGFE14

Edge-1: [pic]

Edge-002: [pic]

Edge-012: [pic]

Edge-1,002: [pic]

Edge-1,012: [pic]

Edge-002,012: [pic]

Edge Types for TGFE15

Edge-2: [pic]

Edge-001: [pic]

Edge-012: [pic]

Edge-2,001: [pic]

Edge-2,012: [pic]

Edge-001,012: [pic]

Edge Types for TGFE16

Edge-2: [pic]

Edge-011: [pic]

Edge-012: [pic]

Edge-2,011: [pic]

Edge-2,012: [pic]

Edge-011,012: [pic]

A product of literals corresponding to edges along a path from the root to a leaf of the TGFDD gives the TGF product of the represented function. Paths ended at the constant 0-leaf do not contribute to the TGFSOP and the TGF product corresponding to a path ended at the constant 2-leaf is multiplied by 2 to get the required product term. Sum of all such products gives the TGFSOP expression for the function represented in the TGFDD. For example, the TGFSOP expressions derived from the three TGFDDs of Figure 3 are

KTGFDD: [pic]

PKTGFDD: [pic]

FKTGFDD: [pic]

Each of the paths terminating at constant 1-leaf and 2-leaf yields a TGF product term. Therefore, the number of product terms in a TGFSOP expression is exactly equal to such paths. If we designate the number of such paths for KTGFDD, PKTGFDD, and FKTGFDD by the notations path(KTGFDD), path(PKTGFDD), and path(FKTGFDD), respectively, then in general the following relationship holds:

path(KTGFDD) ( path(PKTGFDD) ( path(FKTGFDD)

Similarly, if we designate the number of nodes in KTGFDD, PKTGFDD, and FKTGFDD by the notations node(KTGFDD), node(PKTGFDD), and node(FKTGFDD), respectively, then in general the following relationship also holds:

node(KTGFDD) ( node(PKTGFDD) ( node(FKTGFDD)

7. Fundamentals of Multi-Valued Quantum Logic

In multi-valued (MV) Quantum Computing (QC), the unit of memory (information) is qudit. MV quantum logic operations manipulate qudits, which are microscopic entities such as a photon’s polarization or atomic spin. Ternary logic values of 0, 1, and 2 are represented by a set of distinguishable different states of a qutrit. These states can be a photon’s polarizations or an elementary particle’s spins. After encoding these distinguishable quantities into multiple-valued constants, qutrit states are represented by [pic], [pic], and [pic], respectively.

Qudits exist in a linear superposition of states, and are characterized by a wavefunction [pic]. As an example ([pic]), it is possible to have light polarizations other than purely horizontal or vertical, such as slant 45( corresponding to the linear superposition of [pic]. In ternary logic, the notation for the superposition is [pic], where (, (, and ( are complex numbers. These intermediate states cannot be distinguished, rather a measurement will yield that the qutrit is in one of the basis states, [pic], [pic], or [pic]. The probability that a measurement of a qutrit yields state [pic] is [pic], state [pic] is [pic], and state [pic] is [pic]. The sum of these probabilities is one. The absolute values are required since, in general, (, ( and γ are complex quantities.

Pairs of qutrits are capable of representing nine distinct states,[pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], and [pic], as well as all possible superpositions of the states. This property may be mathematically described using the Kronecker product (tensor product) operation ( [66]. The Kronecker product of matrices is defined as follows:

[pic]

As an example, consider two qutrits with [pic] and [pic]. When the two qutrits are considered to represent a state, that state [pic] is the superposition of all possible combinations of the original qutrits, where

[pic]

Superposition property allows qubit states to grow much faster in dimension than classical bits, and qudits faster than qubits [32]. In a classical system, n bits represent [pic] distinct states, whereas n qutrits correspond to a superposition of [pic] states. In the above formula some coefficient can be equal to zero, so there exist a constraint bounding the possible states in which the system can exist. As observed in [32] – “Allowing d to be arbitrary enables a tradeoff between the number of qudits making up the quantum computer and the number of levels in each qudit”. An output of a gate is obtained by multiplying the unitary matrix of this gate by the vector of Hilbert space corresponding to this gate’s input state (see examples below). A resultant unitary matrix of arbitrary quantum circuit is created by matrix or Kronecker multiplications of composing subcircuits. These all contribute to difficulty in understanding the concepts of quantum computing and creating efficient analysis, simulation, verification and synthesis algorithms for QC. Generally, however, we believe that much can be learned from the history of Electronic Computer Aided Design as well as from MV logic theory and design, and the lessons learned there should be used to design efficient CAD tools for MV quantum computing. Many lessons can be taken especially from a subarea of logic synthesis theory that is called “EXOR Logic” or “Reed-Muller Logic” and also from spectral approaches to synthesis.

In terms of logic operations, anything that changes a vector of qudit states to another qudit satisfying measurement probability properties can be considered as an operator (unitary matrix). These phenomena can be modeled using the analogy of a “quantum circuit”. In a quantum circuit, wires do not carry ternary constants but correspond to 3-tuples of complex values, (, (, and γ. Quantum logic gates of the circuit map the complex values on their inputs to complex values on their outputs. As mentioned, operation of quantum gates is described by matrix operations. Any quantum circuit is a composition of parallel and serial connections of blocks, from small to large. Serial connection of blocks corresponds to multiplication of their (unitary) matrices. Parallel connection corresponds to Kronecker multiplication of their matrices. So, theoretically, the analysis, simulation and verification are easy and can be based on matrix methods. Practically they are tough because the dimensions of the matrices grow exponentially. All these become much easier when one deals only with permutative matrices, which are equivalent to multi-output truth tables. We deal with such special class in this paper. In binary case such circuits constitute the most of the quantum array layout and are often grouped together, so decomposition to permutation and non-permutation unitary matrices may be easy. Such circuits exist also in many well-known quantum algorithms, such as Deutsch, Grover, Shorr, error correcting and fault tolerant quantum computing circuits, etc. [66].

8. Some Ternary Permutation Quantum Gates

Any unitary matrix represents a quantum gate. If a unitary matrix has only one 1 in every column and the remaining elements are 0, then such a matrix is called a permutation matrix. A quantum gate represented by a permutation matrix is called a permutation quantum gate. In this paper we concentrate only on permutation quantum gates.

Figure 6 shows a 2*2 ternary Feynman gate. Here A is the controlling input and B is the controlled input. The output P is equal to the input A and the output Q is GF3 sum of A and B. If [pic], then [pic] and the ternary Feynman gate acts as a copying gate. The ternary 2*2 Feynman gate is practically realizable, for instance see [32].

Figure 6. 2*2 ternary Feynman gate.

Another very useful 2*2 gate is a Generalized Ternary gate (GTG gate) [33] as shown in Figure 7. Here, input A is the controlling input and input B is the controlled input. The output P is equal to the input A. The controlling input A controls a conceptual ternary multiplexer (a conditional gate) that can be realized using quantum technology such as ion traps [32]. If [pic], then the output Q is the x shift of the input B. Similarly, if [pic], then the output Q is the y shift of the input B and if [pic], then the output Q is the z shift of the input A. Here shift means all ternary shift operations including the Buffer (simple quantum wire). Quantum realizations of the shift gates are discussed in Section 9. As the Conditional gate and the Shift gates are realizable in quantum technology, the GTG gate is a truly realizable ternary quantum gate. Observe that the De Vos gates [13] and the ternary Feynman gates are special cases of this gate. This gate was introduced for the first time in [33] as a ternary gate but it belongs to the general type of generalized controlled quantum gates from [73,74].

Figure 7. 2*2 Generalized Ternary gate.

A very useful gate for multiple input circuit synthesis is a 3*3 Toffoli gate as shown in Figure 8. Design of GFSOP arrays and factorized arrays corresponding to TGFDDs is based on these gates. Here the inputs A and B are the controlling inputs and the input C is the controlled input. The output P is equal to the input A, the output Q is equal to the input B, and the output R is equal to [pic], where [pic] and + are GF3 multiplication and addition, respectively.

Figure 8. 3*3 Toffoli gate.

Any m*m (m > 2) gate is very difficult to realize in quantum technology, since interaction of more than two particles is nearly impossible to control. Therefore, these gates should be realized from 1*1 and 2*2 gates. As ternary Feynman gate and GTG gate are relatively easy to realize, they are treated as primitive gates for realizing other gates. A 3*3 Toffoli gate is realizable from 1*1 Shift gates, 2*2 Feynman gate, and 2*2 GTG gate as discussed in Section 11.

9. Quantum Realization of Ternary Shift Gates

The unitary matrices describing the five shift gates (except the buffer, which is quantum wire) are given in Figure 9. In principle these gates can be realized as 1*1 quantum gates using basic technology dependent quantum primitives. However, we also propose realization of these shift gates using ternary Feynman primitives in Figure 10. These realizations require two to three quantum wires.

Figure 9. Unitary matrices of ternary shift gates.

Figure 10. Quantum realization of ternary shift gates.

10. Quantum Realization of Ternary Swap Gate

As wire crossing is not permitted in quantum logic, swap gate is essential for quantum logic synthesis. The unitary matrix for ternary swap gate is given in Figure 11. We also propose quantum realization of ternary quantum swap gate using Feynman primitive in Figure 12.

Figure 11. Unitary matrix for ternary quantum swap gate.

Figure 12. Quantum realization of ternary swap gate.

11. A New Generalization of Ternary Toffoli Gate

We propose a ternary generalization of Toffoli gate in Figure 13, where [pic] is an arbitrary ternary function of the input variables [pic]. By inspection of the truth table it can be shown that the gate is a ternary reversible gate. Depending on [pic] and the value of n many possible gates can be constructed.

Figure 13. A new generalized ternary Toffoli gate.

The method of creating an arbitrary reversible gate is shown in Figure 14. In this method an arbitrary non-reversible one-output function controls an arbitrary reversible operator. [pic] is an inverse gate of gate G. H is a reversible gate that includes arbitrary controlled ternary function. Several garbage signals can be internally created between G and [pic]. But, as [pic] gate uses these garbage signals to restore the constants, they do not contribute dramatically to the increase of the scratchpad register width (the number of quantum wires in the circuit). The original inputs are restored at the output terminals, thus allowing the inputs to be used in the next gates in the cascade. Of course, this approach is restricted to some types of cascades like those of “generalized sum-of-products type” which reuse inputs.

Figure 14. Principle of creating arbitrary reversible gate.

For TGFSOP the function [pic] will essentially be GF3 products of some of the input variables. Using the above method of creating arbitrary reversible gate, the generalized ternary Toffoli gate of Figure 13 with [pic] can be realized using 2*2 ternary Shift gates, 2*2 ternary Feynman gate, and 2*2 GTG gates as shown in Figure 15. The Figure 15 is self-explanatory and, by verifying the truth tables of each signal, reader can verify the realization. The first five GTG gates are used to realize the Galois product of the inputs A and B. The last five GTG gates are the inverse gates of the first five GTG gates for restoring the input constants. Using the same technique generalized ternary Toffoli gate with any number of inputs and outputs and for any arbitrary controlling function can be implemented using truly realizable quantum technology.

Figure 15. Realization of the generalized ternary Toffoli gate with [pic].

12. Synthesis of Multi-Output TGFSOP using Quantum Cascade of Generalized Ternary Toffoli Gates

For synthesizing TGFSOP using cascade of ternary Toffoli gates, we assume that [pic]. The general pattern of a cascade to implement TGFSOP functions using ternary Toffoli gates is shown in Figure 16. It is obvious that to make it quantum realizable, in general, the swap gates have to be added. It should be observed that variables are replicated to allow realization of composite literals.

Figure 16. General pattern of a cascade to implement ternary functions using ternary Toffoli gates.

Theorem. Any TGFSOP function can be realized in a cascade of reversible ternary Toffoli, ternary Swap, and 5 ternary shift gates using at most [pic]quantum wires, where n is the number of input variables and m is the number of outputs.

Proof. To realize a TGFSOP function, product terms can be implemented and added with other product terms using ternary Toffoli gates (see Figure 16). As wire crossing is not permitted in quantum circuits, ternary swap gates must be used. Ternary reversible literals can be implemented using ternary shift gates along the quantum wire. However, to realize composite literals, two copies of the variables will be needed. Therefore, [pic] quantum wires will be required for n input variables. Such a variable copying can be done using a ternary Feynman gate as a copying gate. Realization of shift gates requires quantum wires for constants 1 and 2 (see Figure 10). Moreover, the realization of the generalized ternary Toffoli gate requires a constants 0 and 1 (see Figure 15). So, 3 quantum wires will be needed for these three input constants 0, 1, and 2. Finally, m quantum wires will be needed for outputs. Therefore, a total of [pic]quantum wires will be needed for realizing any TGFSOP function. However, for a particular function, copies of all input variables may not be required and, therefore, [pic]is the maximum number of quantum wires needed to realize a TGFSOP function. QED

We assumed in this proof that a Galois multiplication can be done for any number of inputs, as shown for binary case by Barenco at al [69]. If for certain technological reason this technique cannot be used, the counterpart of the standard decomposition of multi-input Toffoli gate to 3-input Toffoli gates with constant inputs from [66,69] is used. For ternary case, every two-input multiplication gate being a part of the multi-input Toffoli gate requires three input/output constants. We have no space here to discuss efficient realizations of Ternary Toffoli gates and other similar gates (such as wave cascades of Mishchenko et al [72]) in both layout variants and they will be a subject of a separate paper.

For reducing the number of swap gates in the proposed cascade, we use the product ordering and variable ordering. For this purpose we use the following heuristic:

1. For each product term determine the cost (number of basic literals) and frequency of occurrence in the multi-output TGFSOP.

2. In the cascade, arrange the product terms according to their decreasing order of costs. This arrangement will reduce the number of swaps among the wires for inputs. In case of tie, break it by arranging the product terms according to their decreasing order of frequency. This arrangement will reduce the number of swaps among the wires for the function outputs. For further tie, break it arbitrarily.

3. Keeping the order of the product terms as determined in step 2, place swap gates and shift gates as needed.

The heuristic is illustrated for the functions of Figure 16. Frequency of occurrences, costs, and ordering of the product terms are shown in Table 4. In some quantum realization technologies it is not possible to realize a gate on arbitrary two (or more) quantum wires. This requires adding swap gates. For a cascade from Figure 16 we assume that gates can be build only on geometrically adjacent wires. The resultant cascade is shown in Figure 17. However, the assumption of adjacency here is only an example. For instance in NMR technology, one can assume other rules deciding for which groups of wires in the cascade the gates can be build [33]. Thus, some limited crossing of vertical and horizontal wires may be allowed. Which wires are groupable depends on neighborhood of atomic bonds in a molecule (atoms correspond to quantum wires and gates are build based on direct bonds) [66 – 71].

Table 4. Frequency of occurrences, costs, and ordering of the product for the functions [pic] and [pic].

|Product |[pic] |[pic] |Cost |Freq. |Order |

|[pic] |x | |4 |1 |2 |

|[pic] |x |x |4 |2 |1 |

|[pic] |x | |2 |1 |4 |

|[pic] |x |x |2 |2 |3 |

|[pic] | |x |1 |1 |5 |

Figure 17. Quantum cascaded realization of the functions [pic] and [pic]. In order to explain the role of adding swap gates for technology related TGFSOP realization, in this layout it is assumed that a gate can be realized only on geometrically adjacent wires. Other rules of adjacency exist for various technologies.

The proposed realization method automatically accomplishes the conversion of non-reversible ternary function to reversible ternary function, which is not a trivial problem by itself and has been not presented in the literature. Our conversion, however, does not produce the quantum scratchpad register with the minimum width.

13. Experimental Results

We have written C++ programs for creating optimal KTGFDDs for multiple-output ternary functions and for flattening the KTGFDD for deriving the resultant TGFSOP expression. As no standard ternary benchmark functions are available in the literature, we have created some ternary benchmark functions as given in the Appendix of Section 16 and performed experimentation with them. Besides, we experimented with two benchmark functions (mm3 and pal3) from [64]. The results of the experimentation are given in Table 5. The fourth column of the table shows the number of nodes in the KTGFDD and the fifth column shows the number of product terms in the resultant TGFSOP expression.

For prodn functions, the number of nodes is exactly equal to the number of inputs for up to 8 input functions. The number of products is 1 for up to 8 input functions, which is the exact minimum solution for prodn functions.

For sumn functions, the number of products is exactly equal to the number of inputs for up to 5 input functions, which is the exact minimum solution for sumn functions.

For 3cy2, 4cy2, 4cy3, 5cy2, 5cy4, and 6cy5 functions, the number of products is exactly equal to the number of inputs, which is the exact minimum solution.

For sqsumn functions, the number of products is exactly equal to the number of inputs for up to 5 input functions, which is the exact minimum solution for sqsumn functions.

For a2bcc and mul2 functions, the number of products is 2, which is the exact minimum solution for this function. For other functions, we have no theoretical results to make any comment. However, the results seem to be adequately moderate.

Table 5. Number of nodes in KTGFDD and number of resulting products in TGFSOP for some ternary benchmark functions.

|Function |Input |Output |Nodes |Products |

|prod2 |2 |1 |2 |1 |

|prod3 |3 |1 |3 |1 |

|prod4 |4 |1 |4 |1 |

|prod5 |5 |1 |5 |1 |

|prod6 |6 |1 |6 |1 |

|prod7 |7 |1 |7 |1 |

|prod8 |8 |1 |8 |1 |

|prod9 |9 |1 |15 |3 |

|prod10 |10 |1 |38 |15 |

|sum2 |2 |1 |3 |2 |

|sum3 |3 |1 |5 |3 |

|sum4 |4 |1 |7 |4 |

|sum5 |5 |1 |9 |5 |

|sum6 |6 |1 |21 |9 |

|sum7 |7 |1 |53 |74 |

|sum8 |8 |1 |168 |252 |

|sum9 |9 |1 |437 |1117 |

|sum10 |10 |1 |905 |2759 |

|3cy2 |3 |1 |5 |3 |

|4cy2 |4 |1 |9 |4 |

|4cy3 |4 |1 |9 |4 |

|5cy2 |5 |1 |12 |5 |

|5cy3 |5 |1 |15 |7 |

|5cy4 |5 |1 |11 |5 |

|6cy2 |6 |1 |24 |9 |

|6cy3 |6 |1 |34 |24 |

|6cy4 |6 |1 |24 |9 |

|6cy5 |6 |1 |15 |6 |

|sqsum2 |2 |1 |3 |2 |

|sqsum3 |3 |1 |5 |3 |

|sqsum4 |4 |1 |7 |4 |

|sqsum5 |5 |1 |9 |5 |

|sqsum6 |6 |1 |20 |18 |

|sqsum7 |7 |1 |58 |63 |

|sqsum8 |8 |1 |203 |295 |

|sqsum9 |9 |1 |428 |855 |

|sqsum10 |10 |1 |1019 |2506 |

|avg2 |2 |1 |4 |4 |

|avg3 |3 |1 |10 |7 |

|avg4 |4 |1 |20 |27 |

|avg5 |5 |1 |34 |69 |

|avg6 |6 |1 |54 |183 |

|avg7 |7 |1 |75 |516 |

|avg8 |8 |1 |175 |1438 |

|avg9 |9 |1 |423 |4396 |

|avg10 |10 |1 |1029 |11802 |

|a2bcc |3 |1 |5 |2 |

|thadd |2 |2 |5 |4 |

|tfadd |3 |2 |10 |10 |

|mul2 |2 |2 |4 |2 |

|mul3 |3 |2 |8 |5 |

|mami4 |4 |2 |14 |7 |

|mm3 |5 |1 |18 |18 |

|pal3 |6 |1 |12 |27 |

We have also written C++ program for creating quantum cascade of multi-output TGFSOP expressions. We experimented with the TGFSOPs of the benchmark functions of Table 5 and the results are given in Table 6. In Table 6 the fourth column shows the number of copying gates, fifth column shows the number of ternary shift gates, the sixth column shows the number of ternary swap gates, and the last column shows the number of generalized ternary Toffoli gates needed in the cascade.

For prodn function, the number of swap gates is zero for up to 8 input functions. For sumn function, the number of swap gates is zero for up to 5 input functions. For 3cy2, 4cy3, 5cy4, and 6cy5 functions, the number of swap gates is zero. For sqsumn function, the number of swap gates is zero for up to 5 input functions. For avgn, the number of swap gates is zero for 4 and 5 input functions. But from the results of Table 6 it can be seen that there is a scope of reducing the number of shift gates by modifying the heuristic.

Table 6. Numbers of copying gates, shift gates, swap gates, and Toffoli gates for some ternary benchmark functions.

|Function |Input |Output |Copy |Shift |Swap |Toffoli |

|prod2 |2 |1 |0 |2 |0 |1 |

|prod3 |3 |1 |0 |2 |0 |1 |

|prod4 |4 |1 |0 |4 |0 |1 |

|prod5 |5 |1 |0 |4 |0 |1 |

|prod6 |6 |1 |0 |6 |0 |1 |

|prod7 |7 |1 |0 |6 |0 |1 |

|prod8 |8 |1 |0 |8 |0 |1 |

|prod9 |9 |1 |7 |15 |1 |3 |

|prod10 |10 |1 |9 |47 |107 |15 |

|sum2 |2 |1 |0 |2 |0 |2 |

|sum3 |3 |1 |0 |3 |0 |3 |

|sum4 |4 |1 |0 |3 |0 |4 |

|sum5 |5 |1 |0 |5 |0 |5 |

|sum6 |6 |1 |5 |14 |33 |9 |

|sum7 |7 |1 |6 |249 |596 |74 |

|sum8 |8 |1 |7 |750 |1450 |252 |

|sum9 |9 |1 |8 |3545 |3317 |1117 |

|sum10 |10 |1 |9 |10301 |3523 |2759 |

|3cy2 |3 |1 |0 |6 |0 |3 |

|4cy2 |4 |1 |0 |12 |2 |4 |

|4cy3 |4 |1 |0 |11 |0 |4 |

|5cy2 |5 |1 |0 |5 |6 |5 |

|5cy3 |5 |1 |0 |18 |4 |7 |

|5cy4 |5 |1 |0 |13 |0 |5 |

|6cy2 |6 |1 |4 |15 |31 |9 |

|6cy3 |6 |1 |5 |62 |9 |24 |

|6cy4 |6 |1 |5 |28 |17 |9 |

|6cy5 |6 |1 |0 |18 |0 |6 |

|sqsum2 |2 |1 |2 |0 |0 |2 |

|sqsum3 |3 |1 |3 |0 |0 |3 |

|sqsum4 |4 |1 |4 |0 |0 |4 |

|sqsum5 |5 |1 |5 |0 |0 |5 |

|sqsum6 |6 |1 |6 |31 |76 |18 |

|sqsum7 |7 |1 |7 |201 |868 |63 |

|sqsum8 |8 |1 |8 |1112 |1900 |295 |

|sqsum9 |9 |1 |9 |3025 |3406 |855 |

|sqsum10 |10 |1 |10 |9988 |5700 |2506 |

|avg2 |2 |1 |2 |7 |4 |4 |

|avg3 |3 |1 |3 |15 |4 |7 |

|avg4 |4 |1 |4 |79 |0 |27 |

|avg5 |5 |1 |5 |215 |0 |69 |

|avg6 |6 |1 |6 |582 |24 |183 |

|avg7 |7 |1 |7 |1628 |52 |516 |

|avg8 |8 |1 |8 |4536 |64 |1438 |

|avg9 |9 |1 |9 |14084 |1782 |4465 |

|avg10 |10 |1 |10 |39382 |68 |11802 |

|a2bcc |3 |1 |1 |2 |2 |2 |

|thadd |2 |2 |2 |5 |1 |4 |

|tfadd |3 |2 |3 |11 |19 |10 |

|mul2 |2 |2 |2 |2 |1 |2 |

|mul3 |3 |2 |3 |4 |5 |5 |

|mami4 |4 |2 |4 |14 |51 |7 |

|mm3 |5 |1 |5 |53 |24 |18 |

|pal3 |6 |1 |6 |104 |32 |27 |

14. Conclusions

Designing a cascade of reversible “permutative” gates is one of few fundamental problems in quantum computing. Among the multiple-valued quantum circuits the GFSOP cascades are so far the most fundamental ones and they are mainly discussed. Various Ternary Galois Field Decision Diagrams are a starting point to create such cascades and can be used also to create other types of quantum cascades. They are thus of a basic importance in multi-valued quantum logic synthesis.

In this paper we proposed 16 Ternary Galois Field Expansions (TGFE) which generalize to ternary and adapt to reversible logic the concepts of (binary) Shannon and Davio expansions used in Kronecker Decision Diagrams. We also proposed three new types of Ternary Galois Field Decisions Diagrams (TGFDD) suitable for reversible ternary logic synthesis. They are the Kronecker Ternary Galois Field Decision Diagram (KTGFDD), the Pseudo-Kronecker Galois Field Decision Diagram (PKTGFDD), and the Free-Kronecker Ternary Galois Field Decision Diagram (FKTGFDD). We proposed an efficient heuristic for creating the new KTGFDD with the reduced node counts and also reduced path counts that terminate at constant 1-leaf and 2-leaf. This method is applicable not only to KTGFDD but to PKTGFDD and FKTGFDD as well. We also proposed a method of flattening the TGFDDs for determining the near optimal Ternary Galois Field Sum of Products (TGFSOP) expression for ternary functions. As our optimal KTGFDD reduces the paths terminating at constant 1-leaf and 2-leaf, the number of product terms in the resulting TGFSOP will also be reduced. The experimental results show that for many functions the resultant TGFSOPs are exact minimum solutions.

In the proposed TGFSOP expression we used five (except buffer) reversible ternary unary operators (only three were previously used), which can be built as quantum 1*1 ternary gates. We proposed a new ternary generalization of Toffoli gate with discussion of its quantum realization. We also proposed a TGFSOP-based reversible logic synthesis method using quantum cascade of ternary shift gates, swap gates, and generalized Toffoli gates. We have chosen cascaded realization, since cascades have the same number of internal signals at every level with small garbage or no garbage at all. Cascades can also be easily represented using standard quantum notation introduced by Feynman. Crossing of horizontal wires is not allowed in quantum technologies. In some technologies, gates can be realized only on some non-adjacent quantum wires [33]. In this case using a ternary swap gate is useful in logic synthesis of ternary reversible circuits. We proposed quantum realization of a ternary swap gate for the first time. For creating the proposed cascade, we used a rudimentary heuristic for variable ordering and product ordering with the intention of reducing the number of swap gates. The experimental results show that the method generates a large number of swap gates, which needs to be reduced in the future research.

The quantum realizations of binary gates are called pseudo-binary, so by analogy we will call our circuits introduced here – pseudo-ternary. They will be both called “permutation circuits” because their unitary matrices are permutation matrices.

The proposed multi-output TGFSOP synthesis method is applicable to all kinds of polynomial expansions presented so far in literature as well as new expansions that have composite literals.

Further research includes: (i) determining heuristics for creating optimal PKTGFDDs and FKTGFDDs that can potentially lead to simpler TGFSOP expressions and their corresponding quantum cascades, as well as other types of quantum circuits, (ii) investigating more efficient heuristic for reducing both the number of swap gates and shift gates in the proposed cascades, (iii) synthesizing circuits for realistic gate-realization constraints for any specific quantum technology (such as for instance NMR [70, 71] and (iv) creating a good library of ternary benchmark functions.

15. Acknowledgements

The authors would like to thank Prof. Soonchil Lee and Dr. Jae-Seung Lee for help in understanding NMR-based quantum computing. However, the authors are the only ones to be blamed for possible mistakes and inaccuracies of this paper. The authors also thank Professors Soonchil Lee, Radomir Stankovic, Tsutomu Sasao and Bogdan Falkowski, and Dr. Anas Al-Rabadi, for help in finding literature and useful feedback on some part of the draft paper.

16. References

1] K.J. Adams and J. McGregor, “Comparison of Different Features of Quaternary Reed-Muller Canonical Forms and Some New Statistical Results”, Proc. 32nd IEEE Int. Symp. on Multiple-Valued Logic, Boston, Massachusetts, 2002, pp. 83-88.

2] D. Aharonov and M. Ben-Or, “Polynomial Simulations of Decohered Quantum Computers”, (Online preprint quant-ph/9611029), 37th Annual Symp. on Foundations of Computer Science, Burlington, Vermont, October 1996, pp. 4655.

3] A. Al-Rabadi, “Synthesis and Canonical Representations of Equally Input-Output Binary and Multiple-Valued Galois Quantum Logic: Decision Trees, Decision Diagrams, Quantum Butterflies, Quantum Chrestenson Gate, Multiple-Valued Bell-Einstein-Podolsky-Rosen Basis States”, Technical Report #2001/008, ECE Dept., PSU, August 2001.

4] A. Al-Rabadi, “Novel Methods for Reversible Logic Synthesis and Their Application to Quantum Computing”, Ph. D. Thesis, PSU, Portland, Oregon, USA, October 24, 2002.

5] A. Al-Rabadi, L. W. Casperson, M. Perkowski and X. Song, “Multiple-Valued Quantum Logic”, Booklet of 11th Workshop on Post-Binary Ultra-Large-Scale Integration Systems (ULSI), Boston, Massachusetts, May 15, 2002, pp. 35-45.

6] A. Al-Rabadi and M. Perkowski, “Multiple-Valued Galois Field S/D Trees for GFSOP Minimization and their Complexity”, Proc. 31st IEEE Int. Symp. on Multiple-Valued Logic, Warsaw, Poland, May 22-24, 2001, pp. 159-166.

7] A. Ashikhmin and E. Knill, “Non-binary quantum stabilizer codes”,

8] B. Benjauthrit and I.S. Reed, “Galois switching functions and their applications”, IEEE Trans. on Computers, Vol. C-25, No. 1, 1976, pp. 79-86.

9] J. L. Brylinski and R. Brylinski, “Universal Quantum Gates”, Mathematics of Quantum Computation, CRC Press, 2002, LANL e-print quant-ph/010862.

10] A. V. Burlakov, M. V. Chekhova, O.V. Karabutova, D.N. Klyshko, and S. P. Kulik, “Polarization state of a biphoton: quantum ternary”, Physical Review A, Vol. 60, R4209, 1999.

11] H. F. Chau, “Correcting quantum errors in higher spin systems”, Physical Review A, Vol. 55, R839-R841, 1997.

12] M. Cohn, “Switching function canonical form over integer fields”, Ph.D. Thesis, Harvard University, 1960.

13] A. De Vos, B. Raa, and L. Storme, “Generating the group of reversible logic gates”, Journal of Physics A: Mathematical and General, Vol. 35, 2002, pp. 7063-7078.

14] K. M. Dill, K. Ganguly, R. J. Safranek, and M. A. Perkowski, “A New Zhegalkin Galois Logic”, Proc. 3rd Int. Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Oxford Univ., U.K., September 1997, pp. 247-257.

15] E. Dubrova, “Evaluation of m-valued Fixed Polarity Generalizations of Reed-Muller Canonical Form”, Proc. 29th Int. Symp. on Multiple-Valued Logic, Freiburg, Germany, 1999, pp. 92-98.

16] E. Dubrova and J.C. Muzio, “Generalized Reed-Muller canonical form of a multiple-valued algebra”, Multiple-Valued Logic - An International Journal, 1996, pp. 104-109.

17] B.J. Falkowski and S. Rahardja, “Efficient computation of quaternary fixed polarity Reed-Muller expansions”, IEE Proc., Part E, Vol. 142, No. 5, 1995, pp. 345-352.

18] M.U. Garaev and R.G. Faradzhev, “On an analog of Fourier expansion over Galois Fields and its applications to problem of generalized sequential machines”, Izv. Akad. Nauk Azerb. SSR, Ser. Fiz.- Techn. Math. Nauk, No. 6, 1965, pp. 1-68.

19] D. Gottesman, “Fault-tolerant quantum computation with higher-dimensional systems”, Chaos, Solitons, Fractals, Vol. 10, No. 10, 1999, pp. 1749-1758.

20] D.H. Green, “Ternary Reed-Muller switching functions with fixed and mixed polarities”, Int. J. Electronics, Vol. 67, No. 5, 1989, pp. 761-775.

21] D.H. Green, “Reed-Muller expansions with fixed and mixed polarities over GF(4)”, IEE Proc. Part E Vol. 137, No. 5, 1990, pp. 380-388.

22] D.H. Green and I.S. Taylor, “Modular representations of multiple-valued logic systems”, IEE Proc., Part E, Vol. 121, No.2, 1974, pp. 166-172.

23] B. Harking, and C. Moraga, “Efficient derivation of Reed-Muller expansions in multiple-valued logic systems”, Proc. 22nd Int. Symp. on Multiple-Valued Logic, Sendai, Japan, May 27-29 1992, pp. 436-441.

24] D. Jankovic, R.S. Stankovic, and R. Drechsler, “Efficient Calculation of Fixed-Polarity Polynomial Expressions for Multiple-Valued Logic Functions”, Proc. 32nd IEEE Int. Symp. on Multiple-Valued Logic, Boston, Massachusetts, May 2002, pp. 76-82.

25] U. Kalay, D.V. Hall, and M. Perkowski, “Easily Testable Multiple-Valued Galois Field Sum-of-Products Circuits”, Multiple Valued Logic - An International Journal, Vol. 5, 2000, pp. 507-528.

26] P. Kerntopf, “Maximally efficient binary and multi-valued reversible gates”, Booklet of 10th Intl Workshop on Post-Binary Ultra-Large-Scale Integration Systems (ULSI), Warsaw, Poland, May 2001, pp. 55-58.

27] K. L. Kodandapani and R.V. Setur, “Multi-valued algebraic generalization of Reed-Muller canonical forms”, Proc. 4th Symp. on Multiple-Valued Logic, 1974, pp. 505-544.

28] L. Macchiarulo and P. Civera, “Ternary Decision Diagrams with Inverted Edges and Cofactors – an Application to Discrete Neural Networks Synthesis”, Proc. 28th IEEE Int. Symp. on Multiple-Valued Logic, 1998, pp. 58-63.

29] K. Mattle, H. Weinfurter, P.G. Kwiat, and A. Zeilinger, “Dense Coding in Experimental Quantum Communication”, Physical Review Letters, Vol. 76, 1996, pp. 4656-4659.

30] D. M. Miller and R. Drechsler, “On the Construction of Multi-Valued Decision Diagrams”, Proc. 32nd IEEE Int. Symp. on Multiple-Valued Logic, Boston, Massachusetts, 2002, pp. 245-253.

31] C. Moraga, R.S. Stankovic, and D. Jankovic, “Complexity analysis of Reed-Muller-Fourier and Galois Field Representations of Four-Valued Functions”, Research Report 668, Dept. of Comp. Science, Univ. of Dortmund, 1998.

32] A. Muthukrishnan, and C. R. Stroud, Jr., “Multivalued logic gates for quantum computation”, Physical Review A, Vol. 62, No. 5, Nov. 2000, 052309/1-8.

33] M. Perkowski, A. Al-Rabadi, and P. Kerntopf, “Multiple-Valued Quantum Logic Synthesis”, Proc. of 2002 International Symposium on New Paradigm VLSI Computing, Sendai, Japan, December 12-14, 2002, pp. 41-47.

34] M. Perkowski, A. Al-Rabadi, P. Kerntopf, A. Mishchenko, and M. Chrzanowska-Jeske, “Three-Dimensional Realization of Multivalued Functions Using Reversible Logic”, Booklet of 10th Int. Workshop on Post-Binary Ultra-Large-Scale Integration Systems (ULSI), Warsaw, Poland, May 2001, pp. 47- 53.

35] P. Picton, “A Universal Architecture for Multiple-Valued Reversible Logic”, Multiple-Valued Logic - An International Journal, Vol. 5, 2000, pp. 27-37.

36] D.K. Pradhan, “A multi-valued algebra based on finite fields”, Proc. 4th Symp. on Multiple-Valued Logic, 1974, pp. 95-112.

37] E. M. Rains, “Nonbinary Quantum Codes”, IEEE Trans. on Information Theory, Vol. 45, 1999, pp. 1827 –1832.

38] R.S. Stankovic, D. Jankovic, and C. Moraga, “Reed-Muller-Fourier versus Galois Field Representations of Four-Valued Logic Functions”, Proc. 3rd Int. Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Sept. 19-20, 1997, Oxford, UK, pp. 269-278.

39] R. S. Stankovic, and C. Moraga, “Reed-Muller-Fourier representations of multiple-valued functions over Galois fields of prime cardinality”, Proc. IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Hamburg, Germany, September 16-17, 1993, pp. 115-124.

40] R. S. Stankovic, C. Moraga, “Reed-Muller-Fourier representations of multiple-valued functions”, In Recent Developments in Abstract Harmonic Analysis with Applications in Signal Processing, Nauka, Belgrade, 1996, pp. 205-216.

41] T.C. Wesslekamper, “Divided difference method for Galois switching functions”, IEEE Trans. on Computers, Vol. C-27, No. 3, 1978, pp. 232-238.

42] R. Drechsler, “Evaluation of Static Variable Ordering Heuristics for MDD Construction., Proc. 32nd IEEE Int. Symposium on Multiple-Valued Logic, Boston, Massachusetts, May 15-18, 2002, pp. 254-260.

43] R. Drechsler, D. Jankovic, and R.S Stankovic, “Generic Implementation of Decision Diagram Packages in MVL”, Proc. Euromicro Conference (EUROMICRO’99), Vol. 1, Sept. 8-10, 1999, Milan, Italy, p.1352.

44] R. Drechsler and D.M. Miller, “Decision Diagrams in Multi-Valued Logic., Multiple-Valued Logic – An International Journal, vol. 4, 1998, pp. 1-8.

45] C. Files and M.A. Perkowski, “New Multi-valued Functional Decomposition Algorithm Based on MDDs”, IEEE Trans. on Computer-Aided Design, vol. 14, 2000, pp. 1081-1086.

46] S. Hassoun, T. Sasao, and R.K. Brayton (eds.), Logic Synthesis and Verification, Kluwer Academic Publishers, Boston/Dordrecht/London 2002, Chapters 11 and 15.

47] D. Jankovic, W. Günther, and R. Drechsler, “Lower Bound Sifting for MDDs”, Proc. 30th IEEE Int. Symposium on Multiple-Valued Logic, Portland, Oregon, USA. May 23-25, 2000, pp. 193-198.

48] T. Kam, T. Villa, R. Brayton, and A. Sangiovanni-Vincentelli, “Multi-Valued Decision Diagrams: Theory and Applications”, Multiple-Valued Logic – An International Journal, vol. 4, 1998, pp. 9-24.

49] D.M. Miller, “Multiple-Valued Logic Design Tools”, Proc. 23rd IEEE Int. Symposium on Multiple-Valued Logic, Sacramento, California, USA, May 24-27, 1993, pp. 2-11.

50] D.M. Miller, and R. Drechsler, “Implementing a Multiple-Valued Decision Diagram Package”, Proc. 28th IEEE Int. Symposium on Multiple-Valued Logic, Fukuoka, Japan, 27-29 May, 1998, pp. 52-57.

51] H. Sack, E. Dubrova, and C. Meinel, “Mod-p Decision Diagrams: A Data Structure for Multiple-Valued Functions”, Proc. 30th IEEE Int. Symposium on Multiple-Valued Logic, Portland, Oregon, USA, May 23-25, 2000, pp. 233-238.

52] T. Sasao, “Ternary Decision Diagrams: Survey”, Proc. 27th IEEE Int. Symposium on Multiple-Valued Logic, Antigonish, Nova Scotia, Canada, May 28-30, 1997, pp. 241-250.

53] T. Sasao and J.T. Butler, “Planar Multiple-Valued Decision Diagrams”, Proc. 25th IEEE Int. Symposium on Multiple-Valued Logic, Bloomington, Indiana, USA, May 23 - 25, 1995, pp. 28-35.

54] T. Sasao and J.T. Butler, “A Method to Represent Multiple-Output Switching Functions by Using Multi-Valued Decision Diagrams”, Proc. 26th IEEE Int. Symposium on Multiple-Valued Logic, Santiago de Compostela, Spain, May 19-31, 1996, pp. 248- 254.

55] R.S. Stankovic, “Functional Decision Diagrams for Multiple-Valued Functions”, Proc. 25th IEEE Int. Symposium on Multiple-Valued Logic, Bloomington, Indiana, USA, May 23 - 25, 1995, pp. 284-289.

56] R.S. Stankovic and T. Sasao, “Decision Diagrams for Discrete Functions: Classification and Unified Interpretation”, Proc. Asia and South Pacific Design Automation Conference, Yokohama, Japan, February 10-13, 1998, pp. 439-446.

57] F. Schmiedle, W. Günther, and R. Drechsler, “Dynamic Re-Encoding During MDD Minimization”, Multiple- Valued Logic – An International Journal, 2002, pp. 625-643.

58] P. Kerntopf, “Multiple-Valued Decision Diagrams based on generalized Shannon expansion”, Booklet of 12th Workshop on Post-Binary Ultra-Large-Scale Integration Systems (ULSI), Tokyo, May 16, 2003, pp. 9-16.

59] D.M. Miller and G.W. Dueck, “On the Size of Multiple-Valued Decision Diagrams”, Proc. 33rd IEEE Int. Symp. On Multiple-Valued Logic, Tokyo, May 16-19, 2003, pp. 235-240.

60] D.V. Popel and R. Drechsler, “Efficient Minimization of Multiple-Valued Decision Diagrams for Incompletely Specified Function”, Proc. 33rd IEEE Int. Symp. On Multiple-Valued Logic, Tokyo, May 16-19, 2003, pp. 241-246.

61] S. Nagayama and T. Sasao, “Compact Representations of Logic Functions using Heterogeneous MDDs”, Proc. 33rd IEEE Int. Symp. On Multiple-Valued Logic, Tokyo, May 16-19, 2003, pp. 247-252.

62] D.M. Miller and R. Drechsler, “Augmented Sifting of Multiple-Valued Decision Diagrams”, Proc. 33rd IEEE Int. Symp. On Multiple-Valued Logic, Tokyo, May 16-19, 2003, pp. 375-382.

63] J.T. Butler and T. Sasao, “On the Average Path Length in Decision Diagrams of Multiple-Valued Functions”, Proc. 33rd IEEE Int. Symp. On Multiple-Valued Logic, Tokyo, May 16-19, 2003, pp. 383-390.

64]

65] M.H.A. Khan, M.A. Perkowski, and P. Kerntopf, “Multi-Output Galois Field Sum of Products Synthesis with New Quantum Cascades”, Proc. 33rd IEEE Int. Symp. On Multiple-Valued Logic, Tokyo, May 16-19, 2003, pp. 146-153.

66] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.

67] M.D. Price, S.S. Somaroo, A.E. Dunlop, T.F. Havel, and D.G. Cory, “Generalized methods for the development of quantum logic gates for an NMR quantum information processor”, Physical Review A, Vol. 60, No. 4, October 1999, pp. 2777-2780.

68] M.D. Price, S.S. Somaroo, C.H. Tseng, J.C. Core, A.H. Fahmy, T.F. Havel, and D.G. Cory, “Construction and Implementation of NMR Quantum Logic Gates for Two Spin Systems”, Journal of Magnetic Resonance, 140, 1999, pp. 371-378.

69] A. Barenco et al., “Elementary Gates For Quantum Computation”, Physical Review A 52, 1995, pp. 3457-3467.

70] J. Kim, J-S Lee, and S. Lee, “Implementation of the refined Deutsch-Jozsa algorithm on a three-bit NMR quantum computer”, Physical Review A, Volume 62, 022312, 2000.

71] J. Kim, J-S. Lee, and S. Lee, “Implementing unitary operators in quantum computation,” Physical Review A, Volume 62, 032312, 2000.

72] A. Mishchenko, M. Perkowski, “Logic Synthesis of Reversible Wave Cascades”, Proc. 11th IEEE/ACM Int’l Workshop on Logic and Synthesis, 2002, pp. 197-202.

73] Andrei Khlopotine, Marek Perkowski and Pawel Kerntopf, “`Reversible Logic Synthesis by Iterative Compositions”, Proc. IWLS 2002, June 4-7, 2002

74] Martin Lukac, Mikhail Pivtoraiko, Alan Mischenko, and Marek Perkowski, “`Automated Synthesis of Generalized Reversible Cascades using Genetic Algorithms”,' Proceedings of Symposium on Boolean Problems, September, 2002, Freiberg, Germany.

17. Appendix: Ternary Benchmark Function Created

prodn: input [pic]; output [pic]. [Output is the GF3 product of n input variables.]

sumn: input [pic]; output [pic]. [Output is the GF3 sum of n input variables.]

ncyr: input [pic]; output [pic]. [A ternary GFSOP function of n input variables, where the products consist of r input variables in cyclic order. Example: For 3cy2, [pic].]

sqsumn: input [pic]; output [pic]. [Output is the GF3 sum of squares of n input variables]

avgn: input [pic]; output [pic]. [Output is the integer part of the average of n input variables expressed as mod 3 value.]

a2bcc: input [pic]; output [pic]. [An arbitrary function [pic] expressed as mod 3 value.]

thadd: input a b; output [pic] ,[pic]. [Ternary half-adder]

tfadd: input a b c; output [pic], [pic]. [Ternary full-adder]

mul2: input a b; output [pic], [pic]. [2-trit ternary multiplier]

mul3: input a b c; output [pic], [pic]. [3-trit ternary multiplier]

mami4: input a b c d; output [pic] [pic]. [Four input arbitrary function, where the output y is maximum of the first two inputs and the output z is the minimum of the last two inputs.]

-----------------------

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download