Synthesis of Quantum Multiple-Valued Circuits

D. Michael Miller, Dmitri Maslov and Gerhard W. Dueck

An r -valued m -variable reversible logic function maps each of the rm input patters to a unique output pattern.The synthesis problem is to realize a reversible function by a cascade of primitive reversible gates. In this paper,we present a simple heuristic algorithm that exploits the bidirectional synthesis possibility inherent in the reversibility of the specification.The primitive reversible gates considered here are MVL extensions of the well-known binary T ffoli gates.We analyze the structure of the gates that we use and show h w these gates can be easily simulated in a quantum technology. We present exhaustive results for the 9! 2-variable 3-valued reversible functions comparing the results of our algorithm to optimal results found by breadth-first search.We also show results for specific ternary examples including showing how the presented technique can be applied to the synthesis of a 3-input,3-valued adder which is not itself a reversible problem.When the circuit for the full adder is synthesized, we use it as an example of an approach to a circuit simplification, called the templates tool.Formalization and proper investigation of the templates simplification tool proposed in this paper is still under investigation.