Intervention de Cédric Villani

– Je n'ai pas souvenir d'avoir vu une justification de ce « n puissance un plus epsilon » (n1+ε) complètement explicitée. Je me souviens l'avoir lu dans un ouvrage de Leslie Valiant. Les grands ouvrages comme ceux de Donald Knuth ne s'intéressent pas aux mécanismes physiques, mais uniquement au nombre d'opérations élémentaires à réaliser et à leur complexité. Ils classifient les problèmes abstraits suivant les difficultés à résoudre, les dispositifs permettant de les surmonter, etc. Pour cette raison, la discipline se développe bien avant l'apparition des ordinateurs quantiques, de la même façon que la théorie de la programmation est apparue bien avant les langages, avec des précurseurs comme Ada Lovelace.

Pendant longtemps on s'est demandé – certains se le demandent encore – si la programmation quantique restera uniquement une discipline universitaire, ou sera effectivement mise en oeuvre dans les laboratoires de recherche, et pour les utilisateurs.

Aujourd'hui, on voit que les ordinateurs disposent de cinquante qubits, là où il leur en faudrait mille fois plus. Le jour où l'on aura des ordinateurs performants, capables de résoudre des tâches complexes, la question se posera de façon très forte et concrète. Un encadré en page deux de la note évoque précisément cet algorithme de Shor qui, en 1994, a vraiment, d'un coup, mis sous les feux de la rampe la question de la programmation quantique, en montrant que le problème de la factorisation, alors perçu comme très difficile, deviendrait facile à résoudre si l'on pouvait disposer d'ordinateurs quantiques. On voit que sur un tel sujet, les avantages comparatifs obtenus peuvent être considérables. Comme indiqué dans l'encadré, il faut commencer par représenter le problème dans un formalisme adapté au calcul quantique, avec une combinaison d'états, comme des atomes qui se trouveraient à 10 % dans un état, 20 % dans un deuxième, 2 % dans un troisième, etc. tant qu'ils restent dans un état quantique et tant qu'on n'effectue pas de mesure les obligeant à prendre un état unique défini.

Une fois le problème mis sous cette forme, on agit sur tous ces objets à la fois. On commence par préparer le problème d'une façon permettant de le traiter en beaucoup moins d'opérations qu'avant, un peu comme si au lieu de passer en revue toutes les pages d'un livre de façon linéaire, opération très longue, on agissait simultanément sur toutes les pages du livre à la fois, par exemple pour effectuer une correction ou un changement de fonte. Mais, au préalable, il faut se mettre en situation de traiter le problème de manière quantique, par exemple en ouvrant le livre et en collant toutes les pages les unes à côté des autres.

La démarche lancée aujourd'hui par Atos, permet, à défaut de disposer d'un ordinateur quantique, de simuler par des ordinateurs classiques le comportement de celui-ci, de façon à se « faire la main », algorithmiquement parlant. Si l'on pouvait à peu de frais simuler le fonctionnement d'un ordinateur quantique, cela signifierait qu'on saurait résoudre à peu de frais des problèmes qui sont du ressort de celui-ci. Tel n'est pas le cas, bien entendu. Les ordinateurs quantiques les plus complexes simulés par Atos comportent quelques dizaines de qubits, ce qui correspond aussi aux meilleurs systèmes qu'on parvient à fabriquer actuellement physiquement.