Theorem: Exact one-way classical communication cost

In the stated one-way implementation model, exact recovery requires at least four distinguishable messages, hence at least two fixed-length classical bits. The distributed programme above attains the bound.

Proof. By Theorem thm:B3, any exact code recovery must implement $\mathcal{D}$ on the entire three-qubit input space. A minimum Kraus family is

The four ${\beta }_j$ are an orthonormal basis, and the four $C_j{R}_3$ are nonproportional unitaries.

A one-way protocol has a POVM effect $E_m$ for each message and a Bob channel with Kraus operators $B_{m\ell }$. Diagonalize $E_m={\sum }_r|{\eta }_{mr}⟩⟨{\eta }_{mr}|$. The full channel has product-form Kraus maps

Every such Kraus map lies in the span of the four $K_j$: the Choi operator is a positive sum of its Kraus-vector projectors, so no vector can have a component outside its support.

Expand $⟨\eta |={\sum }_j{a}_j⟨{\beta }_j|$. Membership of a nonzero product map $B⟨\eta |$ in that span requires

for every $j$. If two coefficients $a_j$ were nonzero, two distinct correction unitaries would be proportional, which they are not. Thus each nonzero $\eta$ is supported on one basis vector ${\beta }_j$.

For one fixed message, the same nonzero Bob Kraus operator cannot serve two distinct basis vectors. Hence each nonzero $E_m$ is supported on one ${\beta }_j$. POVM completeness requires all four basis directions. There must therefore be at least four messages. The two-bit construction is complete and correct by Theorem thm:streamupper.