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

Quantum Information and Computation

Simple construction of quantum universal variable-length source coding

Masahito Hayashi, Koji Matsumoto

Published Nov 1, 2002• 22 citations
Publisher

Abstract

We simply construct a quantum universal variable-length source code in which, independent of information source, both of the average error and the probability that the coding rate is greater than the entropy rate H(\overline{\rho}_p), tend to 0. If H(\overline{\rho}_p) is estimated, we can compress the coding rate to the admissible rate H(\overline{\rho}_p) with a probability close to 1. However, when we perform a naive measurement for the estimation of H(\overline{\rho}_p), the input state is demolished. By smearing the measurement, we successfully treat the trade-off between the estimation of H(\overline{\rho}_p) and the non-demolition of the input state. Our protocol can be used not only for the Schumacher's scheme but also for the compression of entangled states.

DOI
10.26421/qic2.s-2

Related papers

Simple construction of quantum universal variable-length source coding

Masahito Hayashi, Keiji Matsumoto

We simply construct a quantum universal variable-length source code in which, independent of information source, both of the average error and the probability that the coding rate is greater than the entropy rate $H(rho_p)$, tend to 0. If $H(rho_p)$ is estimated, we can compress the coding rate to the admissible rate $H(rho_p)$ with a probability close to 1. However, when we perform a naive measurement for the estimation of $H(rho_p)$, the input state is demolished. By smearing the measurement, we successfully treat the trade-off between the estimation of $H(rho_p)$ and the non-demolition of the input state. Our protocol can be used not only for the Schumacher's scheme but also for the compression of entangled states.

arXiv:quant-ph/0209124•Sep 24, 2002•3 citations

Simple construction of quantum universal variable-length source coding

Masahito Hayashi, Koji Matsumoto

This paper describes the construction of a quantum universal variable-length source code in which, independent of information source, both of the average error and the probability that the coding rate is greater than the entropy rate H(/spl rho/~/sub p/), tend to 0. If H(/spl rho/~/sub p/) is estimated, and compress the coding rate to the admissible rate H(/spl rho/~/sub p/) with a probability close to 1. However, when we perform a naive measurement for the estimation of H(/spl rho/~/sub p/), the input state is demolished. By smearing the measurement, we successfully treat the trade-off between the estimation of H(/spl rho/~/sub p/) and the nondemolition of the input state. Our protocol can be used not only for the Schumacher's compression but also for the compression of entangled states.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2003•4 citations

Quantum universal variable-length source coding

Masahito Hayashi, Keiji Matsumoto

We construct an optimal quantum universal variable-length code that achieves the admissible minimum rate, i.e., our code is used for any probability distribution of quantum states. Its probability of exceeding the admissible minimum rate exponentially goes to 0. Our code is optimal in the sense of its exponent. In addition, its average error asymptotically tends to 0.

arXiv:quant-ph/0202001•Physical Review A•Aug 26, 2002•89 citations

Universal quantum information compression and degrees of prior knowledge

Richard Jozsa, Stuart Presnell

We describe a universal information–compression scheme that compresses any pure quantum independent identically distributed (i.i.d.) source asymptotically to its von Neumann entropy, with no prior knowledge of the structure of the source. We introduce a diagonalization procedure that enables any classical compression algorithm to be used in a quantum context. Our scheme is then based on the corresponding quantum translation of the classical Lempel–Ziv algorithm. Our methods lead to a conceptually simple way of estimating the entropy of a source in terms of the measurement of an associated length parameter while maintaining high fidelity for long blocks. As a byproduct we also estimate the eigenbasis of the source. Since our scheme is based on the Lempel–Ziv method, it can potentially be applied also to non–i.i.d. sources that satisfy some further regularity conditions.

arXiv:quant-ph/0210196•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Nov 25, 2003•30 citations

Weak measurements and universal compression of quantum information sources

Alexei Kaltchenko

We present a new quantum data compression scheme, which optimally compresses any completely ergodic quantum information source with a Markovian property. The scheme does not assume any apriory knowledge of the source (other than complete ergodicity and the Markovian property) and uses so-called "weak" (non-demolition) measurements to estimate the eigenbasis and entropy rate of the source. The scheme is fully universal in the sense of being source independent.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•0 citations

Lower Bound on Expected Communication Cost of Quantum Huffman Coding

Anurag Anshu, Ankit Garg, Aram W. Harrow +1 more

Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.

Leibniz international proceedings in informatics•Jan 1, 2016•0 citations
We simply construct a quantum universal variable-length source code in which, independent of information source, both of the average error and the probability that the coding rate is greater than the entropy rate H(\overline{\rho}_p), tend to 0. If H(\overline{\rho}_p) is estimated, we can compress the coding rate to the admissible rate H(\overline{\rho}_p) with a probability close to 1. However, when we perform a naive measurement for the estimation of H(\overline{\rho}_p), the input state is demolished. By smearing the measurement, we successfully treat the trade-off between the estimation of H(\overline{\rho}_p) and the non-demolition of the input state. Our protocol can be used not only for the Schumacher's scheme but also for the compression of entangled states.
We simply construct a quantum universal variable-length source code in which, independent of information source, both of the average error and the probability that the coding rate is greater than the entropy rate H(rhop)H(rho_p)H(rhop​), tend to 0. If H(rhop)H(rho_p)H(rhop​) is estimated, we can compress the coding rate to the admissible rate H(rhop)H(rho_p)H(rhop​) with a probability close to 1. However, when we perform a naive measurement for the estimation of H(rhop)H(rho_p)H(rhop​), the input state is demolished. By smearing the measurement, we successfully treat the trade-off between the estimation of H(rhop)H(rho_p)H(rhop​) and the non-demolition of the input state. Our protocol can be used not only for the Schumacher's scheme but also for the compression of entangled states.
This paper describes the construction of a quantum universal variable-length source code in which, independent of information source, both of the average error and the probability that the coding rate is greater than the entropy rate H(/spl rho/~/sub p/), tend to 0. If H(/spl rho/~/sub p/) is estimated, and compress the coding rate to the admissible rate H(/spl rho/~/sub p/) with a probability close to 1. However, when we perform a naive measurement for the estimation of H(/spl rho/~/sub p/), the input state is demolished. By smearing the measurement, we successfully treat the trade-off between the estimation of H(/spl rho/~/sub p/) and the nondemolition of the input state. Our protocol can be used not only for the Schumacher's compression but also for the compression of entangled states.
We describe a universal information–compression scheme that compresses any pure quantum independent identically distributed (i.i.d.) source asymptotically to its von Neumann entropy, with no prior knowledge of the structure of the source. We introduce a diagonalization procedure that enables any classical compression algorithm to be used in a quantum context. Our scheme is then based on the corresponding quantum translation of the classical Lempel–Ziv algorithm. Our methods lead to a conceptually simple way of estimating the entropy of a source in terms of the measurement of an associated length parameter while maintaining high fidelity for long blocks. As a byproduct we also estimate the eigenbasis of the source. Since our scheme is based on the Lempel–Ziv method, it can potentially be applied also to non–i.i.d. sources that satisfy some further regularity conditions.
Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.