Schumacher's Quantum Data Compression as a Quantum Computation

        An explicit algorithm for performing Schumacher's noiseless compression of quantum bits is given. The 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(n[sup3]) 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; however, space-saving techniques based on those proposed by Bennett are developed which reduce this workspace to O(divided by n) while increasing the running time by less than a factor or two.

By: Richard Cleve (Univ. of Calgary, Canada) and David P. DiVincenzo

Published in: RC20413 in 1996

This Research Report is not available electronically. Please request a copy from the contact listed below. IBM employees should contact ITIRC for a copy.

Questions about this service can be mailed to .