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. The ability of a quantum system to be in
a superposition of states enables us to store an exponential amount of
information in a quantum system. 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.

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.
Furthermore, 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. This is the first example where quantum
techniques are essential in resolving a purely classical question.
Last, we study the power of quantum encodings in the area of cryptography.