Reversible arithmetic coding for quantum data compression

Abstract

We study the problem of compressing a block of symbols (a block quantum state) emitted by a memoryless quantum Bernoulli source. We present a simple-to-implement quantum algorithm for projecting, with high probability, the block quantum state onto the typical subspace spanned by the leading eigenstates 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 propose quantum arithmetic codes to efficiently implement quantum Shannon-Fano codes. Our arithmetic encoder and decoder have a cubic circuit and a cubic computational complexity in the block size. Both the encoder and decoder are quantum-mechanical inverses of each other, and constitute an elegant example of reversible quantum computation.