Past exam of the laser science and quantum information processing course of the University of Oxford / 2006 / 7 / 2 / Solution

A realized message $x$ has self-information $I(x)=-{\log }_2{p}_x$. The average information per source message is its Shannon entropy,The average reaches ${\log }_{2}3\simeq 1.58496$ bits per message at $p_A=p_B=p_C=1/3$. Individual rare realizations can have larger self-information; this bound concerns the average.

The given strings form a prefix code with lengths ${\ell }_A=1$ and ${\ell }_B={\ell }_C=2$. To attain the entropy bound without redundancy, the resulting long bit stream must carry one bit of information per bit: unbiased bits with no predictable dependence. For an independent source, the dyadic source matched to a complete prefix code hasThese probabilities make the encoded stream equivalent to parsing independent fair bits using the code tree. Its expected codeword length and source entropy agree:Here “optimal” means attaining the Shannon bound. If it means only an optimal prefix code among symbol-by-symbol binary prefix codes, the probabilities are not unique: for three positive-probability symbols, this tree is optimal whenever $p_A$ is a largest probability. Huffman coding need not attain entropy exactly for nondyadic probabilities.

Concatenating the specified source-message encodings givesPack consecutive bits in pairs, rather than allocating a fresh Bell pair to each variable-length source word:Under the mapping in part 1, transmitThe block uses six message-bearing qubit transmissions and six preshared Bell pairs. Source-message boundaries are recovered by parsing the decoded prefix bit stream.