Semi-Clifford operations, structure of ${\mathcal{C}}_k$ hierarchy, and gate complexity for fault-tolerant quantum computation

Teleportation is a crucial element in fault-tolerant quantum computation and a complete understanding of its capacity is very important for the practical implementation of optimal fault-tolerant architectures. It is known that stabilizer codes support a natural set of gates that can be more easily implemented by teleportation than any other gates. These gates belong to the so-called ${\mathcal{C}}_k$ hierarchy introduced by Gottesman and Chuang [Nature (London) 402, 390 (1999)]. Moreover, a subset of ${\mathcal{C}}_k$ gates, called semi-Clifford operations, can be implemented by an even simpler architecture than the traditional teleportation setup [X. Zhou, D. W. Leung, and I. L. Chuang, Phys. Rev. A 62, 052316 (2000)]. However, the precise set of gates in ${\mathcal{C}}_k$ remains unknown, even for a fixed number of qubits $n$, which prevents us from knowing exactly what teleportation is capable of. In this paper we study the structure of ${\mathcal{C}}_k$ in terms of semi-Clifford operations, which send by conjugation at least one maximal Abelian subgroup of the $n$-qubit Pauli group into another one. We show that for $n=1,2$, all the ${\mathcal{C}}_k$ gates are semi-Clifford, which is also true for $\{n=3,k=3\}$. However, this is no longer true for $\{n>2,k>3\}$. To measure the capability of this teleportation primitive, we introduce a quantity called “teleportation depth,” which characterizes how many teleportation steps are necessary, on average, to implement a given gate. We calculate upper bounds for teleportation depth by decomposing gates into both semi-Clifford ${\mathcal{C}}_k$ gates and those ${\mathcal{C}}_k$ gates beyond semi-Clifford operations, and compare their efficiency.

Figure 1

Two-bit teleportation scheme. “$<$” denotes an Einstein-Podolsky-Rosen (EPR) pair, $B$ represents Bell-basis measurement, and $R_{xy}^{\prime }=U{R}_{xy}{U}^{†}$, where $R_{xy}$ is a Pauli operator. The double wires carry classical bits and a single wire carries qubits. Any gate in the ${\mathcal{C}}_k$ hierarchy can be implemented fault tolerantly using this teleporation scheme.

Figure 2

One-bit teleportation scheme. For $Z$ teleportation, $A=I$, $B=H$, $D=Z$, and $E$ is a CNOT gate with the first qubit as its target. For $X$ teleportation, $A=H$, $B=I$, $D=X$, and $E$ is a CNOT gate with the first qubit as its control. All semi-Clifford ${\mathcal{C}}_k$ gates can be implemented fault tolerantly using this scheme.

Figure 3

Semi-Clifford operations versus ${\mathcal{C}}_k$ gates. $A$: all gates; $B$: generalized semi-Clifford gates; $C$: semi-Clifford gates; $D$: ${\mathcal{C}}_k$ gates; $E$: ${\mathcal{C}}_3$ gates. $C$ is strictly contained in $B$ and $E$ is strictly contained in $D$. The two question marks indicate two open problems we have: whether $D$ is a subset of $B$; and whether $E$ is a subset of $C$.

Figure 4

A non-Clifford-diagonalizable ${\mathcal{C}}_k$ gate $W_k$. $V_k=\mathrm{diag}(1,e^{i\pi ∕2^{k-1}})$.

Figure 5

(Color online) The behavior of $T_1(2,k)=4[1-(3∕4{)}^{k-2}]$.

Figure 6

Circuit for $n$-qubit quantum Fourier transform.

Figure 7

Definition of the $n-1$-fold uniformly controlled rotation of a qubit about the axis $\vec{a}$.

Figure 8

The $R_{c3}$ gate—three Toffoli gates in series.

Figure 9

Conjugating $X_1$ by $R_{c3}$.

Figure 10

Conjugating $X_1$ by $R_{c2}$.