The asymptotic rates of information-theoretic protocols - including error exponents, compression rates, and channel capacities - are traditionally defined under the idealised assumption that the underlying resource (state or channel) is independent and identically distributed (i.i.d.). Somewhat surprisingly, even slight departures from the exact i.i.d. structure can lead to a drastic breakdown of these protocols. The asymptotic rates of information theoretic protocols - error exponents, compression rates, capacities - were originally evaluated taking for granted that the underlying source (state or channel) is i.i.d. Differently from what we might expect at first glance, it is not hard to exhibit instances of protocols that may drastically fail when the i.i.d. assumption holds only approximately rather than exactly. If the precise nature of the perturbation from the i.i.d. regime is known (e.g. a pointwise defect), we could design a bespoke protocol that compensates for the defect (for example, by discarding the corrupted subsystem). However, in any realistic setting, neither can the i.i.d. behaviour of the system be precisely guaranteed, nor can the deviations from the ideal regime be determined exactly. In this paper we answer the following question: are there protocols that can still achieve the optimal asymptotic rates when the i.i.d. resource is replaced by any arbitrary almost i.i.d. resource along it? What is the nature of the unknown perturbation under which protocols like these are possible? We focus, in particular, on hypothesis testing, data compression, and channel coding. As a by-product of our analysis, we introduce the notion of club distance, as a variant of the well-known diamond distance, and of an almost i.i.d. process, which may be of independent interest.
The asymptotic rates of information-theoretic protocols - including error exponents, compression rates, and channel capacities - are traditionally defined under the idealised assumption that the underlying resource (state or channel) is independent and identically distributed (i.i.d.). Somewhat surprisingly, even slight departures from the exact i.i.d. structure can lead to a drastic breakdown of these protocols. The asymptotic rates of information theoretic protocols - error exponents, compression rates, capacities - were originally evaluated taking for granted that the underlying source (state or channel) is i.i.d. Differently from what we might expect at first glance, it is not hard to exhibit instances of protocols that may drastically fail when the i.i.d. assumption holds only approximately rather than exactly. If the precise nature of the perturbation from the i.i.d. regime is known (e.g. a pointwise defect), we could design a bespoke protocol that compensates for the defect (for example, by discarding the corrupted subsystem). However, in any realistic setting, neither can the i.i.d. behaviour of the system be precisely guaranteed, nor can the deviations from the ideal regime be determined exactly. In this paper we answer the following question: are there protocols that can still achieve the optimal asymptotic rates when the i.i.d. resource is replaced by any arbitrary almost i.i.d. resource along it? What is the nature of the unknown perturbation under which protocols like these are possible? We focus, in particular, on hypothesis testing, data compression, and channel coding. As a by-product of our analysis, we introduce the notion of club distance, as a variant of the well-known diamond distance, and of an almost i.i.d. process, which may be of independent interest.
The generalised quantum Stein's lemma is a key result in quantum hypothesis testing, and connects this fundamental primitive of quantum information processing with quantum resource manipulation, a task that is central for technological applications. Prior works have proved this statement in the idealised setting of independent and identically distributed (i.i.d.) sequences of quantum states, and recent extensions consider also sources that are 'close' to i.i.d., according to the strict notion put forth by Mazzola, Sutter, and Renner. For several applications, however, one would need to consider yet more general sources. We establish a version of the generalised quantum Stein's lemma that is conceptually much simpler and general, as it applies to any source that is asymptotically close to an i.i.d. state with respect to the normalised quantum Wasserstein distance of order 1. As an immediate consequence, we solve the Stein exponent of a scenario where the null hypothesis is arbitrarily varying, expressing it in terms of i.i.d. Stein exponents corresponding to arbitrary states in the convex hull of the null hypothesis base set.
The Quantum Reverse Shannon Theorem has been a milestone in quantum information theory. It states that asymptotically reliable simulation of a quantum channel, assisted by unlimited shared entanglement, requires a rate of classical communication equal to the channel’s entanglement-assisted classical capacity. In this paper, we study the error exponent of quantum channel simulation, which characterizes the optimal speed of exponential convergence of the performance towards the perfect, as the blocklength increases. Based on channel purified distance, we derive lower and upper bounds for the error exponent. Then we show that the two bounds coincide when the classical communication rate is below a critical value, and hence, we have determined the exact formula of the error exponent in the low-rate case. This enables us to obtain an operational interpretation to the channel’s sandwiched Rényi information of order from 1 to 2, since our formula is expressed as a transform of this quantity. In the derivation, we have also obtained an achievability bound for quantum channel simulation in the finite-blocklength setting, which is of realistic significance.
Information-theoretic techniques are based on the assumption that resources are well characterized by independent and identically distributed (iid) states. This assumption cannot be justified operationally, since, for example, correlations between subsequent systems emitted by a source cannot be detected by any practical tomographic protocol. Operationally motivated symmetry assumptions still imply, via de Finetti theorems, that the resources are described by almost-iid states. This raises the question: Are almost-iid resources as effective as perfect iid resources for information-processing tasks? Here we address this question and prove that the conditional entropy of almost-iid states asymptotically coincides with that of iid states. As an application, this implies that squashed entanglement is robust for almost-iid states, asymptotically matching its value on iid states.
We study the robustness of asymptotic entanglement manipulation for Mazzola--Sutter--Renner (MSR) almost-iid sources, which allow a sublinear number of deviations from tensor-power structure. For pure sources along ∣φ⟩AB, every concentration rate below S(φA) is achievable by a single Schur--Weyl protocol depending only on the rate and local Hilbert spaces. For general sources along ρAB, every distillation rate below ED(ρAB) is achievable by a single LOCC protocol sequence independent of the particular source and defect size. Its error vanishes exponentially and uniformly for each prescribed defect bound rn=o(n), yielding an optimal universal distillation rate equal to ED(ρAB). For dilution, the entanglement cost of every MSR almost-iid target sequence along ρAB is at most EF∞(ρAB), the regularized entanglement of formation of the reference state. Consequently, every MSR almost-iid sequence along a pure reference state ∣φ⟩AB is asymptotically reversible, with distillable entanglement and entanglement cost equal to S(φA), even when its individual states are mixed. The proofs establish structural and entropic properties of MSR almost-iid sources that may be useful in other information-theoretic settings.
A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constantE(W,R)which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.
Given two families of quantum states A and B, called the null and the alternative hypotheses, quantum hypothesis testing is the task of determining whether an unknown quantum state belongs to A or B. Mistaking A for B is a type I error, and vice versa for the type II error. In quantum Shannon theory, a fundamental role is played by the Stein exponent, i.e. the asymptotic rate of decay of the type II error probability for a given threshold on the type I error probability. Stein exponents have been thoroughly investigated -- and, sometimes, calculated. However, most currently available solutions apply to settings where the hypotheses simple (i.e. composed of a single state), or else the families A and B need to satisfy stringent constraints that exclude physically important sets of states, such as separable states or stabiliser states. In this work, we establish a general formula for the Stein exponent where both hypotheses are allowed to be composite: the alternative hypothesis B is assumed to be either composite i.i.d. or arbitrarily varying, with components taken from a known base set, while the null hypothesis A is fully general, and required to satisfy only weak compatibility assumptions that are met in most physically relevant cases -- for instance, by the sets of separable or stabiliser states. Our result extends and subsumes the findings of [BBH, CMP 385:55, 2021] (that we also simplify), as well as the 'generalised quantum Sanov theorem' of [LBR, arXiv:2408.07067]. The proof relies on a careful quantum-to-classical reduction via measurements, followed by an application of the results on classical Stein exponents obtained in [Lami, arXiv:today]. We also devise new purely quantum techniques to analyse the resulting asymptotic expressions.