Depuis les années 90, des algorithmes comme celui de Peter Shor [Shor, 1997] ont permis de réaliser le gain substantiel que représenterait la réalisation d’un ordinateur quantique. Dès lors, de grandes entreprises et certains états ont mobilisé de nombreux moyens pour y parvenir. Parallèlement, une recherche très active se développe dans cette éventualité. Tour à tour, les différentes communautés scientifiques s’emparent de ces outils. La communauté RO organise des écoles d’été en lien avec de nouveaux masters (Sorbonne, Master parcours IQ), des liens très forts sont développés en géométrie algébrique [Jaffali, 2020] et des articles comme celui de Montanaro sur le backtracking quantique [Montanaro, 2016] amènent la réflexion à maturité, notamment pour SAT et CSP. Cet exposé est basé sur [Mermin, 2020, Jaffali, 2020, Perdrix, ] et l’école thématique de Montpellier (2-5 novembre 2021). Nous nous intéresserons à la notion de bit quantique, d’intrication et aux particularités des algorithmes quantiques pour la communauté SAT et CSP. Enfin, nous évoquerons quelques perspectives de recherche dans le domaine du ≪ Machine Learning Quantique (QML) ≫. 

[Jaffali, 2020] Jaffali, H. (2020). Étude de l’Intrication dans les Algorithmes Quantiques : Approche Géométrique et Outils Dérivés. PhD thesis. 2020UBFCA017. 

[Mermin, 2020] Mermin, D. (2020). Calculs et algorithmes quantiques. Number 978-2-271-07017-3. EDP Sciences, cnrs editions edition. 

[Montanaro, 2016] Montanaro, A. (2016). Quantum walk speedup of backtracking algorithms. 

[Perdrix, ] Perdrix, S. Pépites algorithmiques - informatique quantique. 

[Shor, 1997] Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5) :1484–1509.