0  \cdots 0 \rangle_{\rm
tape}  \otimes \nonumber \\
& & | l_1+\cdots+l_{N}  \rangle_{\rm total~length} \;.\end{aligned}$$ We have included an ancillary space storing the total length of the codewords generated so far.[^10] This space requires $\log(N l_{\rm max})$ qubits.

Even though the encoding of signals themselves are done one-by-one, the shifting operation can be sped up by parallel computation. Indeed, as before, the required controlled-shifting operation can be performed in $O(\log N)$ depth. As before, if a sequential implementation is used instead, the complete encoding of one signal still requires only $O \left( N (\log N)^a \right)$ gates.

Now the encoding of the $N$ signals in quantum communication is done sequentially, implying $O(N)$ applications of the shifting operation. Therefore, with a parallel implementation of the shifting operation, the whole process has depth $O\left( N (\log N)^a \right)$. With a sequential implementation, it takes $O\left( N^2 (\log N)^a \right)$ steps.

Transmission
------------

Notice that the message is written on the message tape from left to right. Moreover, starting from left to right, the state of each qubit once written remains unchanged throughout the encoding process. This decoupling effect suggests that rather than waiting for the completion of the whole encoding process, the 