  Optimal implementation of quantum gates is crucial for designing a quantum
computer. We consider the matrix representation of an arbitrary multiqubit
gate. By ordering the basis vectors using the Gray code, we construct the
quantum circuit which is optimal in the sense of fully controlled single-qubit
gates and yet is equivalent with the multiqubit gate. In the second step of the
optimization, superfluous control bits are eliminated, which eventually results
in a smaller total number of the elementary gates. In our scheme the number of
controlled NOT gates is $O(4^n)$ which coincides with the theoretical lower
bound.
