We consider a generic elementary gate sequence which is needed to implement a general quantum gate acting on $n$ qubits—a unitary transformation with $4^n$ degrees of freedom. For synthesizing the gate sequence, a method based on the so-called cosine-sine matrix decomposition is presented. The result is optimal in the number of elementary one-qubit gates, $4^n$, and scales more favorably than the previously reported decompositions requiring $4^n-2^{n+1}$ controlled NOT gates.

• Received 7 May 2004

DOI:https://doi.org/10.1103/PhysRevLett.93.130502