codeword.

A sequential implementation of the encoding algorithm requires only $O \left(N (\log N)^a \right)$ gates.

Proof: This follows immediately from the fact that the encoding is in [**QNC**]{} and uses $O(N)$ qubits: At each time step of a parallel implementation, only $O(N)$ steps are implemented. Since the network has depth $O( (\log N)^a)$, there can be at most $O \left(N (\log N)^a
\right)$ gates in the network.

Communication
=============

We now attempt to use the quantum Huffman coding for communication rather than for the storage of quantum signals. By communication, we assume that Alice receives the signals [*one by one*]{} from a source and is compelled to encode them one-by-one. As we will show below, the number of qubits required is slightly more, namely $N ( \bar{L} + \delta + \lceil \log l_{\rm max} \rceil ) +
\left\lceil \log \left(N l_{\rm max}\right) \right\rceil$. The code that we will construct is not instantaneous, but Alice and Bob can pay a small penalty in stopping the transmission any time. In fact, we have the following:

Sequential encoding and decoding of a quantum Huffman code for communication requires only $O (N^2 (\log N)^a)$ computational steps.

The proof follows in the next three 