Schumacher’s quantum data compression as a quantum computation

作者：Richard Cleve, David Peter Divincenzo · 发表于：Physical Review A · 年份：1996 · DOI：10.1103/physreva.54.2636 · 被引用次数：51 · 研究领域：Quantum Computing Algorithms and Architecture、Computability, Logic, AI Algorithms、Quantum Information and Cryptography

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(\ensuremath{\surd}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. \textcopyright{} 1996 The American Physical Society.