Quantum computing has emerged about a decade ago. In this course we aim to give a basic introduction to this exciting field, mainly focusing on a description of the model and algorithms. Lecture 1: Quantum computing – the model, teleportation, quantum key distribution, no cloning, classical reversible circuits, general quantum circuits and universality, quantum simulation of probabilistic circuits. Lecture 2: Quantum black-box, Deutsch’s algorithm, Deutsch-Josza, Simon’s algorithm, Hidden subgroup problem, Quantum Fourier Transform. Lecture 3: Shor’s algorithm for factoring, Grover’s algorithm for unstructured search. (Cours organisés en collaboration avec l’Ecole Doctorale de Physique de la Région Parisienne – ED 107)

CNRS, LIAFA, Paris 7