22 november 2010
Quantum information-theory and cryptography
Dr. S. Fehr
(Centrum voor Wiskunde & Informatica, Amsterdam)
As far as we currently understand nature, its behaviour at
nanoscale is described by the laws of quantum mechanics.
Inherent to quantum mechanics are strange effects, like
the superposition principle or Heisenberg’s uncertainty
relation. Making specific use of quantum mechanical
effects has a significant impact on the (in)existence of
certain information processing tasks. Famous examples
are Shor’s quantum algorithm for factoring integers and
Bennett and Brassard’s quantum-key-distribution scheme.
In classical information theory and computer science,
“information” is mathematically modelled by random
variables and their distributions, and “computation” is
formalized by the notion of a Turing machine. In order to
formally study information processing in a quantum world,
we need to adjust these abstract concepts as to reflect the
quantum mechanical behaviour of things.
In this lecture, I will show how to mathematically
capture the concept of “quantum information”, and I
will demonstrate that quantum information may behave
radically different to its classical counterpart. It sometimes
even “solves the impossible”. In the second part, I will
discuss some applications of quantum information and its
properties to cryptography.