Synthesis of Unitaries with Clifford+T Circuits

We describe a new method for approximating an arbitrary n qubit unitary with precision ε using a Clifford and T circuit with O(4nn(log(1/ε)+n)) gates. The method is based on rounding off a unitary to a unitary over the ring Z[i,1/2–√] and employing exact synthesis. We also show that any n qubit unitary over the ring Z[i,1/2–√] with entries of the form (a+b2–√+ic+id2–√)/2k can be exactly synthesized using O(4nnk) 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(32nnk) elementary gates.