Minimization of ternary reversible logic cascades using a universal subset of generalized ternary gates

Universal MS gates for multiple-valued quantum circuits have been introduced recently by Muthukrishnan and Stroud, as well as their realization using ion trap devices [11]. No synthesis algorithm was however given neither experimental results of its application. Here we present an algorithm that creates a cascade of gates from the gate family introduced in [11]. The algorithm starts from ternary reversible function specification and always terminates. It does not require ancilla bits. The algorithm can find a solution for any reversible ternary function with n inputs and n outputs utilizing gates such as five single-qubit ternary inverter gates and the subset of two-qubit ternary Generalized Controlled Gates. The algorithm is a generalization of the algorithm presented by Dueck, Maslov, and Miller in [3] to ternary logic and new type of gates. A compaction algorithm is defined to improve the results of the basic algorithm. Three variants of search are compared.