An Algorithmic Theory of Communication – ACOM

In the road towards quantum technologies that can achieve a quantum advantage, a major bottleneck is the large overhead needed to correct for errors caused by unwanted noise. Despite important research activity and great progress in designing better error correcting codes, the fundamental limits of communication over a quantum noisy medium are far from being understood. In fact, it is fair to say that we do not have a satisfactory quantum analogue of Shannon's celebrated noisy coding theorem.

The objective of this project is to leverage tools from optimization theory in order to build an Algorithmic theory of COMmunication that would go beyond the current approach founded by Shannon's paper “A Mathematical Theory of Communication”. The goal is to establish efficient algorithms that determine the optimal method for reliable communication using a noisy medium. This approach is particularly appealing in the context of quantum information theory for at least two reasons. First, Shannon's approach of determining the asymptotic maximum rate for reliable communication in terms of an entropic quantity has found significant hurdles, in particular due to the non-additivity of many quantum entropic quantities. Second, the asymptotic definition of communication rates has little practical relevance, at least for the near future of quantum technologies.

Our aim is to develop efficient algorithms that take as input a description of a quantum noise model and output a near-optimal method for reliable communication under this noise model. For example, we expect our algorithm to give answers to questions such as: how many qubits can be reliably transmitted using 100 photons that undergo depolarizing noise with parameter 5%? We expect these algorithms to contribute to optimizing communication over quantum networks, as well as to building fault-tolerant quantum computing devices with fewer resources. In addition, we will develop algorithms to efficiently approximate quantum entropic quantities and explore applications to quantum cryptography and entanglement measures. The developed open-source software will be made available for use by the public. Moreover, we will establish general methods to compute the operationally-relevant quantum entropy of a large composite system as a function of its components and will apply it to obtain tight and non-asymptotic security bounds for quantum cryptographic protocols.