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

Question

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.

Answer 1

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.