# Applying $R^{'\dagger}_{xz}$ in gate teleportation

In figure 4 of the paper Quantum Teleportation is a Universal Computational Primitive, the authors show a circuit for applying a unitary $$U$$ fault-tolerantly via teleportation. I'll paste the figure below for easier reference:

However, our teleportation construction provides a straightforward way to produce any gate in $$C_3$$, as shown in Fig. 4. For $$U \in C_3$$, first construct the state $$|\Psi^n_U\rangle = (I \otimes U)|\Psi^n\rangle.$$ Next, take the input state $$|\psi\rangle$$ and do Bell basis measurements on this and the $$n$$ upper qubits of $$|\Psi^n_U\rangle$$, leaving us with $$n$$ qubits in the state $$|\psi_{out}\rangle=UR_{xz}|\psi\rangle = R^{'}_{xz}U|\psi\rangle.$$ where $$R_{xz}$$ is an operator in $$C_1$$ which depends on the (random) Bell basis measurement outcomes $$xz$$, and $$R^{'}_{xz}$$ is an operator in $$C_2$$: the image of $$R_{xz}$$ under conjugation by $$U$$. Since $$R^{'}_{xz}$$ is in the Clifford group, it can be performed fault-tolerantly. As long as $$|\Psi_U^n\rangle$$ can be prepared fault-tolerantly, this construction allows $$U$$ to be performed fault-tolerantly.

$$C_1$$ is the Pauli group, $$C_2$$ the Clifford group, and $$C_3$$ is defined as $$C_3 \equiv \{U|UC_1U^\dagger \subseteq C_2\}$$.

I was trying to implement the circuit in Qiskit and couldn't make it work. I think the problem I'm having is about $$R_{xz}$$ and $$R^{'}_{xz}$$. First of all, they are not giving a concrete definition of these gates, so I just assumed they were the same as the gates applied on the normal state teleportation circuit. That is, an $$X$$ gate controlled on the measurement result of the top qubit followed by a $$Z$$ gate controlled on the result of measuring the second qubit. In this case, $$R_{xz}=Z^{z}X^{x}$$ which in turn means that $$R^{'}_{xz}=UZ^{z}X^{x}U^{-1}$$.

However, this would defeat the purpose of the teleportation protocol since it'd involve applying $$U$$ and $$U^{-1}$$ which is exactly what we are looking a workaround for. (Note that applying $$U$$ is allowed before the dotted line in the circuit since it is part of state preparation which can be performed fault-tolerantly as described on the appendix of the linked paper.) Therefore, I think I might have two things wrong: 1) the definition of $$R_{xz}$$ and 2) how is the gate $$R^{'\dagger}_{xz}$$ actually applied and controlled.

It'd be great if anyone can point me in the right direction regarding these two concerns. Any links to more recent literature regarding these protocols or a variant of it are also very welcome. Or if you already have a working implementation of this protocl on Qiskit, I'd be happy to look at it.

1. The recovery operator $$R_{xz}$$ is the same one as you would apply when doing quantum state teleporation

2. $$R'^\dagger_{xz}$$ will be some combination of Clifford gates and Pauli gates, the latter classically conditioned on the Bell basis measurement outcome.

I think that a single qubit ($$n=1$$) will be sufficient to demonstrate whats going on here. Let the registers be labelled from top to bottom as $$A$$, $$B$$, and $$C$$ and recall that you can rewrite the initial state (before either $$U$$ or Bell measurement are performed) as$$^1$$:

$$\tag{1} |\alpha\rangle_A\otimes |\Phi_0\rangle_{BC} = \frac{1}{2}\sum_{\ell=0}^3 |\Phi_\ell\rangle_{AB} \otimes \sigma_\ell|\alpha\rangle_C$$

where $$\sigma_\ell$$ is a single-qubit Pauli and I am using a Bell basis: \begin{align} \tag{2a-d} |\Phi_0\rangle &= \frac{1}{\sqrt{2}} (|00\rangle + |11\rangle)\\ |\Phi_1\rangle &= (\sigma_1\otimes I)|\Phi_0\rangle\\ |\Phi_2\rangle &= i(\sigma_1 \otimes \sigma_3 )|\Phi_0\rangle\\ |\Phi_3\rangle &= (I \otimes \sigma_3 )|\Phi_0\rangle\\ \end{align}

Now $$C$$ applies $$U$$ to their system and $$AB$$ performs the Bell basis measurement. This gives $$AB$$ knowledge of $$\ell\equiv xz$$ (two bits!) which they share, leaving the system in the state $$\tag{3} |\psi'\rangle_{ABC} = |\Phi_\ell\rangle_{AB} \otimes U\sigma_\ell|\alpha\rangle_C$$

In this notation we have $$\sigma_\ell \equiv R_{xz}$$ and if this were vanilla state teleportation we would apply $$R_{xz}$$ to recover $$|\alpha\rangle$$ in system $$C$$. But To recover $$U|\alpha\rangle$$ we need to apply the specific recovery operation \begin{align}\tag{4a-c} |\psi'\rangle_{ABC} &\rightarrow I\otimes I \otimes (U\sigma_\ell U^\dagger)^\dagger |\psi'\rangle_{ABC} \\&=|\Phi_\ell\rangle_{AB} \otimes U\sigma_\ell U^\dagger U\sigma_\ell|\alpha\rangle_C \\&=|\Phi_\ell\rangle_{AB} \otimes U|\alpha\rangle_C \end{align}

which recovers the desired final state and demonstrates that the correct recovery operation was $$R_{xz}' \equiv U\sigma_\ell U^\dagger$$ (its not clear to me why the adjoint is required but I've left it for consistency; it might have something to do with global phases that appear in the Pauli and Clifford groups that are irrelevant in practice).

$$U$$ is not just any gate, it must belong to the set of gates for which $$U \sigma_\ell U^\dagger$$ is a Clifford gate. So by construction you are allowed to apply the recovery operation fault-tolerantly and you don't actually apply $$U$$ at any point after the dashed line in Figure 4.

### Example

For $$U=T$$ the authors provided the recovery operations $$T\sigma_\ell T^\dagger$$ as \begin{align}\tag{5a-d} R'_0 &= I\\ R'_1 &= S\sigma_1\\ R'_2 &= S\sigma_2 \\ R'_3 &= \sigma_3 \end{align}

up to a global phase. So imagine $$AB$$ measures $$\ell = 1$$ ($$xz=01$$ in binary), then starting from Equation (3) we would proceed by applying

\begin{align}\tag{6} |\Phi_1\rangle_{AB} \otimes T \sigma_1|\alpha\rangle_C \rightarrow |\Phi_1\rangle_{AB} \otimes S\sigma_1 T \sigma_1|\alpha\rangle_C \end{align}

And we can then compute \begin{align} \tag{7a-d} S\sigma_1 T \sigma_1 &\dot{=} \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi / 4}\end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \\ &= \begin{pmatrix} 0 & 1 \\ i & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ e^{i\pi / 4} & 0 \end{pmatrix} \\ &= \begin{pmatrix} e^{i\pi/4} & 0 \\ 0 & i \end{pmatrix} \\ &\dot{=} e^{-i\pi/4} T \end{align}

where I've intentionally applied $$R_{xz}'$$ instead of $$R_{xz}'^\dagger$$ to demonstrate that it still works up to global phase.

$$^1$$ To derive this identity, start by rewriting the computational basis states like this: \begin{align} |00\rangle &= \frac{1}{2} \left[(|00\rangle + |11\rangle) + (|00\rangle - |11\rangle)\right] \end{align} and so \begin{align} |00\rangle &= \frac{1}{\sqrt{2}} \left(|\Phi_0\rangle + |\Phi_3\rangle\right)\\ |01\rangle &= \frac{1}{\sqrt{2}} \left(|\Phi_1\rangle +i|\Phi_2\rangle\right)\\ |10\rangle &= \frac{1}{\sqrt{2}} \left(|\Phi_1\rangle -i |\Phi_2\rangle\right)\\ |11\rangle &= \frac{1}{\sqrt{2}} \left(|\Phi_0\rangle - |\Phi_3\rangle\right) \end{align}

Then for a general single-qubit state $$|\alpha\rangle = a|0\rangle + b|1\rangle$$ we have \begin{align} |\alpha\rangle |\Phi_0\rangle &= \frac{1}{\sqrt{2}}(a|0\rangle + b|1\rangle)(|00\rangle + |11\rangle)\\ &= \frac{1}{\sqrt{2}} (a|\color{red}{00}0\rangle + a|\color{red}{01}1\rangle + b|\color{red}{10}0\rangle + b|\color{red}{11}1\rangle)\\ &= \frac{1}{2} \left(\color{red}{\left(|\Phi_0\rangle + |\Phi_3\rangle\right)} a|0\rangle + \color{red}{\left(|\Phi_1\rangle +i|\Phi_2\rangle\right)}a|1\rangle + \color{red}{\left(|\Phi_1\rangle -i |\Phi_2\rangle\right)}b|0\rangle + \color{red}{\left(|\Phi_0\rangle - |\Phi_3\rangle\right)}b|1\rangle \right)\\ &= \frac{1}{2} \left(|\Phi_0\rangle (a|0\rangle + b|1\rangle) + |\Phi_1\rangle (a|1\rangle + b|0\rangle) + |\Phi_2\rangle (ia|1\rangle - ib|0\rangle) + |\Phi_3\rangle (a|0\rangle - b|1\rangle) \right)\\ &= \frac{1}{2} \left(|\Phi_0\rangle \sigma_0 |\alpha\rangle + |\Phi_1\rangle \sigma_1 |\alpha\rangle + |\Phi_2\rangle \sigma_2 |\alpha\rangle + |\Phi_3\rangle \sigma_3 |\alpha\rangle \right)\\ &=\frac{1}{2}\sum_{\ell=0}^3 |\Phi_\ell\rangle \otimes \sigma_\ell|\alpha\rangle \end{align}

which recovers the desired expression.

• I think there's a typo on equation (6); before the right arrow you put $\sigma_2$ but you said $\ell=1$ so I think it should be $\sigma_1$ as in the right side of the arrow. Is this right? Sep 10 at 13:43
• And one question about equation (1). I tried to explicitly write out the sum to see if it equals the LHS but it doesn't seem to do. Could you point me to some reference about this derivation or write it out explicitly? Sep 10 at 14:18
• Sorry, I made a mistake with the definition of the Bell basis (the subscripts didn't correspond to the desired pauli recovery operation). Should be better now. Sep 10 at 16:32
• Yes, this was actually the result I got to so it makes a lot of sense. Thank you very much! Sep 10 at 16:58