Improved Decomposition of Multiple-Control Ternary Toffoli Gates Using Muthukrishnan-Stroud Quantum Gates

In conventional binary reversible circuit synthesis, reversible gates are decomposed into quantum gates using some standard quantum gate library. In recent years there has been increased attention in synthesis using ternary reversible gates since it leads to a reduction in the number of lines. However, very few works exist that address the problem of decomposing ternary reversible gates based on some ternary quantum gate library. Most of these works use Muthukrishnan-Stroud (M-S) gates for decomposition of ternary Toffoli gate, and they use a naive approach that requires an exponential (in number of control lines) number of M-S gates. Also the number of ancilla lines required is (\(c-1\)), where c is the number of control lines. The present paper proposes a method for decomposing ternary Toffoli gates to M-S gates that requires less number of ancilla lines, and also requires a number of M-S gates that is linear in c. A template-based post-decomposition optimization step has also been used to further reduce the number of M-S gates required. Decomposition results for up to 16 control lines have been presented.