Document Type

Conference Proceeding

Publication Date



Computer algorithims, Quantum electronics, Logic circuits -- Design and construction


The choice of the best set of universal ternary gates for quantum circuits is an open problem. We create exact minimum cost ternary reversible gates with quantum multiplexers using the method of iterative deepening depth-first search (IDDFS) [25]. Such search is better for small problems than evolutionary algorithms or other search methods. Several new gates that are provably exact minimum cost have been discovered. These gates are next used as library building blocks in the minimization of larger ternary quantum circuits like highly testable GFSOP cascades [15,16] (that generalize ESOP) as well as the wave cascades [24] generalized to ternary logic. They are useful to design oracles for multivalued algorithms such as Deutsch-Jozsa [26] and Grover.


Paper originally presented at the RM Symposium, Oslo. 2007.

Persistent Identifier