Descriptif
This course is an introduction to the concept of a quantum computer. It uses quantum-mechanical principles and generalizes classical computers. It has been demonstrated that such a computer can solve in polynomial time problems that are considered to be hard for a classical computer such as factoring large integers or solving the discrete logarithm problem (this is Shor's algorithm). The security of virtually all public-key cryptography used in practice right now relies on the hardness of these problems and a quantum computer would break those cryptosystems. It has also been found that such a computer is able to search in an unstructured set much more efficiently than a classical computer (this is Grover's algorithm). We will cover in this course the bases of quantum computation and present the main quantum algorithms that offer a speedup over classical algorithms. We will also cover other applications of quantum mechanics, such as simulating physical systems or quantum cryptography. The latter exploits the laws of quantum physics to establish the security of certain cryptographic primitives, such as key distribution protocols.
Objectifs pédagogiques
The aim of this course is to
- explain the basic principles of a quantum computer
- give an overview of the problems for which there is a quantum speed-up
- explain what we can do right now in quantum computing.
Diplôme(s) concerné(s)
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade réduitPour les étudiants du diplôme Diplôme d'ingénieur de l'Ecole polytechnique
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme M1 Informatique - Voie Jacques Herbrand - X
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 4 ECTS
Programme détaillé
1) Introduction
- qubits and quantum registers
- measurement and unitary evolution
- elementary gates
- the Einstein-Podolsky-Rosen paradox, quantum teleportation, superdense
coding
2) The circuit model
- classical and quantum circuits
- universality of quantum computation with a restricted set of
elementary gates
3) The first algorithms
- Deutsch-Josza
- Bernstein-Vazirani
- Simon's algorithm
4) Advanced algorithms
- the Grover algorithm
- the amplitude amplification algorithm, other algorithms that are
relevant to cryptography such as collision algorithms
5) Advanced algorithms based on the quantum Fourier transform
- the quantum Fourier transform
- application: phase estimation
- the abelian hidden subgroup problem
- application : Shor's algorithm for factoring and solving the discrete
logarithm problem
6) Hamiltonian simulation
- Hamiltonians
- applications to quantum chemistry
- the Lie-Suzuki-Trotter method
- the LCU method
7) Advanced algorithm for solving large linear systems: the
Harrow-Hassidim-Lloyd algorithm
8) Quantum cryptography
- quantum key distribution
Support pédagogique multimédia
