Synthesis of unitaries with Clifford+T circuits

We describe a new method for approximating an arbitrary $n$ qubit unitary with precision $\epsilon$ using a Clifford and T circuit with $O(4^{n}n(\log (1\mathrm{/}\epsilon )+n))$ gates. The method is based on rounding off a unitary to a unitary over the ring $\mathbb{Z}[i,1\mathrm{/}\sqrt{2}]$ and employing exact synthesis. We also show that any $n$ qubit unitary over the ring $\mathbb{Z}[i,1\mathrm{/}\sqrt{2}]$ with entries of the form $(a+b\sqrt{2}+ic+id\sqrt{2})\mathrm{/}{2}^k$ can be exactly synthesized using $O(4^{n}nk)$ Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring $O(3^{2^n}nk)$ elementary gates.