Un problème informatique bien connu cherche à trouver l'itinéraire le plus efficace pour qu'un vendeur itinérant rende visite à des clients dans un certain nombre de villes. Apparemment simple, c'est en fait étonnamment complexe et très étudié, avec des implications dans des domaines aussi vastes que la fabrication et le contrôle du trafic aérien.

Des chercheurs de l'Université de Floride centrale et de l'Université de Boston ont développé une nouvelle approche pour résoudre plus rapidement des problèmes de calcul aussi difficiles. Tel que rapporté le 12 mai dans Communication Nature , ils ont découvert un moyen d'appliquer la mécanique statistique, une branche de la physique, pour créer des algorithmes plus efficaces qui peuvent fonctionner sur des ordinateurs traditionnels ou un nouveau type de machine de calcul quantique, a déclaré le professeur Eduardo Mucciolo, président du département de physique du Collège des sciences de l'UCF.

La mécanique statistique a été développée pour étudier les solides, gaz et liquides aux échelles macroscopiques, mais est maintenant utilisé pour décrire une variété d'états complexes de la matière, du magnétisme à la supraconductivité. Des méthodes dérivées de la mécanique statistique ont également été appliquées pour comprendre les modèles de trafic, le comportement des réseaux de neurones, avalanches de sable et fluctuations boursières.

Il existe déjà des algorithmes efficaces basés sur la mécanique statistique qui sont utilisés pour résoudre des problèmes de calcul. De tels algorithmes mappent les problèmes sur un modèle de variables binaires sur les nœuds d'un graphe, et la solution est codée sur la configuration du modèle avec la plus faible énergie. En construisant le modèle dans le matériel ou une simulation informatique, les chercheurs peuvent refroidir le système jusqu'à ce qu'il atteigne sa plus faible énergie, révélant la solution.

"Le problème avec cette approche est qu'il faut souvent passer par des transitions de phase similaires à celles trouvées lors du passage d'une phase liquide à une phase vitreuse, où existent de nombreuses configurations concurrentes à basse énergie, " a déclaré Mucciolo. " De telles transitions de phase ralentissent considérablement le processus de refroidissement, rendant la méthode inutile."

Mucciolo et ses collègues physiciens Claudio Chamon et Andrei Ruckenstein de BU ont surmonté cet obstacle en mappant le problème de calcul original sur un modèle statistique élégant sans transitions de phase, qu'ils ont appelé le modèle de sommet. Le modèle est défini sur un réseau à deux dimensions et chaque sommet correspond à une porte logique réversible connectée à quatre voisins. Les données d'entrée et de sortie se situent aux limites du réseau. L'utilisation de portes logiques réversibles et la régularité du réseau ont été des ingrédients cruciaux pour éviter le problème de transition de phase, dit Mucciolo.

"Notre méthode exécute essentiellement les choses à l'envers afin que nous puissions résoudre ces problèmes très difficiles, " dit Mucciolo. " Nous attribuons à chacune de ces portes logiques une énergie. Nous l'avons configuré de telle sorte qu'à chaque fois que ces portes logiques sont satisfaites, l'énergie est très faible - donc, quand tout est satisfait, l'énergie globale du système devrait être très faible."

Chamon, un professeur de physique à la BU et le chef d'équipe, a déclaré que la recherche représente une nouvelle façon de penser au problème.

"Ce modèle ne présente aucune transition de phase thermodynamique en vrac, ainsi l'un des obstacles pour atteindre les solutions présentes dans les modèles précédents a été éliminé, " il a dit.

Le modèle de vertex peut aider à résoudre des problèmes complexes en apprentissage automatique, optimisation des circuits, et d'autres défis informatiques majeurs. Les chercheurs étudient également si le modèle peut être appliqué à la factorisation des semi-premiers, nombres qui sont le produit de deux nombres premiers. La difficulté d'effectuer cette opération avec de très grands semi-premiers sous-tend la cryptographie moderne et a offert une justification clé pour la création d'ordinateurs quantiques à grande échelle.

De plus, le modèle peut être généralisé pour ajouter une autre voie vers la solution de problèmes de calcul classiques complexes en tirant parti du parallélisme de la mécanique quantique - le fait que, selon la mécanique quantique, un système peut être dans plusieurs états classiques en même temps.

"Notre article présente également un cadre naturel pour la programmation de dispositifs de calcul à usage spécial, tels que les machines D-Wave Systems, qui utilisent la mécanique quantique pour accélérer le temps de résolution des problèmes de calcul classiques, " dit Ruckenstein.

Zhi-Cheng Yang, un étudiant diplômé en physique à la BU, est également co-auteur de l'article. Les universités ont déposé une demande de brevet sur certains aspects du modèle vertex.