On attend avec impatience l’arrivée des ordinateurs quantiques, et surtout le moment où ils achèveront la suprématie quantique, c’est-à-dire quand ils seront capables d’exécuter des tâches inaccessibles aux ordinateurs classiques.

Pour des tas de raisons, il y a encore beaucoup de travail : combat contre la décohérence, correction des erreurs, mais aussi l’incapacité de ces nouvelles machines à réaliser certains algorithmes parfaitement utilisables par leurs équivalents classiques. C’est le cas de certains procédés de multiplication.

On a beaucoup parlé il y a quelques semaines d’un nouveau moyen d’effectuer cette opération connue de tous, surtout lorsqu’elle implique des grands nombres. En fait cette dernière recherche est basée sur des travaux initiés dès les années 60 par le mathématicien russe Anatoly Karatsuba. La technique de Karatsuba est bien connue, souvent utilisée au sein des machines classiques. Elle consiste essentiellement à diviser les grands nombres en de plus petits. Comme l’explique le magazine Quanta : « Pour multiplier deux nombres à huit chiffres, par exemple, vous devez d’abord diviser chacun en deux nombres à quatre chiffres, puis encore chacun de ces nombres en deux. Vous effectuez ensuite des opérations sur tous les nombres à deux chiffres et reconstituez les résultats pour obtenir le produit final. »

Tout cela est bel et bon, mais alors où est le problème ? C’est qu’il existe des résultats intermédiaires. Lorsque l’ordinateur classique en a fini avec les nombres à deux chiffres, il s’en débarrasse pour se concentrer sur les nombres à quatre chiffres.

Or c’est une loi fondamentale de l’informatique quantique : le calcul doit être totalement réversible, c’est-à-dire qu’il doit toujours être possible de reconstituer le calcul en question (par exemple, 3+7 = 10 n’est pas réversible si vous récupérez juste le résultat. Le 10 peut avoir été obtenu d’une infinité de façons, par exemple 8+2 ou 1258-1248). Si l’on voulait implémenter la méthode Karatsuba avec une machine quantique, cela impliquerait de garder tous les intermédiaires en mémoire, ce qui aurait un coût gigantesque.

Mais un récent algorithme été découvert par Craig Gidney(@CraigGidney), un ingénieur de la division d’informatique quantique de Google, nous explique Quanta. Ce dernier a publié ses résultats le 15 avril dernier dans ArXiv. Sa méthode, sans entrer dans lés détails mathématiques, permet d’éviter l’accumulation de résultats intermédiaires. Les inputs, nous dit l’article de Quanta, se transforment directement en output.

Certes, conclut le magazine, pour l’instant les ordinateurs quantiques sont incapables d’aller plus loin que multiplier des nombres à un chiffre. Mais lorsqu’ils seront plus puissants (si jamais cela arrive un jour) alors l’algorithme est déjà prêt…

Image : la méthode de calcul Katsuba d’une multiplication de grands nombres, via Quanta Magazine.