Title :
Exact Synthesis of Elementary Quantum Gate Circuits for Reversible Functions with Don´t Cares
Author :
Grosse, Daniel ; Wille, Robert ; Dueck, Gerhard W. ; Drechsler, Rolf
Author_Institution :
Inst. of Comput. Sci., Univ. of Bremen, Bremen
Abstract :
Compact realizations of reversible logic functions are of interest in the design of quantum computers. In this paper we present an exact synthesis algorithm, based on Boolean satisfiability (SAT), that finds the minimal elementary quantum gate realization for a given reversible function. Since these gates work in terms of qubits, a multi-valued encoding is proposed. Don´t care conditions appear naturally in many reversible functions. Constant inputs are often required when a function is embedded into a reversible one. The proposed algorithm takes full advantage of don´t care conditions and automatically sets the constant inputs to their optimal values. The effectiveness of the algorithm is shown on a set of benchmark functions.
Keywords :
computability; logic design; multivalued logic circuits; quantum gates; boolean satisfiability; dont care conditions; elementary quantum gate circuits; exact synthesis; multivalued encoding; reversible logic functions; Circuit synthesis; Computer science; Encoding; Logic circuits; Logic functions; Minimization; Multivalued logic; Network synthesis; Niobium; Quantum computing; Boolean Satisfiability; Reversible Logic; Synthesis;
Conference_Titel :
Multiple Valued Logic, 2008. ISMVL 2008. 38th International Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
978-0-7695-3155-7
DOI :
10.1109/ISMVL.2008.42