Exact synthesis of elementary quantum gate circuits for reversible functions with don't cares

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.