We describe a new method for approximating an arbitrary n qubit unitary with precision ε using a Clifford and T circuit with O(4 n n(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 + b √ 2 + ic + id √ 2)/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. PACS numbers: 03.67.Lx Implementing a unitary operation using a universal gate set is a fundamental problem in quantum computing. The problem naturally arises when we want to implement some quantum algorithm on a fault tolerant quantum computer. Most fault tolerant protocols allow one to implement only Clifford circuits (those generated by CNOT, Hadamard and Phase gates). To achieve universal quantum computation one needs to add at least one non-Clifford gate. One of the common examples is gate. Many unitaries that occur in quantum algorithms cannot be implemented exactly using the Clifford and T gate set and must be approximated. However, the study of unitaries that can be implemented exactly using Cliffords and T has been useful for finding more efficient approximations. An example is an asymptotically optimal algorithm for approximating single qubit rotations using Clifford and T gates [11] . This algorithm achieves polynomial speed-up over the Solovay-Kitaev algorithm [2, 5] (which is applicable to generic universal gate sets). The key ingredients of this algorithm are: an algorithm for synthesizing optimal single qubit circuits given a unitary that can be implemented exactly [7] and an efficient round-off procedure that approximates an arbitrary single qubit unitary by the one that is exactly implementable. We extend these ideas to the approximate synthesis of unitaries acting on multiple qubits and show that any n qubit unitary can be approximated with precision ε using at most O (4 n n (log (1/ε) + n)) Clifford and T gates and two ancillae. Our procedure results in a slightly larger asymptotic number of gates in comparison to first using an asymptotically optimal decompositions of an n qubit unitary into O (4 n ) single qubit unitaries and CNOT gates [1, 8] and then approximating each single qubit unitary with Clifford and T circuit. Both approaches are asymptotically optimal when the number of qubits is fixed, according to the lower bounds established in [4, 6] . However, our decomposition is more directly related to
Kliuchnikov then introduced an algorithm which achieved an upper bound of O(4 n nk) gates, using a different method requiring at most two ancillas REF .
Synthesis of unitaries with Clifford+T circuits
ArXiv
ArXiv
Mathematics Physics Computer Science