Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing

Alors que des prototypes d'ordinateur quantique encore très limités voient progressivement le jour, un véritable travail de fourmi s'est enclenché, au sein d'une communauté encore trop restreinte, pour comprendre et maîtriser toutes les facettes du calcul quantique, de la modélisation à la réalisation expérimentale, en passant par la solution algorithmique, son analyse, sa programmation et sa vérification.
Dans les années 1980, Richard Feynman suggérait qu'un ordinateur fonctionnant selon les règles de la physique quantique pourrait résoudre des problèmes intraitables par un ordinateur classique. Il faudra attendre 2019 pour que Google effectue un calcul sur un prototype de circuit quantique programmable. Cette prouesse, qui remet en question les fondements de la thèse de Church-Turing, a ouvert la voie à nombre de start-up, grandes entreprises du numérique et gouvernements qui s'orientent peu à peu vers cette technologie à laquelle on prédit de larges champs d'application : intelligence artificielle, cryptographie et sécurité, finance, santé. Un travail de grande ampleur s'est enclenché pour comprendre toutes les facettes du calcul quantique, notamment des algorithmes, et relever le défi de ce nouveau tournant technologique.