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

One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys

Joseph M. Renes, Renato Renner

Published Aug 14, 2016• 50 citations
OpenAlex

Abstract

The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max-entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields bounds on the amount of common randomness and secret key that can be recovered in one-shot from hybrid classical-quantum systems using one-way classical communication.

Related papers

One-Shot Classical Data Compression With Quantum Side Information and the Distillation of Common Randomness or Secret Keys

Joseph M. Renes, Renato Renner

The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields tight bounds on the amount of common randomness and secret key that can be recovered in one shot from hybrid classical-quantum systems using one-way classical communication.

arXiv:1008.0452•IEEE Transactions on Information Theory•Feb 28, 2012•71 citations

Rethinking quantum smooth entropies: Tight one-shot analysis of quantum privacy amplification

Bartosz Regula, Marco Tomamichel

We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.

quant-pharXiv:2603.04493•Mar 6, 2026•0 citations

Duality of privacy amplification against quantum adversaries and data compression with quantum side information

Joseph M. Renes

Information processing protocols are typically built out of simpler parts, called primitives, and two of the most important such primitives are privacy amplification (PA) and data compression. The former extracts the truly secret part of some classical data, while the latter squeezes it into the smallest possible form. We show these tasks are dual in the setting of quantum information processing. Specifically, the tasks of PA of classical information against quantum adversaries and classical data compression with quantum side information are dual in the sense that the ability to perform one implies the ability to perform the other. The duality arises because the two protocols are connected by complementarity and the uncertainty principle in the quantum setting. Applications include a new uncertainty principle formulated in terms of smooth min- and max-entropies, which are useful in the study of one-shot protocols, as well as new conditions for approximate quantum error correction.

arXiv:1003.0703•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Dec 15, 2010•36 citations

Noisy Channel Coding via Privacy Amplification and Information Reconciliation

Joseph M. Renes, Renato Renner

We show that optimal protocols for noisy channel coding of public or private information over either classical or quantum channels can be directly constructed from two more primitive information-theoretic protocols: privacy amplification and information reconciliation, also known as data compression with side information. We do this in the one-shot scenario of structureless resources, and formulate our results in terms of the smooth min- and max-entropy. In the context of classical information theory, this shows that essentially all two-terminal protocols can be reduced to these two primitives, which are in turn governed by the smooth min- and max-entropies, respectively. In the context of quantum information theory, the recently-established duality of these two protocols means essentially all two-terminal protocols can be constructed using just a single primitive. As an illustration, we show how optimal noisy channel coding protocols can be constructed solely from privacy amplification.

arXiv:1012.4814•IEEE Transactions on Information Theory•Aug 3, 2011•107 citations

Classical data compression with quantum side information

Igor Devetak, Andreas Winter

The problem of classical data compression when the decoder has quantum side information at his disposal is considered. This is a quantum generalization of the classical Slepian-Wolf theorem. The optimal compression rate is found to be reduced from the Shannon entropy of the source by the Holevo information between the source and side information.

arXiv:quant-ph/0209029•Physical Review A•Oct 3, 2003•118 citations

Equivalence of Three Classical Algorithms With Quantum Side Information: Privacy Amplification, Error Correction, and Data Compression

Toyohiro Tsurumaru

Privacy amplification (PA) is an indispensable component in classical and quantum cryptography. Error correction (EC) and data compression (DC) algorithms are also indispensable in classical and quantum information theory. We here study these three algorithms (PA, EC, and DC) in the presence of quantum side information, and show that they all become equivalent in the one-shot scenario. As an application of this equivalence, we take previously known security bounds of PA, and translate them into coding theorems for EC and DC which have not been obtained previously. Further, we apply these results to simplify and improve our previous result that the two prevalent approaches to the security proof of quantum key distribution (QKD) are equivalent. We also propose a new method to simplify the security proof of QKD.

arXiv:2009.08823•IEEE Transactions on Information Theory•Nov 8, 2021•8 citations
The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max-entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields bounds on the amount of common randomness and secret key that can be recovered in one-shot from hybrid classical-quantum systems using one-way classical communication.
The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields tight bounds on the amount of common randomness and secret key that can be recovered in one shot from hybrid classical-quantum systems using one-way classical communication.
We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.
Information processing protocols are typically built out of simpler parts, called primitives, and two of the most important such primitives are privacy amplification (PA) and data compression. The former extracts the truly secret part of some classical data, while the latter squeezes it into the smallest possible form. We show these tasks are dual in the setting of quantum information processing. Specifically, the tasks of PA of classical information against quantum adversaries and classical data compression with quantum side information are dual in the sense that the ability to perform one implies the ability to perform the other. The duality arises because the two protocols are connected by complementarity and the uncertainty principle in the quantum setting. Applications include a new uncertainty principle formulated in terms of smooth min- and max-entropies, which are useful in the study of one-shot protocols, as well as new conditions for approximate quantum error correction.
We show that optimal protocols for noisy channel coding of public or private information over either classical or quantum channels can be directly constructed from two more primitive information-theoretic protocols: privacy amplification and information reconciliation, also known as data compression with side information. We do this in the one-shot scenario of structureless resources, and formulate our results in terms of the smooth min- and max-entropy. In the context of classical information theory, this shows that essentially all two-terminal protocols can be reduced to these two primitives, which are in turn governed by the smooth min- and max-entropies, respectively. In the context of quantum information theory, the recently-established duality of these two protocols means essentially all two-terminal protocols can be constructed using just a single primitive. As an illustration, we show how optimal noisy channel coding protocols can be constructed solely from privacy amplification.
Privacy amplification (PA) is an indispensable component in classical and quantum cryptography. Error correction (EC) and data compression (DC) algorithms are also indispensable in classical and quantum information theory. We here study these three algorithms (PA, EC, and DC) in the presence of quantum side information, and show that they all become equivalent in the one-shot scenario. As an application of this equivalence, we take previously known security bounds of PA, and translate them into coding theorems for EC and DC which have not been obtained previously. Further, we apply these results to simplify and improve our previous result that the two prevalent approaches to the security proof of quantum key distribution (QKD) are equivalent. We also propose a new method to simplify the security proof of QKD.