MU4PY118: Algorithmic complexity theory (3 ECTS)
This unit offers general training in algorithmic complexity theory to physics students interested in the interface between physics and computer science, in particular quantum information. We will try to present, in particular, the richness of the formal construction of this discipline, its historical developments and its vast field of applications illustrated by numerous examples. 

Thematics / Notions and content:

• Modèles de calcul: Machine de Turing et circuits booléens

• Calculabilité, complexité en temps et en espace, uniforme ou non-uniforme.

• Calcul déterministe, non-déterministe, randomisé 

• Classes de complexité (P, NP, PSPACE, P/poly, hiérarchie polynomiale)

• Complexité et cryptographie

MU4PY201: Classical and quantum Shannon’s Theory (6 ECTS)
This unit offers a general training in information theory (Shannon theory) to students who want to integrate a Master 2 in research, in particular related to quantum information.  We will try to demonstrate, in particular, how based on the concept of entropy, it is possible to characterize information data processing, in the presence or not of noise. Applications to telecommunications, classical or quantum, will be shown, but also links with thermodynamics and open quantum systems.

Thematics / Notions and content:

Classical Shannon theory:

• entropies de Shannon, Boltzmann et von Neuman: physique et mesures de l'information

• encodage optimal: compression et correction d'erreur

• entropies conditionnelles classiques: erreurs discrètes et bruits additifs continus

• communications, informations mutuelles et capacités

• mesures entropiques de l’intrication quantique

• exemples classiques et quantiques (distribution quantique de clé, débit des télécommunications classiques, démon de Maxwell)