En pratique, de nombreux programmes conçus pour les ordinateurs classiques ne peuvent pas être exécutés sur des ordinateurs quantiques car ils ne peuvent pas oublier sélectivement les informations. Le nouvel algorithme de multiplication montre comment contourner ce problème.
Les bits classiques sont en noir et blanc et les bits quantiques sont un peu plus compliquésQuand j'avais 9 ans, mes parents ont acheté un nouvel ordinateur. À presque tous les égards, il était meilleur que l'ancien, sauf un: mes courses préférées n'y ont pas commencé. Je me souviens de ce que je pensais - pourquoi ai-je besoin d'un ordinateur dernier cri s'il ne démarre pas mon programme préféré?
Les ordinateurs quantiques ont le même problème. En théorie, ils sont capables de tout ce dont le classique est capable. Dans la pratique, leur nature quantique rend presque impossible l'exécution de certains des algorithmes classiques les plus importants.
C'est pourquoi l'
ouvrage , publié le 15 avril, contient de bonnes nouvelles.
Craig Gidney , un informaticien de Google AI Quantum à Santa Barbara, en Californie, décrit une version quantique de l'algorithme classique pour multiplier rapidement de très grands nombres. Sur les ordinateurs classiques, cet algorithme fonctionne depuis un certain temps. Mais avant le travail de Gidney, il n'était pas clair s'il serait possible de l'adapter aux machines quantiques.
Plus important encore, l'algorithme de multiplication appartient à la classe des algorithmes informatiques omniprésents. Gidney pense que sa nouvelle technique permettra aux ordinateurs quantiques de mettre en œuvre toute la classe de ces algorithmes, qui jusqu'à présent ont été considérés comme trop lourds à utiliser dans une machine quantique.
Cet algorithme de multiplication profite de la découverte, qui a été la première percée dans la multiplication réalisée sur plusieurs milliers d'années. La méthode traditionnelle de multiplication à l'école nécessite n
2 étapes, où n est le nombre de caractères dans les nombres multipliés. Pendant plusieurs milliers d'années, les mathématiciens ont cru qu'il n'existait pas d'approche plus efficace.
Mais, comme nous l'avons récemment précisé dans l'article «Les
mathématiciens ont découvert le moyen idéal de multiplier les nombres », en 1960, le mathématicien soviétique Anatoly Karatsuba a découvert un moyen plus rapide. Sa méthode consistait à diviser les nombres longs en nombres plus courts. Pour multiplier deux nombres à huit chiffres, par exemple, vous devez d'abord les diviser en deux nombres à quatre chiffres, puis diviser chacun d'eux en deux nombres à deux chiffres. Ensuite, vous devez effectuer plusieurs opérations avec des nombres à deux chiffres et restaurer le résultat de la multiplication finale. Pour multiplier de très grands nombres, la méthode Karatsuba prend beaucoup moins de mesures que la méthode scolaire.
Lorsqu'un ordinateur classique fonctionne sur l'algorithme de Karatsuba, il supprime les informations du processus. Par exemple, en rétablissant les nombres à deux chiffres en quatre chiffres, il oublie les nombres à deux chiffres. Maintenant, il ne s'intéresse qu'aux nombres à quatre chiffres. La version classique de l'algorithme est similaire à un grimpeur jetant son équipement en montant - il peut se déplacer plus rapidement s'il ne transporte pas tous les déchets avec lui.
Mais les ordinateurs quantiques ne peuvent pas éliminer les informations.
Les ordinateurs quantiques effectuent des calculs par le biais de manipulations avec des bits quantiques, ou «qubits». Ils sont entrelacés ou confus. Cette confusion donne aux ordinateurs quantiques d'énormes opportunités - au lieu de stocker des informations dans des bits séparés, les ordinateurs quantiques utilisent des interactions complexes de tous les qubits. En conséquence, pour certaines tâches, les ordinateurs quantiques sont en mesure de démontrer une puissance de calcul exponentiellement supérieure à celle des ordinateurs classiques.
Cependant, la même propriété qui rend les ordinateurs quantiques si puissants les rend également fragiles. Étant donné que les qubits sont enchevêtrés, il est impossible de changer certains d'entre eux sans affecter tout le monde. Cela rend impossible la suppression sélective des informations disponibles sur les ordinateurs classiques. Faire tomber les qubits, c'est comme couper des parties d'une bande - même une seule coupe peut détruire la bande entière.
Cette exigence de conservation de l'information complique la création de versions quantiques d'algorithmes récursifs, c'est-à-dire se tournant vers elles-mêmes. En informatique, les algorithmes récursifs sont très largement utilisés, mais pour fonctionner au mieux, ils ont besoin de l'ordinateur pour éliminer les informations à chaque étape. Sans cela, l'informatique deviendra rapidement impossible. "Si vous enregistrez des informations chaque fois que vous effectuez une opération, l'espace qu'elle occupe augmentera avec le nombre d'opérations", a déclaré
Ashley Montanaro , spécialiste de l'information quantique à l'Université de Bristol. Toute machine pratique manquera rapidement de mémoire.
Dans un nouveau travail, Gidney décrit une méthode quantique pour implémenter la multiplication de Karatsuba, qui ne nécessite pas une grande consommation de mémoire. Au lieu de générer des valeurs intermédiaires pour obtenir le résultat final, il utilise la méthode "
optimisation de la récursivité de queue " pour transformer directement l'entrée en sortie. Cela permet à l'algorithme d'éviter de créer des informations intermédiaires qu'un ordinateur quantique ne peut pas rejeter. "Il se débarrasse du problème des qubits supplémentaires sans générer de qubits supplémentaires", a déclaré
Thomas Vaughn , spécialiste de l'information quantique à l'Université Creiton.
Gidney pense que sa méthode fonctionnera pour adapter de nombreux algorithmes récursifs classiques aux ordinateurs quantiques. Jusqu'à présent, les ordinateurs quantiques sont à un stade si précoce qu'ils peuvent à peine faire face à la multiplication de chiffres uniques. Cependant, l'algorithme est prêt, et lorsque leurs schémas seront améliorés, ils deviendront capables de bien plus.