qubits can be done efficiently by using an array of three XOR’s with the two qubits alternately used as the control and the target.[^8] The shift operation is just a permutation and therefore can be done in constant depth [@moore]. However, we actually need something slightly stronger: a controlled-shift, controlled by functions of the lengths $|l_1\rangle$ and $|l_2\rangle$, which are quantum variables. To do a shift controlled by the register $|s\rangle$, we expand $s$ in binary, and perform a shift by $2^i$ positions conditioned on the appropriate bit of $s$. When $|s\rangle$ is a quantum register in a superposition, this operation performed coherently will entangle the register with the tape, just as in the third difficulty described above. It is no longer a problem here, since we will disentangle the register and the tape during decoding.

Now the encoder keeps the original length tape for [*each*]{} signal as well as the message tape for two messages, i.e., $| l_1 \rangle | l_2 \rangle | h_1 h_2 0 \cdots 0\rangle_{\rm
tape} $. Notice that it is relatively fast to compute the length $l_1 + l_2$ of the two messages from $l_1$ and $l_2$. Therefore, the merging procedure can be performed in 