Hybrid GA Synthesis of Ternary Reversible Circuits Using Max-Min Algebra
Musharrat Khan and Jacqueline E. Rice
Ternary reversible logic is a promising choice for low-power implementation and is also physically realizable in quantum computation. Two previous methods for ternary reversible circuit synthesis are based on TGFSOPs and Max-Min algebra. Both require high quantum cost and a large number of ancilla inputs. We propose an alternative Max-Min algebra-based method, where ternary logic functions are represented as Max-Min expressions and are realized using multiple-controlled unary gates. We also propose quantum-level realizations of multiple-controlled unary gates. We introduce minimization of Max-Min expressions using K-maps and then propose a hybrid genetic algorithm-based method for minimization and synthesis of ternary reversible circuits. We experimented with 24 benchmark functions of up to five variables. On average our method requires 41.36% lower quantum cost and 35.72% fewer ancilla inputs than the method based on TGFSOPs, and 74.39% fewer ancilla inputs than the previously proposed Max-Min algebra-based method.
Keywords: Ternary logic, reversible logic, quantum logic, max-min algebra, ternary sub-functions, minimization of max-min expressions, multiple-controlled unary gates, post-synthesis quantum cost reduction, hybrid genetic algorithm.