Reversible arithmetic coding for quantum data compression

We study the problem of compressing a block of symbols (a block quantum sta te) emitted by a memoryless quantum Bernoulli source. We present a simple-t o-implement quantum algorithm for projecting, with high probability the blo ck quantum state onto the typical subspace spanned by the leading eigenstat es of its density matrix. We propose a fixed-rate quantum Shannon-Fano code to compress the projected block quantum state using a per-symbol code rate that is slightly higher than the von Neumann entropy limit. Finally, we pr opose quantum arithmetic codes to efficiently implement quantum Shannon-Fan o codes. Our arithmetic encoder and decoder have a cubic circuit and a cubi c computational complexity in the block size. Both the encoder and decoder are quantum-mechanical inverses of each other, and constitute an elegant ex ample of reversible quantum computation.