Informatique quantique pour la recherche opérationnelle (ROQ)
- Titre :
- Informatique quantique pour la recherche opérationnelle (ROQ)
- Section :
- Optionnel
- État pour cette année :
- OPEN
- Mots clés :
- Informatique quantique, Algorithme de Grover, QAOA, Qiskit
- Ects :
- 2
- Responsable :
- Dimitri Watel (ENSIIE)
- Intervenants :
-
Camille Grange (LIRMM SNCF)Dimitri Watel (ENSIIE)
- Prérequis :
Algèbre linéaire, Programmation linéaire, Complexité des algorithmes, Circuit logique
- Objectif :
Ce cours a pour objectif de former les apprenants à l'informatique quantique. A l'issue du cours, les apprentants maîtriseront les concepts permettant de concevoir des algorithmes quantiques pour des problèmes de décision ou d'optimisation, d'estimer la complexité de ces algorithmes et d'utiliser les outils existants (langages de programmation, simulateurs et accès à de vraies machines quantiques), notamment pour résoudre des problèmes classiques de recherche opérationnelle. Ce cours apporte, premièrement, la possibilité de concevoir des algorithmes pour des ordinateurs quantiques qui pourraient voir le jour dans une ou plusieurs décenies, et, secondement, de sortir du cadre de l'algorithmique classique avec un autre paradigme, une autre manière de réfléchir pour concevoir des algorithmes.
- Contenu / Plan :
- Bases de l'informatique quantique, Algorithmes à base d'oracle (Algorithme de Deutsch-Jozsa)
- Algorithmes à base d'oracle (suite, Algorithme de Bernstein Vazirani et de Grover)
- TP introductif à qiskit, Résolution de problèmes d'optimisations, notamment avec l'algorithme de Grover
- TP Résolution de problèmes d'optimisations, notamment avec l'algorithme de Grover (suite)
- Algorithmes variationnels quantiques, Théorème adiabatique, Quantum Approximate Optimization Algorithm (Algorithme QAOA)
- Examen (demi-séance), TP sur l'algorithme QAOA
Remarque
Le cours pourrait être mutualisé avec une option de l'ENSIIE qui a lieu le mardi entre début Novembre (après les vacances de Octobre/Novembre) et la première semaine de Janvier. Cette option compte 12 séances en tout. Le programme présenté ici est complété avec : l'algorithme de Shor, des notions de complexités (puissance des machines quantique, simulation des machines quantique, portes univerelles, calcule une borne inférieure de la complexité de l'algorithme de Grover), quelques TD et quelques TP (utilisation du simulateur Quirk, un TP sur Qiskit introductif supplémentaire, et un TP sur QAOA supplémentaire).
- Bibliographie :
-
-
Livre : "Quantum Un peu de mathématiques pour l'informatique quantique" d'Arnaud Bodin.
ISBN : 979-8758133095 https://exo7math.github.io/quantum-exo7/ -
Cours du collège de France, par Frédéric Magniez
https://www.college-de-france.fr/chaire/frederic-magniez-informatique-et-sciences-numeriques-chaire-annuelle/events?type=All -
Article : Bernstein, E., Vazirani, U. (1997). Quantum complexity theory. SIAM journal on computing , 26(5), 1411-1473.
https://epubs.siam.org/doi/10.1137/S0097539796300921. -
Article : Watrous, J. (2008). Quantum computational complexity.
https://arxiv.org/abs/0804.3401 -
Article : Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219).
https://arxiv.org/abs/quant-ph/9605043 -
Livre : "Quantum Computation and Quantum Information" de Nielsen M.A. et Chuang I.L
ISBN : 978-1107619197 -
Livre : Quantum computier science de Mermin N.D.
ISBN : 978-0521876582
-
- Liens :
- Compétences visées :
-
Concevoir un algorithme quantique à base d'oracle pour résoudre un problème de décision ou d'optimisation.
-
Utiliser les algorithmes de Grover et de QAOA comme des boîtes noires pour résoudre un problème de décision ou d'optimisation.
-
Comprendre les avantages et les limites de l'informatique quantique.
-
Utiliser Qiskit pour programmer ces algorithmes et les faire fonctionner sur des simulateurs ou des machines réelles.
-
- Modalités de contrôle :
- Examen lors de la dernière séance (Coefficient 1).
- Projet (Coefficient X???°