Quantum encodings and applications to locally decodable codes and communication complexity

Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. On one hand, the ability of a quantum system to be in a superposition of states provides a way to encode an exponential amount of information in a quantum state. However, this information is accessible only indirectly via measurements. The goal of this thesis is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. (1) We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long standing open question in the area of quantum communication complexity. (2) We show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity. We resolve a main open question about the efficiency of Locally Decodable Codes by reducing the problem to one about quantum codes and solving the latter using tools from quantum information theory. This is the first example where quantum techniques are essential in resolving a purely classical question. (3) We investigate the power of quantum encodings in the area of cryptography. We study certain cryptographic primitives, such as Private Information Retrieval, Symmetrically-Private Information Retrieval and Coin Flipping.