Information Theory 6

Abstract: We study hypothesis testing (aka state certification) in the \emph{non-identically distributed} setting. A recent work (Garg et~al.~2023) considered the classical case, in which one is given (independent) samples from $T$ unknown probability distributions $p_1, \dots, p_T$ on $[d] = \{1, 2, \dots, d\}$, and one wishes to accept/reject the hypothesis that their average $p_{\textnormal{avg}}$ equals a known hypothesis distribution~$q$. Garg et al.~showed that if one has just $c = 2$ samples from each $p_i$, and provided $T \gg \frac{\sqrt{d}}{\eps^2} + \frac{1}{\eps^4}$, one can (whp) distinguish $p_{\textnormal{avg}} = q$ from $\dtv{p_{\textnormal{avg}}}{q} > \eps$. This nearly matches the optimal result for the classical iid setting (namely, $T \gg \frac{\sqrt{d}}{\eps^2}$). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical \emph{quantum} states. Here we uncover an unexpected phenomenon: for any $d$-dimensional hypothesis state~$\sigma$, and given just a \emph{single} copy ($c = 1$) of each state $\rho_1, \dots, \rho_T$, one can distinguish $\rho_{\textnormal{avg}} = \sigma$ from $\Dtr{\rho_{\textnormal{avg}}}{\sigma} > \eps$ provided $T \gg d/\eps^2$. (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with $c = 1$ is provably impossible in the classical case. A technical tool we introduce may be of independent interest: an Efron--Stein inequality, and more generally an Efron--Stein decomposition, in the quantum setting.

Abstract: We study the quantum umlaut information, a correlation measure defined for bipartite quantum states as a reversed variant of the quantum mutual information. We show that it has an operational interpretation as the asymptotic error exponent in the hypothesis testing task of deciding whether a given bipartite state is product or not. We generalise the umlaut information to quantum channels, where it also extends the notion of `oveloh information' [Nuradha et al., arXiv:2404.16101]. We prove that channel umlaut information is additive for classical-quantum channels, while we observe additivity violations for fully quantum channels. Inspired by recent results in entanglement theory, we then show as our main result that the regularised umlaut information constitutes a fundamental measure of the quality of classical information transmission over a quantum channel - as opposed to the capacity, which quantifies the quantity of information that can be sent. This interpretation applies to coding assisted by activated non-signalling correlations, and the channel umlaut information is in general larger than the corresponding expression for unassisted communication as obtained by Dalai for the classical-quantum case [IEEE Trans. Inf. Theory 59, 8027 (2013)]. In the classical unassisted setting, the channel umlaut information has a further operational interpretation as the zero-rate error exponent of list decoding in the large list limit. Combined with prior works on non-signalling--assisted zero-error channel capacities, our findings imply a dichotomy between the settings of zero-rate error exponents and zero-error communication. While our results are single-letter only for classical-quantum channels, we also give a single-letter bound for fully quantum channels in terms of the `geometric' version of umlaut information.

Abstract: A major line of questions in quantum information and computing asks how quickly locally random circuits converge to resemble global randomness. In particular, approximate k-designs are random unitary ensembles that resemble random circuits up to their first k moments. It was recently shown that on n qudits, random circuits with slightly structured architectures converge to k-designs in depth O(log n), even on one-dimensional connectivity. It has however remained open whether the same shallow depth applies more generally among random circuit architecture and connectivity, or if the structure is truly necessary. We recall the study of exponential relative entropy decay, another topic with a long history in quantum information theory. We show that a constant number of layers of a parallel random circuit on a family of architectures including one-dimensional `brickwork' has O(1 / logn) per-layer multiplicative entropy decay. We further show that on general connectivity graphs of bounded degree, randomly placed gates achieve O(1 / nlogn)-decay (consistent with log n depth convergence). Both of these results imply that random circuit ensembles with O(polylog(n)) average depth achieve k-designs in diamond norm. Hence our results address the question of whether extra structure is truly necessary for log-depth convergence. Furthermore, the relative entropy recombination techniques might be of independent interest.