  We propose the theory of Cayley graphs as a framework to analyse gate counts
and quantum costs resulting from reversible circuit synthesis. Several methods
have been proposed in the reversible logic synthesis literature by considering
different libraries whose gates are associated to the generating sets of
certain Cayley graphs. In a Cayley graph, the distance between two vertices
corresponds to the optimal circuit size. The lower bound for the diameter of
Cayley graphs is also a lower bound for the worst case for any algorithm that
uses the corresponding gate library. In this paper, we study two Cayley graphs
on the Symmetric Group $S_{2^n}$: the first, denoted by $I_n$, is defined by a
generating set associated to generalized Toffoli gates; and the second, the
hypercube Cayley graph $H_n$, is defined by a generating set associated to
multiple-control Toffoli gates. Those two Cayley graphs have degree $n2^{n-1}$
and order $2^n!$. Maslov, Dueck and Miller proposed a reversible circuit
synthesis that we model by the Cayley graph $I_n$. We propose a synthesis
algorithm based on the Cayley graph $H_n$ with upper bound of $(n-1)2^{n}+1$
multiple-control Toffoli gates. In addition, the diameter of the Cayley graph
$H_n$ gives a lower bound of $n2^{n-1}$.
