Schumacher's quantum data compression as a quantum computation

Abstract

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(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; however, space-saving techniques based on those proposed by Bennett are developed which reduce this workspace to $O(\sqrt{n})$ while increasing the running time by less than a factor of two.

37 pages, no figures

References in corpus (6)

• Elementary gates for quantum computation
• Quantum Computers and Dissipation
• Quantum Networks for Elementary Arithmetic Operations
• A Simple Quantum Computer
• Universality in Quantum Computation
• Efficient Networks for Quantum Factoring

Cited by in corpus (26)

• Quantum Computing
• The Ion Trap Quantum Information Processor
• The mother of all protocols: Restructuring quantum information's family tree
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum Gates and Circuits
• Parallel Quantum Computing in a Single Ensemble Quantum Computer
• Applications of coherent classical communication and the Schur transform to quantum information theory
• The Asymptotic Cooling of Heat-Bath Algorithmic Cooling
• Scalable NMR Quantum Computation
• NMR implementation of a building block for scalable quantum computation
• Models of quantum computation and quantum programming languages
• Quantum Mixed State Compiling
• Single Shot i-Toffoli Gate in Dispersively Coupled Superconducting Qubits
• Quantum Computation and Spin Physics
• The Quantum Schur Transform: I. Efficient Qudit Circuits
• Asymptotic Redundancies for Universal Quantum Coding
• Power of one non-clean qubit
• Device-independent randomness generation with sublinear shared quantum resources
• Fundamental limitations for measurements in quantum many-body systems
• Generic Quantum Block Compression
• Energy Requirements for Quantum Data Compression and 1-1 Coding
• Extending scientific computing system with structural quantum programming capabilities
• Numerical Analysis of Boosting Scheme for Scalable NMR Quantum Computation
• Quantum black holes as solvents
• Lipschitz continuity of quantum-classical conditional entropies with respect to angular distance and related properties
• Compression of quantum shallow-circuit states