We show that a set of gates that consists of all one-bit quantum gates (U(2)) and
the two-bit exclusive-or gate (that maps Boolean values \((x,y)\) to \((x,x \oplus y)\))
is universal in the sense that all unitary operations on arbitrarily many bits \(n\)
(U(\(2^n\))) can be expressed as compositions of these gates. We investigate the number
of the above gates required to implement other gates, such as generalized Deutsch-Toffoli
gates, that apply a specific U(2) transformation to one input bit if and only if the
logical AND of all remaining input bits is satisfied. These gates play a central role
in many proposed constructions of quantum computational networks. We derive upper
and lower bounds on the exact number of elementary gates required to build up a variety
of two-and three-bit quantum gates, the asymptotic number required for \(n\)-bit Deutsch-Toffoli
gates, and make some observations about the number required for arbitrary \(n\)-bit
unitary operations.