J'ai récemment vu beaucoup plus de battage médiatique autour des ordinateurs quantiques sur X, alors j'ai pensé que je ferais un long post à leur sujet. Résumé exécutif : je ne crois pas que l'informatique quantique arrive de sitôt. Je pense cela parce qu'aucun progrès n'a été réalisé depuis de nombreuses années sur le problème le plus simple pour lequel les ordinateurs quantiques peuvent être utilisés, qui est la factorisation. Le record de factorisation quantique est resté autour du nombre 15 (oui, 15, 3 x 5 !) pendant une décennie maintenant, et aucun progrès évident n'a eu lieu récemment. Mon raisonnement est ci-dessous. Je vais décomposer les choses pour les personnes qui ne connaissent pas beaucoup les mathématiques ou l'informatique, mais cela pourrait quand même effrayer les personnes ayant des phobies des mathématiques. La factorisation de grands nombres est d'un intérêt particulier car plusieurs algorithmes cryptographiques importants dépendent du fait qu'il faut beaucoup de temps pour factoriser un nombre suffisamment grand en ses facteurs premiers en utilisant des ordinateurs conventionnels. Vous pouvez factoriser un petit nombre (disons 21) à la main très rapidement, il suffit d'essayer de le diviser par les nombres en commençant par 2 puis 3, et vous découvrirez rapidement que 21 est 3 x 7. Cependant, cela ne fonctionne pas pour des nombres vraiment grands car l'espace de tous les nombres que vous devriez essayer devient trop grand. Si vous pouviez factoriser des nombres de plus de 1200 chiffres décimaux (pas le nombre 1200, qui a quatre chiffres, mais des nombres avec 1200 chiffres !), vous pourriez casser de nombreux systèmes cryptographiques qui intéressent les gens, mais personne ne sait comment le faire assez rapidement sur un ordinateur normal. (Assez rapidement signifie "avant que toutes les étoiles dans le ciel ne s'éteignent.") Il y a quelques années, Peter Shor a montré que vous pouviez (en théorie du moins) factoriser des nombres très rapidement en utilisant des ordinateurs quantiques. La factorisation utilisant l'algorithme de Shor est, à mon avis, le benchmark le plus évident difficile à falsifier pour l'informatique quantique. En 2016, le nombre 15 (pas un nombre à 15 chiffres, le nombre 15 !) a été pour la première fois factorisé (évidemment en 3 x 5) dans une démonstration propre et non truquée de l'algorithme de Shor. C'est un petit nombre, mais c'était un début. (Il y a un certain débat sur le fait que le nombre 21 a également été factorisé dans une démonstration non truquée de l'algorithme de Shor ou non.) Mais encore une fois, 15 est un nombre à deux chiffres. Nous voulons factoriser des nombres de milliers de chiffres pour pouvoir casser des systèmes cryptographiques. Cependant, depuis 2016, aucun nombre plus grand n'a été factorisé dans des démonstrations propres de l'algorithme de Shor. (Certaines personnes ont affirmé avoir factorisé des nombres plus grands en utilisant l'algorithme de Shor, mais elles ont toujours utilisé des astuces qui nécessitaient qu'elles connaissent déjà les facteurs pour le faire et configurer l'ordinateur quantique avec ce qui revient à une pré-connaissance de la réponse, ce qui n'est vraiment pas le but. Je recherche des démonstrations *non truquées*.) Nous avons attendu longtemps que quelqu'un démontre la factorisation d'un nombre même légèrement plus grand que 15. Vous auriez espéré qu'il y aurait eu des progrès réguliers à ce sujet, avec quelqu'un factorisant (disons) un nombre comme 77 (7 x 11), puis un comme 323 (17 x 19), puis quelque chose de milliers, et ainsi de suite. Cependant, personne n'a démontré une machine capable de faire quoi que ce soit de mieux que le nombre 15 (qu'un enfant peut factoriser dans sa tête en 3 et 5 en quelques instants) et ce record a tenu pendant très longtemps. Donc, sur ce problème au moins, un problème vraiment basique qui est facile à expliquer, il n'y a pas eu de progrès régulier dans l'informatique quantique. Nous avons eu beaucoup de battage médiatique, beaucoup de gens montrant des ordinateurs quantiques prétendument exécutant des algorithmes qui ne sont pas tout à fait des démonstrations aussi clairement propres, mais nous n'avons rien vu depuis longtemps sur la factorisation. Je croirai qu'il y a eu un véritable progrès dans l'informatique quantique lorsque nous commencerons à voir des nombres plus grands factorisés dans des démonstrations propres et non truquées de l'algorithme de Shor. Je croirai que nous avons fait de réels progrès lorsque nous pourrons traiter des nombres à quatre chiffres, c'est-à-dire des nombres de milliers. Même une démonstration de quelque chose qui pourrait faire un nombre à deux chiffres beaucoup plus grand que 15 serait la bienvenue. Cependant, aucune machine capable de faire cela n'est vraiment à l'horizon à court terme. Maintenant, être capable de casser des codes nécessite des machines capables de traiter des nombres avec *des milliers* de chiffres, mais nous n'avons même pas encore de nombres à trois chiffres en vue (ou même la plupart des nombres à deux chiffres). Donc, mon benchmark personnel est de voir même un peu de progrès à ce sujet. Rappelez-moi quand nous aurons des ordinateurs quantiques capables de factoriser (disons) 323 avec succès, dans une démonstration propre et non truquée de l'algorithme de Shor qui pourrait traiter n'importe quel nombre composite de taille similaire. D'ici là, je ne pense pas qu'il se passe grand-chose d'intéressant, du moins pas pour moi.

(Au fait, je ne veux pas donner l'impression que je pense que l'informatique quantique est impossible ou quoi que ce soit. Je dis juste que de mon point de vue, les progrès récents n'ont pas été évidents et nous sommes encore loin de résoudre des problèmes simples comme le factorisation de nombres avec cela.)

Cela dit, cela ne signifie pas non plus que des entreprises comme Google sont folles de poursuivre des recherches pures sur l'informatique quantique. Je pense que cela vaut la peine d'y travailler. Ce n'est tout simplement pas d'application pratique imminente. Il se peut aussi que la NSA ou d'autres organisations similaires aient fait des progrès plus significatifs sur le problème que le monde de la recherche ouverte, mais évidemment, ce n'est pas une information à laquelle j'aurais accès. Enfin, cela ne signifie pas que la recherche sur les algorithmes cryptographiques post-quantiques est une mauvaise idée.

Dans mon post original en haut, j'ai évité de mentionner à quel point les problèmes de mise à l'échelle sont difficiles. Principalement, je me suis concentré sur le fait qu'aucune mise à l'échelle n'a réellement eu lieu. Et pour être sûr, à un moment donné, il est très possible que les choses de correction d'erreur commencent à apparaître. Mais, la mise à l'échelle pour factoriser des nombres sérieux ne va pas se produire le lendemain.

@defendtheworld Donc, encore une fois : je commencerai à croire quand je verrai la technologie évoluer au-delà de la factorisation de 15. Et oui, cela signifie qu'une énorme quantité de travail aura déjà été effectuée, mais cela laissera également une énorme quantité de travail à faire.