Partially smoothed information measures are fundamental tools in one-shot quantum information theory. In this work, we determine the exact strong converse exponents of these measures for both pure quantum states and classical states. Notably, we find that the strong converse exponents based on trace distance takes different forms between pure and classical states, indicating that they are not uniform across all quantum states. Leveraging these findings, we derive the strong converse exponents for quantum data compression, intrinsic randomness extraction, and classical state splitting. A key technical step in our analysis is the determination of the strong converse exponent for classical privacy amplification, which is of independent interest.

We introduce a minimax approach for characterizing the capacities of fully quantum arbitrarily varying channels (FQAVCs) under different shared resource models. In contrast to previous methods, our technique avoids de Finetti-type reductions, providing a more streamlined proof without dependency on the dimension of the jamming system. Consequently, we show that the entanglement-assisted and shared-randomness-assisted capacities of FQAVCs match those of the corresponding compound channels, even in the presence of general quantum adversaries.

The quantum dichotomies problem asks at what rate one pair of quantum states can be approximately mapped into another pair of quantum states. In the many copy limit and for vanishing error, the optimal rate is known to be given by the ratio of the respective quantum relative distances. Here, we study the large-deviation behavior of quantum dichotomies and determine the exact strong converse exponent based on the purified distance. This is the first time to establish the exact high-error large-deviation analysis for this task in fully quantum setting.

We consider the problem of shared randomness-assisted multiple access channel (MAC) simulation for product inputs and characterize the one-shot communication cost region via almost-matching inner and outer bounds in terms of the smooth max-information of the channel, featuring auxiliary random variables of bounded size. The achievability relies on a rejection-sampling algorithm to simulate an auxiliary channel between each sender and the decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments. To bound the cardinality of the auxiliary random variables, we employ the perturbation method from [Anantharam <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>., IEEE Trans. Inf. Theory (2019)] in the one-shot setting. For the asymptotic setting and vanishing errors, our result expands to a tight single-letter rate characterization and consequently extends a special case of the simulation results of [Kurri <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>., IEEE Trans. Inf. Theory (2022)] for fixed, independent and identically distributed (iid) product inputs to universal simulation for any product inputs. We broaden our discussion into the quantum realm by studying feedback simulation of quantum-to-classical (QC) MACs with product measurements [Atif <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>., IEEE Trans. Inf. Theory (2022)]. For fixed product inputs and with shared randomness assistance, we give a quasi tight one-shot communication cost region with corresponding single-letter asymptotic iid expansion.

We determine the exact error and strong converse exponents of shared randomness-assisted channel simulation in worst case total-variation distance. Namely, we find that these exponents can be written as simple optimizations over the R´enyi channel mutual information. Strikingly, and in stark contrast to channel coding, there are no critical rates, allowing a tight characterization for arbitrary rates below and above the simulation capacity. We derive our results by asymptotically expanding the meta-converse for channel simulation [Caoet al., IEEE Trans. Inf. Theory (2024)], which corresponds to nonsignaling assisted codes. We prove this to be asymptotically tight by employing the approximation algorithms from [Bertaet al., Proc. IEEE ISIT (2024)], which show how to round any non-signaling assisted strategy to a strategy that only uses shared randomness. Notably, this implies that any additional quantum entanglement-assistance does not change the error or the strong converse exponents.

International audience

We determine the exact error and strong converse exponent for entanglement-assisted classical-quantum channel simulation in worst case input purified distance. The error exponent is expressed as a single-letter formula optimized over sandwiched Rényi divergences of order $α\in [1, \infty)$, notably without the need for a critical rate--a sharp contrast to the error exponent for classical-quantum channel coding. The strong converse exponent is expressed as a single-letter formula optimized over sandwiched Rényi divergences of order $α\in [\frac{1}{2},1]$. As in the classical work [Oufkir et al., arXiv:2410.07051], we start with the goal of asymptotically expanding the meta-converse for channel simulation in the relevant regimes. However, to deal with non-commutativity issues arising from classical-quantum channels and entanglement-assistance, we critically use various properties of the quantum fidelity, additional auxiliary channel techniques, approximations via Chebyshev inequalities, and entropic continuity bounds.

Information inequalities govern the ultimate limitations in information theory and as such play a pivotal role in characterizing what values the entropy of multipartite states can take. Proving an information inequality, however, quickly becomes arduous when the number of involved parties increases. For classical systems, [Yeung, IEEE Trans. Inf. Theory (1997)] proposed a framework to prove Shannon-type inequalities via linear programming. Here, we derive an analogous framework for quantum systems, based on the strong sub-additivity and weak monotonicity inequalities for the von-Neumann entropy. Importantly, this also allows us to handle constrained inequalities, which - in the classical case - served as a crucial tool in proving the existence of non-standard, so-called non-Shannon-type inequalities [Zhang & Yeung, IEEE Trans. Inf. Theory (1998)]. Our main contribution is the Python package qITIP, for which we present the theory and demonstrate its capabilities with several illustrative examples.

We determine the exact error and strong converse exponents of shared randomness-assisted channel simulation in worst case total-variation distance. Namely, we find that these exponents can be written as simple optimizations over the Rényi channel mutual information. Strikingly, and in stark contrast to channel coding, there are no critical rates, allowing a tight characterization for arbitrary rates below and above the simulation capacity.

The trade-offs between error probabilities in quantum hypothesis testing are by now well-understood in the centralized setting, but much less is known for distributed settings. Here, we study a distributed binary hypothesis testing problem to infer a bipartite quantum state shared between two remote parties, where one of these parties communicates to the tester at zero-rate, while the other party communicates to the tester at zero-rate or higher. As our main contribution, we derive an efficiently computable single-letter formula for the Stein's exponent of this problem, when the state under the alternative is product. As a key tool for proving the converse direction of our results, we develop a quantum version of the blowing-up lemma which may be of independent interest.

We show that Frenkel’s integral representation of the quantum relative entropy provides a natural framework to derive continuity bounds for quantum information measures. Our main general result is a dimension-independent semi-continuity relation for the quantum relative entropy with respect to the first argument. Using it, we obtain a number of results: (1) a tight continuity relation for the conditional entropy in the case where the two states have equal marginals on the conditioning system, resolving a conjecture by Wilde in this special case; (2) a stronger version of the Fannes–Audenaert inequality on quantum entropy; (3) better estimates on the quantum capacity of approximately degradable channels; (4) an improved continuity relation for the entanglement cost; (5) general upper bounds on asymptotic transformation rates in infinite-dimensional entanglement theory; and (6) a proof of a conjecture due to Christandl, Ferrara, and Lancien on the continuity of ’filtered’ relative entropy distances.

We propose an extension of the classical Rényi divergences to quantum states through an optimization over probability distributions induced by restricted sets of measurements. In particular, we define the notion of locally-measured Rényi divergences, where the set of allowed measurements originates from variants of locality constraints between (distant) partiesAandB. We then derive variational bounds on the locally-measured Rényi divergences and systematically discuss when these bounds become exact characterizations. As an application, we evaluate the locally-measured Rényi divergences on variants of highly symmetric data-hiding states, showcasing the reduced distinguishing power of locality-constrained measurements. For n-fold tensor powers, we further employ our variational formulae to derive corresponding additivity results, which gives the locally-measured Rényi divergences operational meaning as optimal rate exponents in asymptotic locally-measured hypothesis testing.

Estimation of quantum relative entropy and its Rényi generalizations is a fundamental statistical task in quantum information theory, physics, and beyond. While several estimators of these divergences have been proposed in the literature along with their computational complexities explored, a limit distribution theory which characterizes the asymptotic fluctuations of the estimation error is still premature. As our main contribution, we characterize these asymptotic distributions in terms of Fréchet derivatives of elementary operator-valued functions. We achieve this by leveraging an operator version of Taylor’s theorem and identifying the regularity conditions needed. As an application of our results, we consider an estimator of quantum relative entropy based on Pauli tomography of quantum states and show that the resulting asymptotic distribution is a centered normal, with its variance characterized in terms of the Pauli operators and states. We utilize the knowledge of the aforementioned limit distribution to obtain asymptotic performance guarantees for a multi-hypothesis testing problem.

We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy - which exactly corresponds to the meta-converse for channel simulation - to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement. As our main result, we prove a guarantee on the ratio of success probabilities of at least$(1-\frac{-1}{\mathbf{e}})$, for both the classical and the quantum setting. We further - show this ratio to be optimal. It can be improved to$(1-\frac{1}{t})$using$o$(ln$(t)$) additional bits (qubits) of communication.

A new finite form of de Finetti's representation theorem is established using elementary information-theoretic tools. The distribution of the first$k$random variables in an exchangeable vector of$n\geq k$random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and an explicit bound is provided. This bound is tighter than those obtained via earlier information-theoretic proofs, and its utility extends to random variables taking values in general spaces. The core argument employed has its origins in the quantum information-theoretic literature.

We consider the problem of simulating a two-sender multiple access channel (MAC) for fixed product inputs, where each sender transmits a message to the decoder over a rate-limited noiseless link based on its input and unlimited randomness shared with the decoder. As our main contribution, we characterize the one-shot communication cost region via almost-matching inner and outer bounds phrased in terms of the smooth max-information of the channel. The achievability relies on a rejection-sampling algorithm to simulate a quantization channel between each sender and decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments relating operational quantities to information measures. Our one-shot results recover the single-letter asymptotic rate region for MAC simulation with fixed, independent and identically distributed product inputs, that was obtained in [Kurri et al., IEEE Transactions on Information Theory 68, 7575 (2022)]. We extend our result to quantum-to-classical channels with a separable decomposition [Atif et al., IEEE Transactions on Information Theory 68, 1085 (2022)], for which we obtain a similar characterization.

We propose an extension of the classical Rényi divergences to quantum states through an optimization over probability distributions induced by restricted sets of measurements. In particular, we define the notion of locally-measured Rényi divergences, where the set of allowed measurements orig-inates from locality constraints between (distant) parties$A$and$B$. As our main result, we derive variational characterizations of these locally-measured Rényi divergences. We then evaluate them for variants of data-hiding states, showcasing the reduced distinguishing power of locality-constrained measurements, and give corresponding applications in locally-measured hypothesis testing.

Estimation of quantum relative entropy is a fundamental statistical task in quantum information theory, physics, and beyond. While several estimators of the same have been proposed in the literature along with their computational complexities explored, a limit distribution theory which characterizes the asymptotic fluctuations of the estimation error is still premature. As our main contribution, we characterize these asymptotic distributions in terms of Fréchet derivatives of elementary operator-valued functions. We achieve this by leveraging an operator version of Taylor's theorem and identifying the regularity conditions needed. As an application of our results, we consider an estimator of quantum relative entropy based on Pauli tomography of quantum states and show that the resulting asymptotic distribution is a centered normal, with its variance characterized in terms of the Pauli operators and states. We utilize the knowledge of the aforementioned limit distribution to obtain asymptotic performance guarantees for a multi-hypothesis testing problem.

We study channel simulation under common randomness assistance in the finite-blocklength regime and identify the smooth channel max-information as a linear program one-shot converse on the minimal simulation cost for fixed error tolerance. We show that this one-shot converse can be achieved exactly using no-signaling-assisted codes, and approximately achieved using common randomness-assisted codes. Our one-shot converse thus takes on an analogous role to the celebrated meta-converse in the complementary problem of channel coding, and we find tight relations between these two bounds. We asymptotically expand our bounds on the simulation cost for discrete memoryless channels, leading to the second-order as well as the moderate-deviation rate expansion, which can be expressed in terms of the channel capacity and channel dispersion known from noisy channel coding. Our bounds imply the well-known fact that the optimal asymptotic rate of one channel to simulate another under common randomness assistance is given by the ratio of their respective capacities. Additionally, our higher-order asymptotic expansion shows that this reversibility falls apart in the second order. Our techniques extend to discrete memoryless broadcast channels. In stark contrast to the elusive broadcast channel capacity problem, we show that the reverse problem of broadcast channel simulation under common randomness assistance allows for an efficiently computable single-letter characterization of the asymptotic rate region in terms of the broadcast channel’s multipartite mutual information.

We study the problem of random-assisted simulation of discrete broadcast channel in one-shot and i.i.d. setups. We derive one-shot inner and outer bounds of the set of attainable message-size pairs for simulating WYZ|Xwithin some total variation distance (TVD) tolerance of ϵ. The inner bounds are based on the bipartite convex split lemma. Whereas the outer bounds are based on the properties of the multi-partite max information. Using these bounds, we establish a single-letter expression of the simulation region of a broadcast channel.

The moderate deviation regime is concerned with the finite block length trade-off between communication cost and error for information processing tasks in the asymptotic regime, where the communication cost approaches a capacity-like quantity and the error vanishes at the same time. We find exact characterisations of these trade-offs for a variety of fully quantum communication tasks, including quantum source coding, quantum state splitting, entanglement-assisted quantum channel coding, and entanglement-assisted quantum channel simulation. The main technical tool we derive is a tight relation between the partially smoothed max-information and the hypothesis testing relative entropy. This allows us to obtain the expansion of the partially smoothed max-information for i.i.d. states in the moderate deviation regime.

Divergence chain rules for channels relate the divergence of a pair of channel inputs to the divergence of the corresponding channel outputs. An important special case of such a rule is the data-processing inequality, which tells us that if the same channel is applied to both inputs then the divergence cannot increase. Based on direct matrix analysis methods, we derive several Rényi divergence chain rules for channels in the quantum setting. Our results simplify and in some cases generalise previous derivations in the literature.

We study the problem of one-shot channel simulation of DMCs with unlimited shared randomness. For any fixed tolerance measured in total variational distance, we propose an achievability bound and a converse bound on the size of the code to simulate the channel. The achievability bound utilizes the convex split lemma, whereas the converse bound is the result of the relationships between smoothed max-divergences and the max-mutual information. The achievability proof does not rely on a "universal state" (compared with some previous related works), and provides a tighter bound. Using the two bounds, we also provide an alternative proof to the reverse Shannon theorem.

In a recent landmark result [Ji et al., arXiv:2001.04383 (2020)], it was shown that approximating the value of a two-player game is undecidable when the players are allowed to share quantum states of unbounded dimension. In this paper, we study the computational complexity of two-player games when the dimension of the quantum systems is bounded by T. More specifically, we give a semidefinite program of size exp(𝒪(T^{12}(log²(AT)+log(Q)log(AT))/ε²)) to compute additive ε-approximations on the value of two-player free games with T× T-dimensional quantum entanglement, where A and Q denote the number of answers and questions of the game, respectively. For fixed dimension T, this scales polynomially in Q and quasi-polynomially in A, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in Q and A. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints that we derive via quantum entropy inequalities.

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorousa priorianda posterioribounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments.

We generalize alternating optimization algorithms of Blahut-Arimoto type to the quantum setting. In particular, we give iterative algorithms to compute the mutual information of quantum channels, the thermodynamic capacity of quantum channels, the coherent information of less noisy quantum channels, and the Holevo quantity of classical-quantum channels. Our convergence analysis is based on quantum entropy inequalities and leads to a priori additive ε-approximations after O (ε-1log N) iterations, where N denotes the input dimension of the channel. We complement our analysis with an a posteriori stopping criterion which allows us to terminate the algorithm after significantly fewer iterations compared to the a priori criterion in numerical examples. Finally, we discuss heuristics to accelerate the convergence.

Due to Csiszár and Körner, the capacity of classical wiretap channels has a single-letter characterization in terms of the private information. For quantum wiretap channels, however, it is known that regularization of the private information is necessary to reach the capacity. Here we study hybrid classical-quantum wiretap channels in order to resolve how much quantumness is needed to witness non-additivity phenomena in Shannon information theory. For wiretap channels with quantum inputs but classical outputs, we prove that the characterization of the capacity in terms of the private information stays single-letter. Hence, entangled input states are of no asymptotic advantage in this setting. For wiretap channels with classical inputs, we show by means of explicit examples that the private information already becomes non-additive when either one of the two receivers becomes quantum (with the other receiver staying classical). This gives non-additivity examples that are not caused by entanglement and illustrates that in the wiretap model quantum adversaries are strictly different from classical adversaries.

Smooth entropies are a tool for quantifying resource trade-offs in (quantum) information theory and cryptography. In typical bi- and multi-partite problems, however, some of the sub-systems are often left unchanged and this is not reflected by the standard smoothing of information measures over a ball of close states. We propose to smooth instead only over a ball of close states which also have some of the reduced states on the relevant sub-systems fixed. This partial smoothing of information measures naturally allows to give more refined characterizations of various information-theoretic problems in the one-shot setting. In particular, we immediately get asymptotic second-order characterizations for tasks such as privacy amplification against classical side information or classical state splitting. For quantum problems like state merging the general resource trade-off is tightly characterized by partially smoothed information measures as well.

We study the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. First, we show that the minimum error of simulation and the one-shot quantum simulation cost under no-signalling assisted codes are given by semidefinite programs. Second, we introduce the channel's smooth max-information, which can be seen as a one-shot generalization of the mutual information of a quantum channel. We provide an exact operational interpretation of the channel's smooth max-information as the one-shot quantum simulation cost under no-signalling assisted codes, which significantly simplifies the study of channel simulation and provides insights and bounds for the case under entanglement-assisted codes. Third, we derive the asymptotic equipartition property of the channel's smooth max-information; i.e., it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. This implies the quantum reverse Shannon theorem in the presence of no-signalling correlations. Finally, we explore the simulation cost of various quantum channels.

Smooth entropies are a tool for quantifying resource trade-offs in information theory and cryptography. However, in typical multi-partite problems some of the sub-systems are often left unchanged and this is not reflected by the standard smoothing of information measures over a ball of close states. We propose to smooth instead only over a ball of close states which also have some of the reduced states on the relevant sub-systems fixed. This partial smoothing of information measures naturally allows to give more refined characterizations of various information-theoretic problems in the one-shot setting. As a consequence, we can derive asymptotic second-order characterizations for tasks such as privacy amplification against classical side information or classical state splitting. For quantum problems like state merging the general resource trade-off is tightly characterized by partially smoothed information measures as well.

We derive converging hierarchies of efficiently computable semidefinite programming outer bounds on the optimal fidelity for the transmission of quantum information over noisy quantum channels. Based on positive partial transpose conditions we give a sufficient criterion for the exact convergence at any given level of the hierarchies. The worst case convergence speed of our hierarchies is quantified via positive semidefinite representable outer approximations on the set of separable Choi states, which are based on novel finite de Finetti theorems for quantum channels.

It is well known that for the discrimination of classical and quantum channels in the finite, non-asymptotic regime, adaptive strategies can give an advantage over non-adaptive strategies. However, Hayashi [IEEE Trans. Inf. Theory 55(8), 3807 (2009)] showed that in the asymptotic regime, the exponential error rate for the discrimination of classical channels is not improved in the adaptive setting. We show that, for the discrimination of classical-quantum channels, adaptive strategies do not lead to an asymptotic advantage. As our main result, this establishes Stein's lemma for classical-quantum channels. Our proofs are based on the concept of amortized distinguishability of channels, which we analyse using entropy inequalities.

We show that the max-Rains information of a quantum channel is an efficiently computable, single-letter strong converse upper bound for transmitting quantum information over quantum channels when assisted by positive-partial-transpose (PPT) preserving channels between every use of the channel. This includes in particular the quantum capacity with local operations and classical communication (LOCC) assistance. For our proof we make use of the amortized entanglement of quantum channels, which is defined as the largest net amount of entanglement that can be generated if the sender and receiver are allowed to share an arbitrary state before using the channel. Our main technical result is that amortization does not enhance the entanglement of quantum channels when entanglement is quantified by the max-Rains relative entropy. We prove this statement by employing semi-definite programming (SDP) duality and SDP formulations for the max-Rains relative entropy and the channel's max-Rains information, found recently in [Wang et al., arXiv:1709.00200].

We study the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. Our main results are as follows. First, we show that the minimum error of simulation under non-signalling assisted codes is efficiently computable via semidefinite programming. The cost of simulating a channel via noiseless quantum channels under non-signalling assisted codes can also be characterized as a semidefinite program. Second, we introduce the channel's smooth max-information, which can be seen as a one-shot generalization of the channel's mutual information. We show that the one-shot quantum simulation cost under non-signalling assisted codes is exactly equal to the channel's smooth max-information. Due to the quantum reverse Shannon theorem, the channel's smooth max-information converges to the channel's mutual information in the independent and identically distributed asymptotic limit. Together with earlier findings on the (activated) non-signalling assisted one-shot capacity of channels [Wang et al., arXiv:1709.05258], this suggest that the operational min- and max-type one-shot analogues of the channel's mutual information are the channel's hypothesis testing relative entropy and the channel's smooth max-information, respectively.

A Markov chain is a tripartite quantum state ρABCwhere there exists a recovery map RB→BCsuch that ρABC= RB→BC(ρAB). More generally, an approximate Markov chain ρABCis a state whose distance to the closest recovered state RB→BC(ρAB) is small. Recently it has been shown that this distance can be bounded from above by the conditional mutual information I(A : C|B)ρof the state. We improve on this connection by deriving the first bound that is tight in the commutative case and features an explicit recovery map that only depends on the reduced state pBC. The key tool in our proof is a multivariate extension of the Golden-Thompson inequality, which allows us to extend logarithmic trace inequalities from two to arbitrarily many matrices.

We establish a converse bounds on the private transmission capabilities of a quantum channel. The main conceptual development builds firmly on the notion of a private state, which is a powerful, uniquely quantum method for simplifying the tripartite picture of privacy involving local operations and public classical communication to a bipartite picture of quantum privacy involving local operations and classical communication. This approach has previously led to some of the strongest upper bounds on secret key rates, including the squashed entanglement and the relative entropy of entanglement. Here we use this approach along with a “privacy test” to establish a general meta-converse bound for private communication.

Quantum-proof randomness extractors are an important building block for classical and quantum cryptography as well as device independent randomness amplification and expansion. Furthermore, they are also a useful tool in quantum Shannon theory. It is known that some extractor constructions are quantum-proof whereas others are provably not [Gavinsky et al., STOC'07]. We argue that the theory of operator spaces offers a natural framework for studying to what extent extractors are secure against quantum adversaries: we first phrase the definition of extractors as a bounded norm condition between normed spaces, and then show that the presence of quantum adversaries corresponds to a completely bounded norm condition between operator spaces. From this, we show that very high min-entropy extractors as well as extractors with small output are always (approximately) quantum-proof. We also study a generalization of extractors called randomness condensers. We phrase the definition of condensers as a bounded norm condition and the definition of quantum-proof condensers as a completely bounded norm condition. Seeing condensers as bipartite graphs, we then find that the bounded norm condition corresponds to an instance of a well-studied combinatorial problem, called bipartite densest subgraph. Furthermore, using the characterization in terms of operator spaces, we can associate to any condenser a Bell inequality (two-player game), such that classical and quantum strategies are in one-to-one correspondence with classical and quantum attacks on the condenser. Hence, we get for every quantum-proof condenser (which includes in particular quantum-proof extractors) a Bell inequality that cannot be violated by quantum mechanics.

We study universal quantum codes for entanglement-assisted quantum communication over compound quantum channels. In this setting, sender and receiver do not know the specific channel that will be used for communication, but only know the set that the channel is selected from. We investigate different variations of the problem: uninformed users, informed receiver, informed sender, and feedback assistance. We derive single-letter formulas for all corresponding channel capacities. Our proofs are based on one-shot decoupling bounds and properties of smooth entropies.

This paper establishes several converse bounds on the private transmission capabilities of a quantum channel. The main conceptual development builds firmly on the notion of a private state, which is a powerful, uniquely quantum method for simplifying the tripartite picture of privacy involving local operations and public classical communication to a bipartite picture of quantum privacy involving local operations and classical communication. This approach has previously led to some of the strongest upper bounds on secret key rates, including the squashed entanglement and the relative entropy of entanglement. Here, we use this approach along with a “privacy test” to establish a general meta-converse bound for private communication, which has a number of applications. The meta-converse allows for proving that any quantum channel's relative entropy of entanglement is a strong converse rate for private communication. For covariant channels, the meta-converse also leads to second-order expansions of relative entropy of entanglement bounds for private communication rates. For such channels, the bounds also apply to the private communication setting in which the sender and the receiver are assisted by unlimited public classical communication, and as such, they are relevant for establishing various converse bounds for quantum key distribution protocols conducted over these channels. We find precise characterizations for several channels of interest and apply the methods to establish converse bounds on the private transmission capabilities of all phase-insensitive bosonic channels.

The relative entropy is the basic concept underlying various information measures like entropy, conditional entropy and mutual information. Here, we discuss how to make use of variational formulas for measured relative entropy and quantum relative entropy for understanding the additivity properties of various entropic quantities that appear in quantum information theory. In particular, we show that certain lower bounds on quantum conditional mutual information are superadditive.

In quantum state redistribution as introduced by Luo and Devetak and Devetak and Yard, there are four systems of interest: the A system held by Alice; the B system held by Bob; the C system that is to be transmitted from Alice to Bob; and the R system that holds a purification of the state in the ABC registers. We give upper and lower bounds on the amount of quantum communication and entanglement required to perform the task of quantum state redistribution in a one-shot setting. Our bounds are in terms of the smooth conditional minand max-entropy, and the smooth max-information. The protocol for the upper bound has a clear structure, building on the work of Oppenheim: it decomposes the quantum state redistribution task into two simpler coherent state merging tasks by introducing a coherent relay. In the independent and identical (i.i.d.) asymptotic limit our bounds for the quantum communication cost converge to the quantum conditional mutual information I(C; R|B), and our bounds for the total cost converge to the conditional entropy H(C|B). This yields an alternative proof of optimality of these rates for quantum state redistribution in the i.i.d. asymptotic limit. In particular, we obtain a strong converse for quantum state redistribution, which even holds when allowing for feedback.

Fawzi and Renner recently established a lower bound on the conditional quantum mutual information (CQMI) of tripartite quantum states ABC in terms of the fidelity of recovery (FoR), i.e., the maximal fidelity of the state ABC with a state reconstructed from its marginal BC by acting only on the C system. The FoR measures quantum correlations by the local recoverability of global states and has many properties similar to the CQMI. Here, we generalize the FoR and show that the resulting measure is multiplicative by utilizing semi-definite programming duality. This allows us to simplify an operational proof by Brandão et al. of the above-mentioned lower bound that is based on quantum state redistribution. In particular, in contrast to the previous approaches, our proof does not rely on de Finetti reductions.

Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).

We show that quantum-to-classical channels, i.e., quantum measurements, can be asymptotically simulated by an amount of classical communication equal to the quantum mutual information of the measurement, if sufficient shared randomness is available. This result generalizes Winter's measurement compression theorem for fixed independent and identically distributed inputs [Winter, CMP 244 (157), 2004] to arbitrary inputs, and more importantly, it identifies the quantum mutual information of a measurement as the information gained by performing it, independent of the input state on which it is performed. Our result is a generalization of the classical reverse Shannon theorem to quantum-to-classical channels. In this sense, it can be seen as a quantum reverse Shannon theorem for quantum-to-classical channels, but with the entanglement assistance and quantum communication replaced by shared randomness and classical communication, respectively. Our proof is based on quantum-proof randomness extractors and the post-selection technique for quantum channels [Christandl et al., PRL 102 (020504), 2009].

Recently a new quantum generalization of the Rényi divergence and the corresponding conditional Rényi entropies was proposed. Here we report on a surprising relation between conditional Rényi entropies based on this new generalization and conditional Rényi entropies based on the quantum relative Rényi entropy that was used in previous literature. This generalizes the well-known duality relation H(A|B)+H(A|C) = 0 for tripartite pure states to Rényi entropies of two different kinds. As a direct application, we prove a collection of inequalities that relate different conditional Rényi entropies.

The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.

We show that quantum-to-classical channels, i.e., quantum measurements, can be asymptotically simulated by an amount of classical communication equal to the quantum mutual information of the measurement, if sufficient shared randomness is available. This result generalizes Winter's measurement compression theorem for fixed independent and identically distributed inputs to arbitrary inputs, and more importantly, it identifies the quantum mutual information of a measurement as the information gained by performing it, independent of the input state on which it is performed. Our result is a generalization of the classical reverse Shannon theorem to quantum-to-classical channels. In this sense, it can be seen as a quantum reverse Shannon theorem for quantum-to-classical channels, but with the entanglement assistance and quantum communication replaced by shared randomness and classical communication, respectively. The proof is based on a novel one-shot state merging protocol for classically coherent states as well as the postselection technique for quantum channels, and it uses techniques developed for the quantum reverse Shannon theorem.

The entanglement cost of a quantum channel is the minimal rate at which entanglement (between sender and receiver) is needed in order to simulate many copies of a quantum channel in the presence of free classical communication. In this paper, we show how to express this quantity as a regularized optimization of the entanglement formation over states that can be generated between sender and receiver. Our formula is the channel analog of a well-known formula for the entanglement cost of quantum states in terms of the entanglement of formation and shares a similar relation to the recently shattered hope for additivity. The entanglement cost of a quantum channel can be seen as the analog of the quantum reverse Shannon theorem in the case where free classical communication is allowed. The techniques used in the proof of our result are then also inspired by a recent proof of the quantum reverse Shannon theorem and feature the one-shot formalism for quantum information theory, the postselection technique for quantum channels as well as Sion's minimax theorem. We discuss two applications of our result. First, we are able to link the security in the noisy-storage model to a problem of sending quantum rather than classical information through the adversary's storage device. This not only improves the range of parameters where security can be shown, but also allows us to prove security for storage devices for which no results were known before. Second, our result has consequences for the study of the strong converse quantum capacity. Here, we show that any coding scheme that sends quantum information through a quantum channel at a rate larger than the entanglement cost of the channel has an exponentially small fidelity.

A natural question in characterizing the information theoretic power of quantum channels is to ask at what rate entanglement is needed in order to asymptotically simulate a quantum channel in the presence of free classical communication. We call this the entanglement cost of a channel, and prove a formula describing it for all channels. We discuss two applications. Firstly, we are able to link the security in the noisy-storage model to a problem of sending quantum rather than classical information through the adversary's storage device. This not only greatly improves the range of parameters where security could be shown previously, but allows us to prove security for storage devices for which no non-trivial statements were known before. Secondly, our result has consequences for the study of the strong converse quantum capacity. Here, we show that any coding scheme that sends quantum information through a quantum channel at a rate larger than the entanglement cost of the channel has an exponentially small fidelity.