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:1707.03619

A unified approach to source and message compression

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

Published Jul 12, 2017• 14 citations
arXivHTMLPDF

Abstract

We study the problem of source and message compression in the one-shot setting for the point-to-point and multi-party scenarios (with and without side information). We derive achievability results for these tasks in a unified manner, using the techniques of convex-split, which was introduced in [Anshu,Devabathini and Jain 2014] and position-based decoding introduced in [Anshu, Jain and Warsi 2017], which in turn uses hypothesis testing between distributions. These results are in terms of smooth max divergence and smooth hypothesis testing divergence. As a by-product of the tasks studied in this work, we obtain several known source compression results (originally studied in the asymptotic and i.i.d. setting) in the one-shot case. One of our achievability results includes the problem of message compression with side information, originally studied in [Braverman and Rao 2011]. We show that both our result and the result in [Braverman and Rao 2011] are near optimal in the one-shot setting by proving a converse bound.

DOI
10.48550/arxiv.1707.03619

Related papers

Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

This paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting.

arXiv:1703.02342•IEEE Transactions on Information Theory•May 8, 2019•23 citations

On the Compression of Messages in the Multi-Party Setting

Anurag Anshu, Penghui Yao

We consider the following communication task in the multi-party setting, which involves joint random variables X Y Z M N with the property that M is independent of Y Z N conditioned on X, and N is independent of X Z M conditioned on Y . Three parties Alice, Bob and Charlie, respectively, observe samples x, y and z from X Y Z. Alice and Bob communicate messages to Charlie with the goal that Charlie can output a sample (m, n) such that the distribution of (x, y, z, m, n) is close to X Y Z M N. This task reflects the simultaneous message passing communication complexity. Furthermore, it is a generalization of some well studied problems in information theory, such as distributed source coding, source coding with a helper and one sender and one receiver message compression. It is also closely related to the lossy distributed source coding task. Our main result is an achievable communication region for this task in the one-shot setting, through which we obtain a nearly optimal characterization using auxiliary random variables of bounded size. We employ our achievability result to provide a nearly optimal one-shot communication region for the task of lossy distributed source coding, in terms of auxiliary random variables of bounded size. Finally, we show that interactions are necessary to achieve the optimal expected communication cost.

arXiv:1808.06449•IEEE Transactions on Information Theory•Jan 9, 2020•1 citation

On the near-optimality of one-shot classical communication over quantum channels

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

We study the problem of transmission of classical messages through a quantum channel in several network scenarios in the one-shot setting. We consider both the entanglement assisted and unassisted cases for the point to point quantum channel, the quantum multiple-access channel, the quantum channel with a state, and the quantum broadcast channel. We show that it is possible to near-optimally characterize the amount of communication that can be transmitted in these scenarios, using the position-based decoding strategy introduced in a prior study (A. Anshu, R. Jain, and N. Warsi, https://ieee.org/document/8399830). In the process, we provide a short and elementary proof of the converse for entanglement-assisted quantum channel coding in terms of the quantum hypothesis testing divergence [obtained earlier in the work of W. Matthews and S. Wehner, IEEE Trans. Inf. Theory 60, 7317–7329 (2014)]. Our proof has the additional utility that it naturally extends to various network scenarios mentioned above. Furthermore, none of our achievability results require a simultaneous decoding strategy, existence of which is an important open question in quantum Shannon theory.

arXiv:1804.09644•Journal of Mathematical Physics•Jan 1, 2019•27 citations

A One-Shot Achievability Result for Quantum State Redistribution

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

We study the problem of entanglement-assisted quantum state redistribution in the one-shot setting and provide a new achievability result on the quantum communication required. Our bounds are in terms of the max-relative entropy and the hypothesis testing relative entropy. We use the techniques of convex split and position-based decoding to arrive at our result. We show that our result is upper bounded by the result obtained in Berta et al. (2016).

arXiv:1702.02396•IEEE Transactions on Information Theory•Nov 29, 2017•21 citations

Achievability bounds on quantum state redistribution using convex split and position based decoding

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

Quantum state redistribution is a fundamental quantum information theoretic primitive that captures a generic quantum communication scenario. In this work, we study the problem of entanglement assisted quantum state redistribution in one-shot setting and provide a new achievability result on the quantum communication required. Our bounds are in terms of max relative entropy and Rényi relative entropy of order 2. We show that our result is upper bounded by the result obtained in Berta, Christandl, Touchette (2016) (which is in terms of smooth conditional max and min entropies). We use the techniques of convex split and position based decoding (through pretty good measurement) to arrive at our result. Furthermore, in order to clarify the connection between our result and other recent results that use convex split and position based decoding, we prove a new relation between the hypothesis testing relative entropy and Rényi relative entropy of order 2.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•0 citations

One-shot bounds for various information theoretic problems using smooth min and max Rényi divergences

Naqueeb Ahmad Warsi

One-shot analogues for various information theory results known in the asymptotic case are proven using smooth min and max Rényi divergences. In particular, we prove that smooth min Rényi divergence can be used to prove one-shot analogue of the Stein's lemma. Using smooth min Rényi divergence we prove a special case of packing lemma in the one-shot setting. Furthermore, we prove a one-shot analogue of covering lemma using smooth max Rényi divergence. We also propose one-shot achievable rate for source coding under maximum distortion criterion. This achievable rate is quantified in terms of smooth max Rényi divergence.

IEEE Information Theory Workshop (ITW)•Sep 1, 2013•10 citations
We study the problem of source and message compression in the one-shot setting for the point-to-point and multi-party scenarios (with and without side information). We derive achievability results for these tasks in a unified manner, using the techniques of convex-split, which was introduced in [Anshu,Devabathini and Jain 2014] and position-based decoding introduced in [Anshu, Jain and Warsi 2017], which in turn uses hypothesis testing between distributions. These results are in terms of smooth max divergence and smooth hypothesis testing divergence. As a by-product of the tasks studied in this work, we obtain several known source compression results (originally studied in the asymptotic and i.i.d. setting) in the one-shot case. One of our achievability results includes the problem of message compression with side information, originally studied in [Braverman and Rao 2011]. We show that both our result and the result in [Braverman and Rao 2011] are near optimal in the one-shot setting by proving a converse bound.
This paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting.
We consider the following communication task in the multi-party setting, which involves joint random variables X Y Z M N with the property that M is independent of Y Z N conditioned on X, and N is independent of X Z M conditioned on Y . Three parties Alice, Bob and Charlie, respectively, observe samples x, y and z from X Y Z. Alice and Bob communicate messages to Charlie with the goal that Charlie can output a sample (m, n) such that the distribution of (x, y, z, m, n) is close to X Y Z M N. This task reflects the simultaneous message passing communication complexity. Furthermore, it is a generalization of some well studied problems in information theory, such as distributed source coding, source coding with a helper and one sender and one receiver message compression. It is also closely related to the lossy distributed source coding task. Our main result is an achievable communication region for this task in the one-shot setting, through which we obtain a nearly optimal characterization using auxiliary random variables of bounded size. We employ our achievability result to provide a nearly optimal one-shot communication region for the task of lossy distributed source coding, in terms of auxiliary random variables of bounded size. Finally, we show that interactions are necessary to achieve the optimal expected communication cost.
We study the problem of transmission of classical messages through a quantum channel in several network scenarios in the one-shot setting. We consider both the entanglement assisted and unassisted cases for the point to point quantum channel, the quantum multiple-access channel, the quantum channel with a state, and the quantum broadcast channel. We show that it is possible to near-optimally characterize the amount of communication that can be transmitted in these scenarios, using the position-based decoding strategy introduced in a prior study (A. Anshu, R. Jain, and N. Warsi, https://ieee.org/document/8399830). In the process, we provide a short and elementary proof of the converse for entanglement-assisted quantum channel coding in terms of the quantum hypothesis testing divergence [obtained earlier in the work of W. Matthews and S. Wehner, IEEE Trans. Inf. Theory 60, 7317–7329 (2014)]. Our proof has the additional utility that it naturally extends to various network scenarios mentioned above. Furthermore, none of our achievability results require a simultaneous decoding strategy, existence of which is an important open question in quantum Shannon theory.
Quantum state redistribution is a fundamental quantum information theoretic primitive that captures a generic quantum communication scenario. In this work, we study the problem of entanglement assisted quantum state redistribution in one-shot setting and provide a new achievability result on the quantum communication required. Our bounds are in terms of max relative entropy and Rényi relative entropy of order 2. We show that our result is upper bounded by the result obtained in Berta, Christandl, Touchette (2016) (which is in terms of smooth conditional max and min entropies). We use the techniques of convex split and position based decoding (through pretty good measurement) to arrive at our result. Furthermore, in order to clarify the connection between our result and other recent results that use convex split and position based decoding, we prove a new relation between the hypothesis testing relative entropy and Rényi relative entropy of order 2.
One-shot analogues for various information theory results known in the asymptotic case are proven using smooth min and max Rényi divergences. In particular, we prove that smooth min Rényi divergence can be used to prove one-shot analogue of the Stein's lemma. Using smooth min Rényi divergence we prove a special case of packing lemma in the one-shot setting. Furthermore, we prove a one-shot analogue of covering lemma using smooth max Rényi divergence. We also propose one-shot achievable rate for source coding under maximum distortion criterion. This achievable rate is quantified in terms of smooth max Rényi divergence.