it becomes of fixed length $\lceil \log l_{\rm max} \rceil$ where $l_{\rm max}$ is the length of the longest Huffman codeword. Therefore, $| \phi_i \rangle $ is mapped into $| 0 \cdots 0 h_i\rangle | l_i \rangle$. Notice that the length of the second tape is $ \lceil \log l_{\rm max} \rceil $ which is generally small compared to $n$. The usage of the second tape is a small price to pay for efficient parallel implementation.

In this Section, we use the model of a quantum gate array for quantum computation. The complexity class [**QNC**]{} is the class of quantum computations that can be performed in polylogarithmic parallel depth [@moore]. We prove the following theorem:

Encoding or decoding of a quantum Huffman code for storage is in the complexity class [**QNC**]{}.

The proof follows in the next two subsections.

Encoding
--------

Without much loss of generality, we suppose that the total number of messages is $N=2^r$ for some positive integer $r$. We propose to encode by divide and conquer. Firstly, we divide the messages into pairs and apply a merging procedure to be discussed in Eq. (\[merging\]) to each pair. The merging effectively reduces the total number of messages to 