Schumacher’s quantum data compression as a quantum computation

An explicit algorithm for performing Schumacher’s noiseless compression of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary strings. The algorithm, which adheres to the rules of reversible programming, is expressed in a high-level pseudocode language. It is implemented using O(${\mathit{n}}^3$) two- and three-bit primitive reversible operations, where n is the length of the qubit strings to be compressed. Also, the algorithm makes use of O(n) auxiliary qubits. Space-saving techniques based on those proposed by Bennett are developed which reduce this workspace to O(√n) while maintaining a running time of O(${\mathit{n}}^3$) (albeit with a larger constant). This latter algorithm is of interest because it has a slightly smaller time-space product, which is considered to be the relevant figure of merit for efficiency in some physical models. © 1996 The American Physical Society.