Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Gate Teleportation

Teleporting operations, not just states.

Teleportation's corrections are Paulis. Conjugate them by a gate UU and you get a recipe for applying UU by consuming a pre-made resource state. That trick (Gottesman & Chuang, 1999) is how fault-tolerant machines perform their hardest gates, how linear optics becomes universal, and why measurements alone can compute.

What you’ll learn

  • Derive the gate-teleportation identity and the correction rule P↦UPU†P\mapsto UPU^\dagger.
  • Define the Clifford hierarchy and show that gates in C3\mathcal C_3, such as TT and CCZ, teleport with Clifford corrections.
  • Derive magic-state injection for the TT gate and explain its role in fault-tolerant architectures.
  • Recognize one-bit teleportation inside measurement-based computing, linear-optics computing and teleportation-based error correction.
  • State and prove the no-programming theorem, and explain what port-based teleportation buys.

Teleporting through a gate

Run ordinary teleportation, then apply a gate UU to Bob's qubit. Because UU acts on Bob's qubit only, it commutes with everything Alice does, so it may just as well be applied to Bob's half of the Bell pair before the protocol starts. The resource becomes ∣ΦU⟩=(I⊗U)∣Φ+⟩\ket{\Phi_U}=(\id\otimes U)\ket{\Phi^+}, the Choi state of UU, which can be prepared offline, tested, and discarded if faulty.

DerivationGate teleportation (Gottesman & Chuang, 1999)
  1. ∣ψ⟩0⊗(I⊗U)∣Φ+⟩12=12∑x,y∣βxy⟩01⊗UXyZx∣ψ⟩2\ket\psi_0\otimes(\id\otimes U)\ket{\Phi^+}_{12}=\tfrac12\sum_{x,y}\ket{\beta_{xy}}_{01}\otimes UX^{y}Z^{x}\ket\psi_2

    Apply I⊗I⊗U\id\otimes\id\otimes U to the teleportation identity ∣ψ⟩∣Φ+⟩=12∑xy∣βxy⟩XyZx∣ψ⟩\ket\psi\ket{\Phi^+}=\tfrac12\sum_{xy}\ket{\beta_{xy}}X^yZ^x\ket\psi.

  2. UXyZx∣ψ⟩=(UXyZxU†) U∣ψ⟩≡PxyU U∣ψ⟩UX^{y}Z^{x}\ket\psi=\big(UX^{y}Z^{x}U^\dagger\big)\,U\ket\psi\equiv P^{U}_{xy}\,U\ket\psi

    Push UU through the Pauli: the by-product becomes PU=UPU†P^U=UPU^\dagger.

  3. (PxyU)†PxyU U∣ψ⟩=U∣ψ⟩\big(P^{U}_{xy}\big)^{\dagger}P^{U}_{xy}\,U\ket\psi=U\ket\psi

    Bob's correction is (PU)†=UP†U†(P^U)^\dagger=UP^\dagger U^\dagger. If UU is a Clifford gate, PUP^U is again a Pauli, and the correction is as cheap as in ordinary teleportation.

  4. The difficulty of applying UU has moved offline, into preparing ∣ΦU⟩\ket{\Phi_U}. Online, only Bell measurements and corrections are needed. For two-qubit gates the same works with two Bell pairs: Gottesman and Chuang's original application was a teleported CNOT.

Check your understanding

You teleport through (I⊗S)∣Φ+⟩(\id\otimes S)\ket{\Phi^+}, and Alice's outcome means the by-product before conjugation is XX. What must Bob apply to obtain S∣ψ⟩S\ket\psi?

  1. XX
  2. YY
  3. ZZ
  4. S†S^\dagger
Show the answer

B. YY

SXS†=YSXS^\dagger=Y, so Bob holds Y S∣ψ⟩Y\,S\ket\psi. Because SS is Clifford the correction is a Pauli, here YY.

The Clifford hierarchy

DerivationT and CCZ sit in the third level
  1. TZT†=ZTZT^\dagger=Z

    TT is diagonal, so it commutes with ZZ.

  2. TXT†=(0e−iπ/4eiπ/40)=X+Y2=e−iπ/4 SXTXT^\dagger=\begin{pmatrix}0&e^{-i\pi/4}\\ e^{i\pi/4}&0\end{pmatrix}=\tfrac{X+Y}{\sqrt2}=e^{-i\pi/4}\,SX

    Not a Pauli, but a Clifford (SXSX): so T∈C3∖C2T\in\mathcal C_3\setminus\mathcal C_2.

  3. CCZ (X⊗I⊗I) CCZ†=X⊗CZ\mathrm{CCZ}\,(X\otimes\id\otimes\id)\,\mathrm{CCZ}^\dagger=X\otimes\mathrm{CZ}

    On ∣abc⟩\ket{abc} the phases combine to (−1)abc+aˉbc=(−1)bc(-1)^{abc+\bar a bc}=(-1)^{bc}. Conjugating a Pauli XX by CCZ yields a CZ on the other two qubits, which is Clifford; by symmetry the same holds on every qubit, and ZZ's commute with CCZ.

The hierarchy is subtler than its definition suggests. C1\mathcal C_1 and C2\mathcal C_2 are groups, but Ck\mathcal C_k for k≥3k\ge3 is not closed under multiplication. Each level is, however, closed under multiplication by Cliffords on either side. Not every unitary lies in some level: a diagonal gate diag(1,eiϕ)\mathrm{diag}(1,e^{i\phi}) belongs to the hierarchy only when ϕ\phi is a rational multiple of π\pi whose denominator is a power of 2, such as T=diag(1,eiπ/4)T=\mathrm{diag}(1,e^{i\pi/4}) in C3\mathcal C_3 or T\sqrt T in C4\mathcal C_4. The diagonal gates of every level have been fully characterized (Cui, Gottesman & Krishna 2017).

Magic-state injection

For a diagonal gate like TT, a full Bell pair is overkill. Half of the protocol, one-bit teleportation (Zhou, Leung & Chuang 2000), suffices, consuming one copy of the magic state ∣A⟩=T∣+⟩=(∣0⟩+eiπ/4∣1⟩)/2\ket A=T\ket+=(\ket0+e^{i\pi/4}\ket1)/\sqrt2.

DerivationThe T-gate gadget
  1. ∣ψ⟩∣A⟩=12(α∣0⟩+β∣1⟩)(∣0⟩+ω∣1⟩),ω=eiπ/4\ket\psi\ket{A}=\tfrac{1}{\sqrt2}\big(\alpha\ket0+\beta\ket1\big)\big(\ket0+\omega\ket1\big),\qquad\omega=e^{i\pi/4}

    Data qubit first, magic state second.

  2. → CNOTdata→A  12[(α∣0⟩+ωβ∣1⟩)∣0⟩+(ωα∣0⟩+β∣1⟩)∣1⟩]\xrightarrow{\ \mathrm{CNOT}_{\text{data}\to A}\ }\ \tfrac{1}{\sqrt2}\Big[\big(\alpha\ket0+\omega\beta\ket1\big)\ket0+\big(\omega\alpha\ket0+\beta\ket1\big)\ket1\Big]

    The CNOT flips the magic qubit in the ∣1⟩\ket1 branch of the data, swapping its two amplitudes there.

  3. m=0:  T∣ψ⟩,m=1:  ω T†∣ψ⟩ → S  T∣ψ⟩m=0:\ \ T\ket\psi,\qquad m=1:\ \ \omega\,T^\dagger\ket\psi\ \xrightarrow{\ S\ }\ T\ket\psi

    Measure the magic qubit in ZZ. For m=1m=1, ωα∣0⟩+β∣1⟩=ω(α∣0⟩+ωˉβ∣1⟩)=ωT†∣ψ⟩\omega\alpha\ket0+\beta\ket1=\omega(\alpha\ket0+\bar\omega\beta\ket1)=\omega T^\dagger\ket\psi, and ST†=TST^\dagger=T. Each outcome has probability ½, and the only correction is the Clifford SS.

Why this matters: by the Eastin–Knill theorem (2009), no quantum error-correcting code that detects arbitrary single-qubit errors has a universal set of transversal logical gates. Leading fault-tolerant architectures, such as the surface code, therefore implement Clifford operations within the code and import non-Clifford gates by injecting distilled magic states: gate teleportation at the logical level. As of the mid-2020s, producing magic states is among the dominant costs in resource estimates for useful algorithms.

Predict before you look

A noisy magic state with error ϵ=10−2\epsilon=10^{-2} goes through one round of 15-to-1 distillation, ϵout≈35ϵ3\epsilon_{\mathrm{out}}\approx35\epsilon^3. What is ϵout\epsilon_{\mathrm{out}}, in units of 10−510^{-5}?

Show the answer

3.5 ×10⁻⁵

35×(10−2)3=3.5×10−535\times(10^{-2})^3=3.5\times10^{-5}. A second round gives 35 (3.5×10−5)3≈1.5×10−1235\,(3.5\times10^{-5})^3\approx1.5\times10^{-12}, at a cost of 152=22515^2=225 noisy inputs per output. The cubic suppression is what makes distillation viable; the multiplicative overhead is what makes it expensive.

Teleportation as computation

One-bit teleportation is also the elementary step of measurement-based quantum computing (Raussendorf & Briegel 2001). Entangle the input qubit 1 with an ancilla qubit 2 in ∣+⟩\ket+, then measure qubit 1 in a rotated basis:

DerivationThe elementary MBQC step
  1. ∣ψ⟩1∣+⟩2 → CZ  α∣0⟩∣+⟩+β∣1⟩∣−⟩\ket\psi_1\ket{+}_2\ \xrightarrow{\ \mathrm{CZ}\ }\ \alpha\ket0\ket{+}+\beta\ket1\ket{-}

    The CZ is one bond of a cluster state.

  2. measure qubit 1 in {∣0⟩±e−iθ∣1⟩2}:outcome m ⇒ XmHP(θ)∣ψ⟩ on qubit 2\text{measure qubit 1 in }\Big\{\tfrac{\ket0\pm e^{-i\theta}\ket1}{\sqrt2}\Big\}:\quad\text{outcome }m\ \Rightarrow\ X^{m}HP(\theta)\ket\psi\ \text{on qubit 2}

    The bra (⟨0∣±eiθ⟨1∣)/2(\bra0\pm e^{i\theta}\bra1)/\sqrt2 leaves 12(α∣+⟩+ (±eiθ)β∣−⟩)=12H(α∣0⟩±eiθβ∣1⟩)\tfrac{1}{\sqrt2}\big(\alpha\ket++\,(\pm e^{i\theta})\beta\ket-\big)=\tfrac{1}{\sqrt2}H\big(\alpha\ket0\pm e^{i\theta}\beta\ket1\big), where P(θ)=diag(1,eiθ)P(\theta)=\mathrm{diag}(1,e^{i\theta}). Using HZ=XHHZ=XH, outcome mm gives XmHP(θ)∣ψ⟩X^mHP(\theta)\ket\psi.

  3. P(θ′) X=eiθ′ X P(−θ′)P(\theta')\,X=e^{i\theta'}\,X\,P(-\theta')

    The by-product XmX^m can be pushed through later steps if the next angle is adapted to (−1)mθ′(-1)^m\theta'. Chaining such steps teleports the logical qubit along the cluster while applying HP(θ)HP(\theta) rotations, which generate all single-qubit unitaries; the two-dimensional cluster supplies entangling gates. Single-qubit measurements on a cluster state are therefore universal.

Linear optics. Photons barely interact, so a deterministic CZ between photonic qubits is impossible with linear optics alone. Knill, Laflamme & Milburn (2001) showed that teleporting the gate, through entangled ancilla photons prepared offline and with heralded measurements and feed-forward, yields scalable quantum computing from single photons, linear optics and photodetection; their teleported gates succeed with probability n/(n+1)n/(n+1) using entangled ancillas of size nn, and error correction handles the remaining failures. Modern photonic architectures build on the same principle with small entangled resource states and "fusion" measurements.

SettingWhat is teleportedResource state
Fault-tolerant QCTT, CCZ and other non-Clifford gates (Bravyi–Kitaev 2005)Distilled magic states
Linear optics (KLM 2001)CZ between photonsEntangled ancilla photons
MBQC (Raussendorf–Briegel 2001)Every gate, via one-bit teleportation chainsCluster or graph states
Teleportation-based error correction (Knill 2005)Encoded data, corrected while it is teleportedEncoded Bell pairs
Distributed QCA CNOT between distant modules: 1 ebit + 2 cbits suffice, and are optimal (Eisert et al. 2000)Bell pairs between modules

Programs as states: limits and frontier

Gate teleportation turns a state into a program: ∣ΦU⟩\ket{\Phi_U} stores UU. Could one fixed device run any unitary, given its program state? Teleportation gives a probabilistic answer: with probability 1/41/4 per qubit Alice's outcome is (0,0)(0,0), no correction is needed, and Bob holds U∣ψ⟩U\ket\psi whatever UU was. A deterministic version is impossible.

DerivationProof (the no-cloning argument again)
  1. ⟨PU∣PV⟩=⟨d∣U†V∣d⟩ ⟨PU′∣PV′⟩for all ∣d⟩\braket{P_U|P_V}=\bra dU^\dagger V\ket d\,\braket{P'_U|P'_V}\qquad\text{for all }\ket d

    Take the inner product of the two defining equations and use G†G=IG^\dagger G=\id. (One first checks that the leftover ∣PU′⟩\ket{P'_U} cannot depend on ∣d⟩\ket d.)

  2. ⟨PU∣PV⟩≠0 ⟹ ⟨d∣U†V∣d⟩ is the same for every ∣d⟩ ⟹ U†V∝I\braket{P_U|P_V}\neq0\ \Longrightarrow\ \bra dU^\dagger V\ket d\ \text{is the same for every }\ket d\ \Longrightarrow\ U^\dagger V\propto\id

    A matrix whose expectation value is the same in every state is a multiple of the identity. ■\blacksquare

Port-based teleportation (Ishizaka & Hiroshima 2008) trades entanglement for simplicity. Alice and Bob share NN maximally entangled pairs, the "ports". Alice measures the input together with her NN halves and announces a port number ii; Bob keeps port ii and discards the rest, with no correction. The fidelity tends to 1 as N→∞N\to\infty. Because no correction is needed, Bob can apply UU to every port before hearing from Alice, which yields an approximate universal programmable processor. Port-based teleportation is also the key tool for instantaneous non-local computation and for attacks on position-based cryptography (Beigi & König 2011).

Key takeaways

  • Teleporting through (I⊗U)∣Φ+⟩(\id\otimes U)\ket{\Phi^+} applies UU with by-products UPU†UPU^\dagger; for Clifford UU they stay Pauli.
  • Gates in Ck\mathcal C_k teleport with corrections in Ck−1\mathcal C_{k-1}: TT and CCZ need only Clifford fix-ups.
  • Magic-state injection (CNOT, ZZ measurement, conditional SS) applies TT using ∣A⟩=T∣+⟩\ket A=T\ket+; with Clifford operations this is universal (Bravyi–Kitaev), sidestepping Eastin–Knill.
  • Measurement-based computing, KLM linear optics, teleportation-based error correction and distributed gates are all gate teleportation in disguise.
  • Programs as states are limited by the no-programming theorem; port-based teleportation gives approximate universality at a large entanglement cost.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

You teleport through (I⊗T)∣Φ+⟩(\id\otimes T)\ket{\Phi^+} and the by-product before conjugation is XX, so Bob holds (up to phase) SX T∣ψ⟩SX\,T\ket\psi. Which correction gives T∣ψ⟩T\ket\psi?

  1. XX
  2. XS†XS^\dagger (first S†S^\dagger, then XX)
  3. SS
  4. T†T^\dagger
Show the answer

B. XS†XS^\dagger (first S†S^\dagger, then XX)

TXT†=e−iπ/4SXTXT^\dagger=e^{-i\pi/4}SX, so Bob must undo SXSX: (SX)−1=XS†(SX)^{-1}=XS^\dagger, a Clifford. That is why C3\mathcal C_3 gates teleport with Clifford corrections.

Question 2

Which statement about the Clifford hierarchy is true?

  1. Every level Ck\mathcal C_k is a group
  2. TT and CCZ lie in C3\mathcal C_3, so they can be teleported with Clifford corrections
  3. Every unitary lies in some finite level Ck\mathcal C_k
  4. Conjugating a Pauli by any C3\mathcal C_3 gate gives a Pauli
Show the answer

B. TT and CCZ lie in C3\mathcal C_3, so they can be teleported with Clifford corrections

TXT†∝SXTXT^\dagger\propto SX and CCZ X1 CCZ†=X1CZ23\mathrm{CCZ}\,X_1\,\mathrm{CCZ}^\dagger=X_1\mathrm{CZ}_{23} are Clifford, so both gates are in C3\mathcal C_3, and teleporting them needs only Clifford corrections.

Question 3

In the TT-gate injection gadget, with what probability does the measurement give m=1m=1 (so that the SS correction is needed)?

  1. ∣β∣2\abs\beta^2
  2. ∣α∣2\abs\alpha^2
  3. It depends on the relative phase of α\alpha and β\beta
  4. 1/21/2, independent of ∣ψ⟩\ket\psi
Show the answer

D. 1/21/2, independent of ∣ψ⟩\ket\psi

The m=1m=1 branch is 12(ωα∣0⟩+β∣1⟩)\tfrac{1}{\sqrt2}(\omega\alpha\ket0+\beta\ket1), whose squared norm is 12(∣α∣2+∣β∣2)=12\tfrac12(\abs\alpha^2+\abs\beta^2)=\tfrac12. The outcome reveals nothing about ∣ψ⟩\ket\psi, as it must for a gadget that preserves superpositions.

Question 4

Why can't a fixed, finite-dimensional device apply an arbitrary unitary UU exactly and deterministically, given a program state that encodes UU?

  1. Because the data qubit would have to be cloned
  2. Because program states decohere faster than data states
  3. Because inequivalent unitaries need mutually orthogonal program states, and there are infinitely many of them
  4. Because teleportation corrections for non-Clifford gates are themselves non-Clifford
Show the answer

C. Because inequivalent unitaries need mutually orthogonal program states, and there are infinitely many of them

The inner-product argument gives ⟨PU∣PV⟩=⟨d∣U†V∣d⟩⟨PU′∣PV′⟩\braket{P_U|P_V}=\bra dU^\dagger V\ket d\braket{P'_U|P'_V} for all ∣d⟩\ket d, which forces ⟨PU∣PV⟩=0\braket{P_U|P_V}=0 unless U∝VU\propto V. A continuum of unitaries cannot fit into finitely many orthogonal states.

Further reading

  • D. Gottesman & I. L. Chuang, "Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations", Nature 402, 390 (1999).
  • X. Zhou, D. W. Leung & I. L. Chuang, "Methodology for quantum logic gate construction", Physical Review A 62, 052316 (2000).
  • S. Bravyi & A. Kitaev, "Universal quantum computation with ideal Clifford gates and noisy ancillas", Physical Review A 71, 022316 (2005).
  • E. Knill, R. Laflamme & G. J. Milburn, "A scheme for efficient quantum computation with linear optics", Nature 409, 46 (2001).
  • R. Raussendorf & H. J. Briegel, "A one-way quantum computer", Physical Review Letters 86, 5188 (2001).