Theorem: Exact recovery if and only if the complete complement is constant

Let $V:C\to R\otimes B$ be an isometry. The following are equivalent:

1. a CPTP decoder on $R$ exactly recovers the code;

2. $\mathcal{C}={\mathcal{T}}_{\sigma }$ for some residual density operator $\sigma$;

3. for a code basis,

   $$\mathcal{C}(E_{ij})={\delta }_{ij}\sigma ;$$

4. for the Bell input,

   $$({\mathrm{id}}_Q\otimes \mathcal{C})(|{\Phi }_d⟩⟨{\Phi }_d|)=\frac{I_Q}{d}\otimes \sigma .$$

When these statements hold, there is an auxiliary Hilbert space $K$, a state ${\sigma }_K$, and an isometry $A:C\otimes K\to R$ such that

The decoder can be chosen as

Proof. The equivalence of (ii) and (iii) follows from linearity. Expanding the normalized Bell state in matrix units proves the equivalence of (iii) and (iv).

Assume (ii). Write the positive spectral decomposition

The sum is finite or countable. Each code basis vector has an expansion

The equality of all complementary matrix units gives

Thus the rule

extends to an isometry. Set ${\sigma }_K={\sum }_{\alpha }{p}_{\alpha }|\alpha ⟩⟨\alpha |$. Tracing $B$ gives (eq:normal-form).

The first term of (eq:exact-decoder) is completely positive. The second is a positive-effect measurement followed by preparation. Their traces add to $\mathrm{Tr}Y$, so the map is CPTP. Substitution into (eq:normal-form) proves exact recovery.

Conversely, suppose (i). Use the normal Stinespring representation of the decoder, with an isometry

The complete decoded isometry is

Since its $C$ output is exactly $|i⟩$ on input $|i⟩$,

for normalized ${\eta }_i$. The decoded off-diagonal matrix unit $E_{ij}$ must also be exact. Tracing $G\otimes B$ therefore gives

Hence all ${\eta }_i$ are one common vector $\eta$. Tracing $C\otimes G$ shows

This proves (ii).