CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries

In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer \({\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^T\) ${\mathcal{J}}_n^{\mathit{CS}}\subset {\mathcal{J}}_n^T$ , where \({\mathcal {J}}_n^{CS}\) ${\mathcal{J}}_n^{\mathit{CS}}$ and \({\mathcal {J}}_n^T\) ${\mathcal{J}}_n^T$ are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying \({\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}\) ${\mathcal{J}}_n^{\mathit{Tof}}={\mathcal{J}}_n^{\mathit{CS}}$ , where \({\mathcal {J}}_n^{Tof}\) ${\mathcal{J}}_n^{\mathit{Tof}}$ is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.