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_nn(log(1/\epsilon )+n))\) gates. The method is based on rounding off a unitary to a unitary over the ring \(Z[i,1/\sqrt{2–√}]\) and employing exact synthesis. We also show that any \(n\) qubit unitary over the ring \(Z[i,1/\sqrt{2–√}]\) with entries of the form \((a+b\sqrt{2–√}+ic+id\sqrt{2–√})/2_k\) can be exactly synthesized using \(O(4_nnk)\) 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.