Published In

Proceedings of IWLS. 2004

Document Type

Conference Proceeding

Publication Date



Reversable logic, Quantum computers, Quantum theory


We present a new type of quantum realizable reversible cascade. Next we present a new algorithm to synthesize arbitrary single-output ternary functions using these reversible cascades. The cascades use “Generalized Multi-Valued Gates” introduced here, which extend the concept of Generalized Ternary Gates introduced previously. While there were 216 GTGs, a total of 12 ternary gates of the new type are sufficient to realize arbitrary ternary functions. (The count can be further reduced to 5 gates, three 2-qubit and two 1-qubit). Such gates are realizable in quantum ion trap devices. For some functions, the algorithm requires fewer gates than results previously published [1, 5, 8, 14]. In addition, the algorithm also does conversion from arbitrary ternary logic to reversible logic at the cost of relatively small garbage. The algorithm is implemented here in ternary logic, but generalization to arbitrary radix is both straightforward and sees a reduction in growth of cost as the radix is increased.


This is the author's version of a paper which was subsequently published as "Synthesis of reversible circuits from a subset of Muthukrishnan-Stroud quantum realizable multi-valued gates." Proceedings of IWLS. 2004.

Persistent Identifier