SCHUMACHERS QUANTUM DATA-COMPRESSION AS A QUANTUM COMPUTATION

An explicit algorithm for performing Schumacher's noiseless compressio n of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary strings. The algor ithm, which adheres to the rules of reversible programming, is express ed in a high-level pseudocode language. It is implemented using O(n(3) ) two- and three-bit primitive reversible operations, where n is the l ength of the qubit strings to be compressed. Also, the algorithm makes use of O(n) auxiliary quibits. Space-saving techniques based on those proposed by Bennett are developed which reduce this workspace to O(ro ot n) while maintaining a running time of O(n(3)) (albeit with a large r constant). This latter algorithm is of interest because it has a sli ghtly smaller time-space product, which is considered to be the releva nt figure of merit for efficiency in some physical models.