An introduction to Quantum Information Theory and applications to Locally Decodable Codes

Iordanis Kerenidis
Centre National de la Recherche Scientifique (CNRS)

Quantum computation and information studies how information is encoded
in nature according to the laws of quantum mechanics and what this
means for its computational power. Although, it is a rather new
research area, there have been numerous surprising results, for
example Shor's algorithm for factoring large numbers and the existence
of unconditionally secure key distribution, that make quantum
information a very exciting and fundamental research field.

In this talk, we give an introduction to the theory of quantum
information by drawing comparisons to classical probability theory. We
start by defining the carrier of quantum information, the quantum bit,
and proceed to describe a notion of entropy for quantum states.
Quantum information theory is a rich mathematical theory that can be used as a powerful tool for the study of classical information, as, for example, in the proof of the Exponential Lower Bound for 2-Query Locally Decodable Codes (see also talks by de Wolf and Wehner)

Presentation (PDF File)

Back to Workshop II: Locally decodable codes, private information retrieval, privacy-preserving data-mining, and public key encryption with special properties