Each year computing machines become faster and faster, but they use still use at their base the same Newtonian physics. Feynman in 1982 already asked about the necessity of this restriction to classical physics. The idea behind quantum computation is to use quantum phenomena to solve tasks that conventional machines cannot achieve.
Historically the first result that showed the superiority of the quantum model was in cryptography. Bennett and Brassard in 1984 gave a first quantum protocol for perfectly secure key distribution. Such an unconditional security does not exist in the classical world.
At present many important concepts of theoretical computer science have been extended to quantum computation, from communication to algorithms and error correcting codes.
The aim of this course is to present the bases of several concepts about quantum computation. The emphasis will be on quantum information and communication. We will describe the basics of Quantum Information Theory and its applications in quantum cryptography, communication complexity and most strikingly in classical complexity theory.
Course overview
Quantum Information (Iordanis Kerenidis/Sophie Laplante)
basics of quantum computing, fundamental algorithms, teleportation, ...
quantum information theory and applications to classical complexity theory
quantum cryptography: key distribution, bit commitment, coin flipping
Quantum Communication Complexity: quantum fingerprints, separations between classical and quantum communication
Quantum Algorithms (Miklos Santha/Julia Kempe)
Shor's factoring algorithm
Grover's Search algorithm
quantum walk algorithms
group theoretic algorithms
10 courses of 3 hours (8 lectures, 2 TD)
Language of the course
Lectures will be in English. Homework assignments and exams will be available in English
and French, at the students' request, and can be written in either language.
A good base in algorithms and complexity is helpful
(elementary algorithms, circuits, complexity classes).
Knowledge of discrete probabilities and basic information theory (Shannon entropy) helpful.
![[arobase]](./commercial_at.png){kind=small}
mpri![[point]](./full_stop.png){kind=small}
master![[Version Française]](./french_flag.png)