Skip to main content
Foundations of Information, Networks, and Decision Systems

Talk information 09/12/2024

Title: Information-theoretic aspects of hypothesis exclusion

Speaker: Mark Wilde
Date and Time: 09/12/2024 4:10PM ET
Location: Rhodes 310 and Zoom

Abstract: In the task of hypothesis exclusion, one is given a system whose state is randomly selected from a finite set, and the goal is to identify a state from the set that is not the true state of the system. That is, the goal of hypothesis exclusion is to exclude the true hypothesis, rather than to identify it. An error, i.e., an unsuccessful exclusion, occurs if and only if the state identified is the true state. The quantum variant of this task, called quantum state exclusion, is an operational task that has significance in studying foundational questions related to interpreting quantum theory.

In this FIND seminar, we study the optimal error probability of hypothesis exclusion and its error exponent — the rate at which the error probability decays asymptotically — from an information-theoretic perspective. Our main finding for the classical case is an exact characterization of the error exponent in terms of a quantity we call the multivariate Chernoff divergence. In the more general quantum case, we establish a single-letter upper bound on the error exponent of state exclusion given by the multivariate log-Euclidean Chernoff divergence.

In the final part of the talk, we also extend our analysis to the more complicated task of quantum channel exclusion, and we establish a single-letter and efficiently computable upper bound on its error exponent, even assuming the use of adaptive strategies. We derive both upper bounds, for state and channel exclusion, based on one-shot analysis and formulate them as a type of multivariate divergence measure called a barycentric Chernoff divergence. Our result on channel exclusion has implications in two important special cases. First, for the special case of two hypotheses, our upper bound provides the first known efficiently computable upper bound on the error exponent of symmetric binary channel discrimination. Second, for the special case of classical channels, we show that our upper bound is achievable by a nonadaptive strategy, thus solving the exact error exponent of classical channel exclusion.

Joint work with Kaiyuan Ji, Hemant Mishra, and Milan Mosonyi and available as https://arxiv.org/abs/2407.13728.

Bio: Mark M. Wilde received the Ph.D. degree in electrical engineering from the University of Southern California, Los Angeles, California. He is an Associate Professor of Electrical and Computer Engineering at Cornell University. He is an IEEE Fellow, he is a recipient of the National Science Foundation Career Development Award, he is a co-recipient of the 2018 AHP-Birkhauser Prize, awarded to “the most remarkable contribution” published in the journal Annales Henri Poincare, and he is an Outstanding Referee of the American Physical Society. His current research interests are in quantum Shannon theory, quantum computation, quantum optical communication, quantum computational complexity theory, and quantum error correction.