The paper by Barenco et al. (1995) introduces a set of elementary gates that are universal for quantum computation. These gates include all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (XOR). The authors demonstrate that any unitary operation on an arbitrary number of bits (U(2^n)) can be expressed as a composition of these gates. They investigate the number of these gates required to implement other gates, such as generalized Deutsch-Toffoli gates, which 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. The paper provides upper and lower bounds on the exact number of elementary gates required to build various two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and observations about the number required for arbitrary n-bit unitary operations. The authors also discuss the efficiency of these constructions, showing that some simulations can be done with linear complexity in certain cases. Key results include: - Any unitary 2x2 matrix can be expressed as a product of specific one-bit and two-bit gates. - A general simulation of a two-bit gate (W) using basic gates (one-bit and two-bit XOR) is possible if and only if W is a special unitary matrix. - Efficient simulations of three-bit gates (W) are possible if phase shifts of the quantum states other than zero are allowed. - For n-bit networks, a simulation of a (n-1)-bit gate (U) can be achieved with Θ(n^2) basic operations. - A linear approximate simulation of a (n-1)-bit gate (U) can be achieved with Θ(n log(1/ε)) basic operations. The paper concludes with discussions on efficient general gate constructions and the potential for future research in quantum gate design.The paper by Barenco et al. (1995) introduces a set of elementary gates that are universal for quantum computation. These gates include all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (XOR). The authors demonstrate that any unitary operation on an arbitrary number of bits (U(2^n)) can be expressed as a composition of these gates. They investigate the number of these gates required to implement other gates, such as generalized Deutsch-Toffoli gates, which 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. The paper provides upper and lower bounds on the exact number of elementary gates required to build various two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and observations about the number required for arbitrary n-bit unitary operations. The authors also discuss the efficiency of these constructions, showing that some simulations can be done with linear complexity in certain cases. Key results include: - Any unitary 2x2 matrix can be expressed as a product of specific one-bit and two-bit gates. - A general simulation of a two-bit gate (W) using basic gates (one-bit and two-bit XOR) is possible if and only if W is a special unitary matrix. - Efficient simulations of three-bit gates (W) are possible if phase shifts of the quantum states other than zero are allowed. - For n-bit networks, a simulation of a (n-1)-bit gate (U) can be achieved with Θ(n^2) basic operations. - A linear approximate simulation of a (n-1)-bit gate (U) can be achieved with Θ(n log(1/ε)) basic operations. The paper concludes with discussions on efficient general gate constructions and the potential for future research in quantum gate design.