Interactive quantum information theory

Quantum information theory has developed tremendously over the past two decades, with analogues and extensions of the source coding and channel coding theorems for unidirectional communication. Meanwhile, for interactive communication, a quantum analogue of communication complexity has been developed, for which quantum protocols can provide exponential savings over the best possible classical protocols for some classical tasks. However, quantum information is much more sensitive to noise than classical information. It is therefore essential to make the best use possible of quantum resources.  In this thesis, we take an information-theoretic point of view on interactive quantum  protocols and study the interactive analogues of source compression and  noisy channel coding. The setting we consider is that of quantum communication complexity:  Alice and Bob want to perform some joint quantum computation while  minimizing the required amount of communication. Local computation is deemed free.  Our results are split  into three distinct chapters, and these are organized in such a way that each can  be read independently.  Given its central role in the context of interactive compression, we devote a chapter to the task of quantum state redistribution. In particular, we prove lower  bounds on its communication cost that are robust in the context of interactive communication. We also prove one-shot, one-message achievability bounds.  In a subsequent chapter, we define a new, fully quantum notion of information  cost for interactive protocols and a corresponding notion of information complexity for bipartite tasks. It characterizes how much quantum information, rather than quantum  communication, Alice and Bob must exchange in order to implement a given bipartite task. We prove many structural properties for these quantities, and provide an operational interpretation for quantum information complexity as the amortized quantum communication complexity. In the special case of classical inputs, we provide an alternate characterization of information  cost that provides an answer to the following question about quantum protocols:  what is the cost of forgetting classical information? Two applications are presented: the first general multi-round direct-sum theorem for quantum protocols, and a tight lower bound, up to polylogarithmic terms, for the bounded-round quantum communication complexity of the disjointness function.  In a final chapter, we initiate the study of the interactive quantum capacity of noisy channels. Since techniques to distribute entanglement are well-studied, we focus on a model with perfect pre-shared entanglement and noisy classical communication. We show that even in the harder setting of adversarial errors, we can tolerate a provably maximal error rate of one half minus epsilon, for an arbitrarily small epsilon greater than zero, at positive communication rates. It then follows that random noise channels with positive capacity for unidirectional transmission also have positive interactive quantum capacity.  We conclude with a discussion of our results and further research directions in interactive quantum information theory.

Keyphrases: Compression, Communication complexity, Coding theory, Direct sum, Disjointness, Information complexity, One-shot information theory, Quantum computation and information, Quantum state redistribution