Portes logiques réversibles conçues pour la factorisation d’entiers à grande échelle
Français
Suivez-nous sur notre page Facebook et notre canal Telegram
Les ordinateurs d’aujourd’hui sont basés sur des microprocesseurs qui exécutent ce qu’on appelle des portes. Une porte peut par exemple être une opération ET, c’est-à-dire une opération qui additionne deux bits. Ces portes, et donc les ordinateurs, sont irréversibles. Autrement dit, les algorithmes ne peuvent pas simplement fonctionner à l’envers. “Si vous prenez la multiplication 2*2=4, vous ne pouvez pas simplement exécuter cette opération en sens inverse, car 4 pourrait être 2*2, mais également 1*4 ou 4*1”, explique Wolfgang Lechner, professeur de physique théorique à Université d’Innsbruck. Si cela était possible, cependant, il serait possible de factoriser de grands nombres, c’est-à-dire de les diviser en leurs facteurs, ce qui est un pilier important de la cryptographie.
Martin Lanthaler, Ben Niehoff et Wolfgang Lechner du Département de physique théorique de l’Université d’Innsbruck et la spin-off quantique ParityQC ont maintenant développé exactement cette inversion d’algorithmes à l’aide d’ordinateurs quantiques. Le point de départ est un circuit logique classique, qui multiplie deux nombres. Si deux nombres entiers sont entrés comme valeur d’entrée, le circuit renvoie leur produit. Un tel circuit est construit à partir d’opérations irréversibles. “Cependant, la logique du circuit peut être encodée dans les états fondamentaux d’un système quantique”, explique Martin Lanthaler de l’équipe de Wolfgang Lechner. “Ainsi, la multiplication et la factorisation peuvent être comprises comme des problèmes d’état fondamental et résolues à l’aide de méthodes d’optimisation quantique.”
Superposition de tous les résultats possibles
“Le cœur de notre travail est l’encodage des éléments de base du circuit multiplicateur, en particulier les portes ET, les additionneurs demi et complets avec l’architecture de parité comme problème d’état fondamental sur un ensemble de spins en interaction”, explique Martin Lanthaler. Le codage permet de construire l’ensemble du circuit à partir de sous-systèmes répétitifs pouvant être disposés sur une grille bidimensionnelle. En enchaînant plusieurs de ces sous-systèmes ensemble, des instances de problème plus importantes peuvent être réalisées. Au lieu de la méthode classique de la force brute, où tous les facteurs possibles sont testés, les méthodes quantiques peuvent accélérer le processus de recherche : pour trouver l’état fondamental, et ainsi résoudre un problème d’optimisation, il n’est pas nécessaire de rechercher l’ensemble du paysage énergétique, mais plus profondément les vallées peuvent être atteintes par “tunneling”.
Les travaux de recherche actuels fournissent un modèle pour un nouveau type d’ordinateur quantique pour résoudre le problème de factorisation, qui est une pierre angulaire de la cryptographie moderne. Ce modèle est basé sur l’architecture de parité développée à l’Université d’Innsbruck et peut être mis en œuvre sur toutes les plates-formes informatiques quantiques actuelles.
Les résultats ont été publiés récemment dans Nature Communication Physique. Le soutien financier pour la recherche a été fourni par le Fonds scientifique autrichien FWF, l’Union européenne et l’Agence autrichienne de promotion de la recherche FFG, entre autres.
