Bounds on information combining are a fundamental tool in coding theory, in particular when analyzing polar codes and belief propagation. They usually bound the evolution of random variables with respect to their Shannon entropy. In recent work this approach was generalized to Renyi $α$-entropies. However, due to the lack of a traditional chain rule for Renyi entropies the picture remained incomplete. In this work we establish the missing link by providing Renyi chain rules connecting different definitions of Renyi entropies by Hayashi and Arimoto. This allows us to provide new information combining bounds for the Arimoto Renyi entropy. In the second part, we generalize the chain rule to the quantum setting and show how they allow us to generalize results and conjectures previously only given for the von Neumann entropy. In the special case of $α=2$ we give the first optimal information combining bounds with quantum side information.
Bounds on information combining are a fundamental tool in coding theory, in particular when analyzing polar codes and belief propagation. They usually bound the evolution of random variables with respect to their Shannon entropy. In recent work this approach was generalized to Renyi α-entropies. However, due to the lack of a traditional chain rule for Renyi entropies the picture remained incomplete. In this work we establish the missing link by providing Renyi chain rules connecting different definitions of Renyi entropies by Hayashi and Arimoto. This allows us to provide new information combining bounds for the Arimoto Renyi entropy. In the second part, we generalize the chain rule to the quantum setting and show how they allow us to generalize results and conjectures previously only given for the von Neumann entropy. In the special case of α=2 we give the first optimal information combining bounds with quantum side information.
“Bounds on information combining” are entropic inequalities that determine how the information (entropy) of a set of random variables can change when these are combined in certain ways. Such bounds play an important role in classical information theory, particularly in coding and Shannon theory. The arguably most elementary kind of information combining is the addition of two binary random variables (a CNOT gate), and the resulting quantities play an important role in Belief propagation and Polar coding. We investigate this problem in the setting where quantum side information is available. Our main technical result is a non-trivial, and close to optimal, lower bound on the combined entropy, which can be seen as an almost optimal “quantum Mrs. Gerber's Lemma”. Our proof uses three main ingredients: (1) a new bound on the concavity of von Neumann entropy; (2) the quantitative improvement of strong subadditivity due to Fawzi-Renner; (3) recent duality results due to Renes et al. We furthermore present conjectures on the optimal bounds under quantum side information, supported by analytical observations and strong numerical evidence. We finally apply our bounds to Polar coding for classical-quantum channels, and show that even non-stationary channels polarize, the blocklength required to approach the symmetric capacity scales at most sub-exponentially in the gap to capacity and under the lower bound conjecture a blocklength polynomial in the gap suffices.
“Bounds on information combining” are entropic inequalities that determine how the information (entropy) of a set of random variables can change when these are combined in certain prescribed ways. Such bounds play an important role in classical information theory, particularly in coding and Shannon theory; entropy power inequalities are special instances of them. The arguably most elementary kind of information combining is the addition of two binary random variables (a CNOT gate), and the resulting quantities play an important role in belief propagation and polar coding. We investigate this problem in the setting where quantum side information is available, which has been recognized as a hard setting for entropy power inequalities. Our main technical result is a non-trivial, and close to optimal, lower bound on the combined entropy, which can be seen as an almost optimal “quantum Mrs. Gerber's Lemma”. Our proof uses three main ingredients: 1) a new bound on the concavity of von Neumann entropy, which is tight in the regime of low pairwise state fidelities; 2) the quantitative improvement of strong subadditivity due to Fawzi-Renner, in which we manage to handle the minimization over recovery maps; and 3) recent duality results on classical-quantum-channels due to Renes et al. We furthermore present conjectures on the optimal lower and upper bounds under quantum side information, supported by interesting analytical observations and strong numerical evidence. We finally apply our bounds to polar coding for binary-input classical-quantum channels, and show the following three results: 1) even non-stationary channels polarize under the polar transform; 2) the blocklength required to approach the symmetric capacity scales at most sub-exponentially in the gap to capacity; and 3) under the aforementioned lower bound conjecture, a blocklength polynomial in the gap suffices.
The Rényi entropy of general order unifies the well-known Shannon entropy with several other entropy notions, like the min-entropy or collision entropy. In contrast to the Shannon entropy, there seems to be no commonly accepted definition for the conditional Rényi entropy: several versions have been proposed and used in the literature. In this paper, we reconsider the definition for the conditional Rényi entropy of general order as proposed by Arimoto in the seventies. We show that this particular notion satisfies several natural properties. In particular, we show that it satisfies monotonicity under conditioning, meaning that conditioning can only reduce the entropy, and (a weak form of) chain rule, which implies that the decrease in entropy due to conditioning is bounded by the number of bits one conditions on. None of the other suggestions for the conditional Rényi entropy satisfies both these properties. Finally, we show a natural interpretation of the conditional Rényi entropy in terms of (unconditional) Rényi divergence, and we show consistency with a recently proposed notion of conditional Rényi entropy in the quantum setting.
The Rényi entropies constitute a family of information measures that generalizes the well-known Shannon entropy, inheriting many of its properties. They appear in the form of unconditional and conditional entropies, relative entropies, or mutual information, and have found many applications in information theory and beyond. Various generalizations of Rényi entropies to the quantum setting have been proposed, most prominently Petz's quasi-entropies and Renner's conditional min-, max-, and collision entropy. However, these quantum extensions are incompatible and thus unsatisfactory. We propose a new quantum generalization of the family of Rényi entropies that contains the von Neumann entropy, min-entropy, collision entropy, and the max-entropy as special cases, thus encompassing most quantum entropies in use today. We show several natural properties for this definition, including data-processing inequalities, a duality relation, and an entropic uncertainty relation.
The R\'enyi entropies constitute a family of information measures that generalizes the well-known Shannon entropy, inheriting many of its properties. They appear in the form of unconditional and conditional entropies, relative entropies or mutual information, and have found many applications in information theory and beyond. Various generalizations of R\'enyi entropies to the quantum setting have been proposed, most notably Petz's quasi-entropies and Renner's conditional min-, max- and collision entropy. Here, we argue that previous quantum extensions are incompatible and thus unsatisfactory.
We propose a new quantum generalization of the family of R\'enyi entropies and the corresponding relative entropies that contains the min-entropy, collision entropy, von Neumann entropy as well as the max-entropy as special cases, thus encompassing most quantum entropies in use today. We show several natural properties for this definition, including data-processing inequalities and a limited duality relation.
We conclude that the treatment of these entropies is technically challenging and requires sophisticated tools from linear algebra. We share several conjectured properties which we were unable to prove.
Quantum R\'enyi relative entropies play a significant part in characterizing operational tasks in quantum information theory. In this paper, we first give some fundamental properties of the zero-relative entropy, and we find that the geometric R\'enyi relative entropy reduces to the zero-relative entropy in the limit case. Then, we define a new mutual information via the zero-relative entropy, and it is the so-called zero-mutual information. In particular, the zero-mutual information is a lower bound of the Petz-R\'enyi and geometric generalized mutual information. We establish the chain rules for the unsmoothed and smoothed versions of the zero-mutual information. As an application, we discuss generalized mutual information with the Petz-R\'enyi, sandwiched R\'enyi, and geometric R\'enyi types, our result gives a uniform chain rule inequality for quantum generalized mutual information.