Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9603009 · Physical Review A

Schumacher’s quantum data compression as a quantum computation

Richard Cleve, David Peter Divincenzo

Published Oct 1, 1996• 52 citations
arXivHTMLPDF

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(${\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.

DOI
10.1103/physreva.54.2636

Related papers

Quantum Entanglement-Based Data Compression via Phase Space Mapping

Jincheng Zhang

This paper proposes a novel data compression technique leveraging the unique properties of quantum entanglement. The core idea involves encoding data into the correlated phase space of entangled qubits, achieving lossless compression. The algorithm utilizes controlled phase manipulation for both encoding and decoding, capitalizing on the inherent correlations between entangled particles. Unlike traditional entropy-based compression methods, this approach directly exploits quantum mechanical phenomena. We demonstrate a theoretical framework and outline a compression algorithm with the potential for significant improvements in compression ratios. The key mathematical representation of the compression process is defined as follows: Let $x = (x_1, x_2, ..., x_N)$ be the original data sequence, where each $x_i$ is a binary value (0 or 1). The compression algorithm maps this sequence to an entangled state $(|\psi_1\rangle, |\psi_2\rangle, ..., |\psi_N\rangle)$, where $|\psi_i\rangle$ represents the state of the *i*-th qubit in the entangled pair. The compression ratio *R* is defined as: $R = \frac{N}{N_{encoded}}$ where *N* is the length of the original data sequence and *Nencoded* is the number of qubits used to represent the data. The encoding process is described by: $|\psi_i\rangle = \alpha_i |0\rangle + \beta_i |1\rangle$ where $\alpha_i$ and $\beta_i$ are complex amplitudes determined by the data bit $x_i$. The decoding process reverses this operation, reconstructing the original data from the measured state of the qubits. The fidelity of the reconstruction is crucial, and the algorithm incorporates techniques to minimize errors due to measurement noise. The overall compression algorithm can be summarized as follows:

•Sep 6, 2026•0 citations

Data Compression for Quantum Code

Kwok Yip Szeto

The general scheme of data compression using the quantum noiseless coding theorem of Schumacher is dicussed for general quantum sources. When the Hilbert space of the quantum source is decomposable into orthogonal subspaces, one can first perform classical data compression before performing the quantum data compression for individual subspaces. For minimizing the resource in quantum coding, a general parameterization of the dimensions in the Jozsa-Schumacher quantum data compression scheme is presented.

arXiv:quant-ph/9607010•Jul 12, 1996•2 citations

Information loss and run time from practical application of quantum data compression

Saahil Patel, Benjamin Collis, William Duong +4 more

Abstract We examine information loss, resource costs, and run time from practical application of quantum data compression. Compressing quantum data to fewer qubits enables efficient use of resources, as well as applications for quantum communication and denoising. In this context, we provide a description of the quantum and classical components of the hybrid quantum autoencoder algorithm, implemented using IBMs Qiskit language. Utilizing our own data sets, we encode bitmap images as quantum superposition states, which correspond to linearly independent vectors with density matrices of discrete values. We successfully compress this data with near-lossless compression using simulation, and then run our algorithm on an IBMQ quantum chip. We describe conditions and run times for training and compressing our data on quantum devices, and relate trainability to specific characteristics and performance metrics of our parametric quantum circuits.

arXiv:2203.11332•Physica Scripta•Mar 15, 2023•8 citations

Entanglement-Assisted Quantum Data Compression

Zahra Baghali Khanian, Andreas Winter

Ask how the quantum compression of ensembles of pure states is affected by the availability of entanglement, and in settings where the encoder has access to side information. We find the optimal asymptotic quantum rate and the optimal tradeoff (rate region) of quantum and entanglement rates. It turns out that the amount by which the quantum rate beats the Schumacher limit, the entropy of the source, is precisely half the entropy of classical information that can be extracted from the source and side information states without disturbing them at all ("reversible extraction of classical information").In the special case that the encoder has no side information, or that she has access to the identity of the states, this problem reduces to the known settings of blind and visible Schumacher compression, respectively, albeit here additionally with entanglement assistance. We comment on connections to previously studied and further rate tradeoffs when also classical information is considered.

arXiv:1901.06346•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•17 citations

Quantum Data Compression of a Qubit Ensemble

Lee A. Rozema, Dylan H. Mahler, Alex Hayat +2 more

Data compression is a ubiquitous aspect of modern information technology, and the advent of quantum information raises the question of what types of compression are feasible for quantum data, where it is especially relevant given the extreme difficulty involved in creating reliable quantum memories. We present a protocol in which an ensemble of quantum bits (qubits) can in principle be perfectly compressed into exponentially fewer qubits. We then experimentally implement our algorithm, compressing three photonic qubits into two. This protocol sheds light on the subtle differences between quantum and classical information. Furthermore, since data compression stores all of the available information about the quantum state in fewer physical qubits, it could allow for a vast reduction in the amount of quantum memory required to store a quantum ensemble, making even today's limited quantum memories far more powerful than previously recognized.

arXiv:1410.3941•Physical Review Letters•Oct 17, 2014•57 citations

Lossless quantum prefix compression for communication channels that are always open

Markus P. Müller, Caroline Rogers, Rajagopal Nagarajan

We describe a method for lossless quantum compression if the output of the information source is not known. We compute the best possible compression rate, minimizing the expected base length of the output quantum bit string (the base length of a quantum string is the maximal length in the superposition). This complements work by Schumacher and Westmoreland who calculated the corresponding rate for minimizing the output's average length. Our compressed code words are prefix-free indeterminate-length quantum bit strings which can be concatenated in the case of multiple sources. Therefore, we generalize the known theory of prefix-free quantum codes to the case where strings have indeterminate length. Moreover, we describe a communication model which allows the lossless transmission of the compressed code words. The benefit of compression is then the reduction of transmission errors in the presence of noise.

arXiv:0808.2003•Physical Review A•Jan 6, 2009•7 citations
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(n3{\mathit{n}}^{3}n3) 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(n3{\mathit{n}}^{3}n3) (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.
This paper proposes a novel data compression technique leveraging the unique properties of quantum entanglement. The core idea involves encoding data into the correlated phase space of entangled qubits, achieving lossless compression. The algorithm utilizes controlled phase manipulation for both encoding and decoding, capitalizing on the inherent correlations between entangled particles. Unlike traditional entropy-based compression methods, this approach directly exploits quantum mechanical phenomena. We demonstrate a theoretical framework and outline a compression algorithm with the potential for significant improvements in compression ratios. The key mathematical representation of the compression process is defined as follows: Let x=(x1,x2,...,xN)x = (x_1, x_2, ..., x_N)x=(x1​,x2​,...,xN​) be the original data sequence, where each xix_ixi​ is a binary value (0 or 1). The compression algorithm maps this sequence to an entangled state (∣ψ1⟩,∣ψ2⟩,...,∣ψN⟩)(|\psi_1\rangle, |\psi_2\rangle, ..., |\psi_N\rangle)(∣ψ1​⟩,∣ψ2​⟩,...,∣ψN​⟩), where ∣ψi⟩|\psi_i\rangle∣ψi​⟩ represents the state of the *i*-th qubit in the entangled pair. The compression ratio *R* is defined as: R=NNencodedR = \frac{N}{N_{encoded}}R=Nencoded​N​ where *N* is the length of the original data sequence and *Nencoded* is the number of qubits used to represent the data. The encoding process is described by: ∣ψi⟩=αi∣0⟩+βi∣1⟩|\psi_i\rangle = \alpha_i |0\rangle + \beta_i |1\rangle∣ψi​⟩=αi​∣0⟩+βi​∣1⟩ where αi\alpha_iαi​ and βi\beta_iβi​ are complex amplitudes determined by the data bit xix_ixi​. The decoding process reverses this operation, reconstructing the original data from the measured state of the qubits. The fidelity of the reconstruction is crucial, and the algorithm incorporates techniques to minimize errors due to measurement noise. The overall compression algorithm can be summarized as follows:
The general scheme of data compression using the quantum noiseless coding theorem of Schumacher is dicussed for general quantum sources. When the Hilbert space of the quantum source is decomposable into orthogonal subspaces, one can first perform classical data compression before performing the quantum data compression for individual subspaces. For minimizing the resource in quantum coding, a general parameterization of the dimensions in the Jozsa-Schumacher quantum data compression scheme is presented.
Abstract We examine information loss, resource costs, and run time from practical application of quantum data compression. Compressing quantum data to fewer qubits enables efficient use of resources, as well as applications for quantum communication and denoising. In this context, we provide a description of the quantum and classical components of the hybrid quantum autoencoder algorithm, implemented using IBMs Qiskit language. Utilizing our own data sets, we encode bitmap images as quantum superposition states, which correspond to linearly independent vectors with density matrices of discrete values. We successfully compress this data with near-lossless compression using simulation, and then run our algorithm on an IBMQ quantum chip. We describe conditions and run times for training and compressing our data on quantum devices, and relate trainability to specific characteristics and performance metrics of our parametric quantum circuits.
Ask how the quantum compression of ensembles of pure states is affected by the availability of entanglement, and in settings where the encoder has access to side information. We find the optimal asymptotic quantum rate and the optimal tradeoff (rate region) of quantum and entanglement rates. It turns out that the amount by which the quantum rate beats the Schumacher limit, the entropy of the source, is precisely half the entropy of classical information that can be extracted from the source and side information states without disturbing them at all ("reversible extraction of classical information").In the special case that the encoder has no side information, or that she has access to the identity of the states, this problem reduces to the known settings of blind and visible Schumacher compression, respectively, albeit here additionally with entanglement assistance. We comment on connections to previously studied and further rate tradeoffs when also classical information is considered.
Data compression is a ubiquitous aspect of modern information technology, and the advent of quantum information raises the question of what types of compression are feasible for quantum data, where it is especially relevant given the extreme difficulty involved in creating reliable quantum memories. We present a protocol in which an ensemble of quantum bits (qubits) can in principle be perfectly compressed into exponentially fewer qubits. We then experimentally implement our algorithm, compressing three photonic qubits into two. This protocol sheds light on the subtle differences between quantum and classical information. Furthermore, since data compression stores all of the available information about the quantum state in fewer physical qubits, it could allow for a vast reduction in the amount of quantum memory required to store a quantum ensemble, making even today's limited quantum memories far more powerful than previously recognized.
We describe a method for lossless quantum compression if the output of the information source is not known. We compute the best possible compression rate, minimizing the expected base length of the output quantum bit string (the base length of a quantum string is the maximal length in the superposition). This complements work by Schumacher and Westmoreland who calculated the corresponding rate for minimizing the output's average length. Our compressed code words are prefix-free indeterminate-length quantum bit strings which can be concatenated in the case of multiple sources. Therefore, we generalize the known theory of prefix-free quantum codes to the case where strings have indeterminate length. Moreover, we describe a communication model which allows the lossless transmission of the compressed code words. The benefit of compression is then the reduction of transmission errors in the presence of noise.