Ternary Max-Min algebra with application to reversible logic synthesis

Ternary reversible circuits are 0.63 times more compact than equivalent binary reversible circuits and are suitable for low-power implementations. Two notable previous works on ternary reversible circuit synthesis are the ternary Galois field sum of products (TGFSOP) expression-based method and the ternary Max-Min algebra-based method. These methods require high quantum cost and large number of ancilla inputs. To address these problems we develop an alternative ternary Max-Min algebra-based method, where ternary logic functions are represented as Max-Min expressions and realized using our proposed multiple-controlled unary gates. We also show realizations of multiple-controlled unary gates using elementary quantum gates. We develop a method for minimization of ternary Max-Min expressions of up to four variables using ternary K-maps. Finally, we develop a hybrid Genetic Algorithm (HGA)-based method for the synthesis of ternary reversible circuits. The HGA has been tested with 24 ternary benchmark functions with up to five variables. On average our method reduces quantum cost by 41.36% and requires 35.72% fewer ancilla inputs than the TGFSOP-based method. Our method also requires 74.39% fewer ancilla inputs than the previous ternary Max-Min algebra-based method.

Authors

• Khan, Musharrat
• University of Lethbridge. Faculty of Arts and Science

• ancilla inputs
• quantum cost
• ternary Max-Min algebra
• ternary reversible circuits
• unary gates

Identifier

hdl:10133/4840

OAI identifier oai:identifier

oai:opus.uleth.ca:10133/4840