← Derniers articles
⚛️ physique quantique

Formally verified harness for Shor's order finding algorithm with O(n2+ϵ)O(n^{2+\epsilon}) gate cost

Cet article présente un harnais formellement vérifié qui ingère des politiques de conception de circuits récursifs provenant de sources externes, telles que des agents d'IA, afin de générer automatiquement des preuves vérifiées par machine de la correction mathématique et d'une complexité de coût de portes en O(n2+ϵ)O(n^{2+\epsilon}) pour l'algorithme de recherche d'ordre de Shor, permettant ainsi un défi ouvert pour la découverte de circuits de factorisation quantique plus efficaces avec une correction garantie.

Auteur original : Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

Publié 2026-11-17
📖 9 min de lecture🧠 Analyse approfondie

Auteur original : Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par l'auteur. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans le paysage de l'informatique moderne, il existe une tension fondamentale entre la vitesse de calcul et la sécurité des secrets. Depuis des décennies, la sécurité des communications numériques repose sur un verrou mathématique : la difficulté de décomposer un grand nombre en ses deux blocs de construction premiers. Si les ordinateurs classiques peinent face à cette tâche, mettant des milliers d'années pour casser un seul code, une machine théorique construite sur les lois de la physique quantique pourrait la résoudre en une fraction de seconde. Cette menace potentielle a poussé les scientifiques à affiner le plan de conception d'une telle machine, plus précisément un algorithme connu sous le nom d'algorithme de Shor. Le défi n'a jamais été de savoir si l'algorithme fonctionne en théorie, mais comment construire la machinerie physique pour l'exécuter efficacement. Le goulot d'étranglement réside dans l'arithmétique : les étapes spécifiques requises pour multiplier et diviser les nombres au sein du système quantique. Pendant des années, les méthodes les plus efficaces connues pour ces étapes nécessitaient un nombre d'opérations qui augmentait si rapidement avec la taille du nombre que même les ordinateurs futurs les plus puissants pourraient ne pas disposer des ressources nécessaires pour accomplir la tâche.

Une équipe de chercheurs a introduit un nouveau cadre conçu pour naviguer dans cet espace de conception complexe, offrant un moyen de trouver des circuits plus rapides et plus efficaces tout en garantissant que les mathématiques restent correctes. Ils ont nommé leur création ForShor, un harnais formellement vérifié qui agit à la fois comme un arbitre et un bâtisseur. Au lieu de demander aux scientifiques de construire manuellement chaque variation possible du circuit quantique — une tâche sujette à l'erreur humaine et impossible à vérifier minutieusement — ils ont construit un système où les chercheurs peuvent soumettre un ensemble de règles, ou une « politique », qui décrit comment la multiplication doit être décomposée. Le système vérifie ensuite automatiquement ces règles par rapport à une norme mathématique rigoureuse. Si les règles passent ce test, le système génère un programme quantique complet et vérifié, et calcule exactement combien de composants physiques, appelés portes, seraient nécessaires pour l'exécuter. Cette approche permet une recherche ouverte de meilleurs designs, où les experts humains et les agents d'intelligence artificielle peuvent rivaliser pour trouver le chemin le plus efficace, tout en garantissant que le circuit résultant est mathématiquement sain et prêt pour une estimation réelle des ressources.

Le cœur du problème réside dans la manière dont l'algorithme gère la multiplication. Pour factoriser un grand nombre, l'ordinateur quantique doit effectuer une série massive de multiplications. Les chercheurs se sont concentrés sur une technique spécifique appelée multiplication récursive de Toom-Cook, qui fonctionne comme une forme sophistiquée de division longue. Au lieu de multiplier directement deux grands nombres, la méthode les divise en morceaux plus petits, multiplie ces morceaux, puis recombine les résultats. L'efficacité de ce processus dépend entièrement de la manière dont les morceaux sont divisés et de la manière dont les résultats sont réassemblés. Il existe d'innombrables façons d'organiser ces étapes, créant un vaste espace de conception. Les chercheurs ont découvert que, bien qu'une méthode mathématique exacte existe pour trouver le meilleur arrangement absolu, elle est informatiquement impossible à exécuter pour les tailles de nombres utilisées dans la cryptographie moderne. Le nombre de possibilités est si élevé que même avec les supercalculateurs les plus rapides, vérifier chaque option prendrait plus longtemps que l'âge de l'univers.

Pour résoudre cela, l'équipe a créé un système qui sépare le travail créatif de conception du circuit du travail fastidieux de sa vérification. Un participant à leur défi soumet une « politique », qui est essentiellement un ensemble d'instructions indiquant à l'ordinateur comment diviser les nombres et quelles opérations effectuer à chaque étape. Le système vérifie ensuite si ces instructions respectent un ensemble strict de règles logiques. Ces règles garantissent que les étapes sont réversibles, qu'aucune information n'est perdue et que le résultat final est mathématiquement équivalent à la multiplication prévue. Si la politique passe ce contrôle, le système construit automatiquement le circuit quantique complet et calcule son coût en ressources. Ce processus est formalisé de manière à ne laisser aucune place au doute ; le système prouve que toute politique valide produira un résultat correct, quel que soit le concepteur ou la complexité du design.

Les résultats de cette approche sont significatifs. En permettant la recherche de meilleurs designs sans la crainte d'introduire des erreurs, les chercheurs ont démontré qu'il est possible de réduire le nombre d'opérations requises pour l'algorithme de Shor. Leur analyse montre qu'avec les bons choix de conception, le nombre d'opérations peut croître beaucoup plus lentement que prévu, passant d'un taux de croissance cubique à quelque chose de plus proche d'un taux quadratique. Cela signifie que pour de très grands nombres, la nouvelle méthode pourrait nécessiter beaucoup moins de ressources que les approches standards. Cependant, les chercheurs prennent soin de noter que, bien que les améliorations théoriques soient substantielles, les meilleurs designs actuels nécessitent encore un nombre de composants physiques qui dépasse de loin les capacités de la technologie d'aujourd'hui. Pour un nombre aussi grand que ceux utilisés dans le chiffrement actuel, le système estime que le design le plus efficace connu nécessiterait tout de même plus d'un billion d'opérations spécifiques, appelées portes T.

Le projet met également en lumière une nouvelle façon de faire de la science à l'ère de l'intelligence artificielle. Le cadre est conçu comme un défi ouvert, invitant les chercheurs humains et les agents d'IA à soumettre leurs propres designs. Le système agit comme un juge neutre, acceptant toute soumission répondant aux critères mathématiques et rejetant celles qui ne les respectent pas. Cela crée un environnement sûr pour l'innovation, où le risque d'un design défectueux est éliminé par la vérification contrôlée par la machine. Les chercheurs ont constaté que, même au sein d'un ensemble restreint de choix de conception, trouver la solution optimale est incroyablement difficile. Ils ont testé leur système avec un exemple spécifique impliquant un nombre de 2048 bits, une taille couramment utilisée dans le chiffrement. Le système a confirmé que, bien qu'une solution exacte optimale existe en théorie, la trouver par force brute est impossible. Au lieu de cela, le système permet des recherches heuristiques, où des agents intelligents peuvent explorer l'espace de conception et proposer de meilleures solutions qui sont ensuite instantanément vérifiées.

L'une des découvertes clés est que l'efficacité de l'algorithme dépend fortement de la taille du nombre à factoriser. Les chercheurs ont découvert que la meilleure façon de diviser les nombres change à mesure que les nombres deviennent plus grands. Un design qui fonctionne bien pour un petit nombre pourrait être inefficace pour un nombre plus grand. Leur système peut gérer cela en permettant différentes stratégies de division à différentes étapes du calcul. Cette flexibilité est cruciale pour repousser les limites du possible. L'équipe a comparé ses résultats avec les méthodes précédentes et a constaté que son approche offre un avantage clair en termes de nombre d'opérations requises, mais seulement pour des nombres nettement plus grands que ceux actuellement en usage. Pour les nombres standards de 2048 bits, l'amélioration est présente mais pas encore assez importante pour rendre la tâche réalisable avec la technologie actuelle.

Le travail fait également le pont entre les preuves mathématiques abstraites et l'ingénierie pratique. Le système prend la description mathématique vérifiée du circuit et la traduit dans un format qui peut être utilisé par des outils logiciels conçus pour estimer les ressources physiques nécessaires. Cette traduction est une étape critique, car elle permet aux chercheurs de voir exactement combien de qubits, ou bits quantiques, et combien de composants de correction d'erreurs seraient nécessaires pour exécuter l'algorithme sur une véritable machine. Les chercheurs ont utilisé ce pipeline pour générer des estimations détaillées pour divers scénarios, confirmant que les améliorations théoriques tiennent bon lorsqu'elles sont traduites en comptes de ressources concrets. Ils ont constaté que le nombre d'opérations croît de manière prévisible, suivant les modèles mathématiques qu'ils ont prouvés.

Malgré les progrès, les chercheurs reconnaissent qu'il reste encore beaucoup de travail à accomplir. Les estimations actuelles sont basées sur des modèles idéalisés de l'ordinateur quantique, et le matériel réel introduira des défis supplémentaires, tels que le bruit et la nécessité de la correction d'erreurs. Le système ne tient pas encore compte de la disposition physique de la machine ni du temps nécessaire pour déplacer l'information entre les différentes parties du processeur. Ce sont les prochaines frontières du domaine. Cependant, la capacité de vérifier formellement la correction de l'algorithme tout en cherchant simultanément le design le plus efficace est un pas en avant majeur. Elle fournit une base solide sur laquelle des améliorations futures peuvent être construites, garantissant que chaque nouvelle idée est testée selon les normes les plus élevées de la rigueur mathématique.

Le projet sert de preuve de concept pour une nouvelle ère de l'ingénierie logicielle quantique. En combinant la vérification formelle avec la recherche ouverte et automatisée, les chercheurs ont créé un outil capable de gérer la complexité des algorithmes quantiques d'une manière qui était auparavant impossible. Cette approche non seulement accélère la recherche de meilleurs algorithmes, mais renforce également la confiance dans les résultats, car chaque affirmation est appuyée par une preuve vérifiée par machine. À mesure que le domaine de l'informatique quantique évolue, des outils comme celui-ci seront essentiels pour naviguer dans le vaste espace de conception et transformer les possibilités théoriques en réalités pratiques. Les chercheurs ont rendu leur cadre public, invitant la communauté mondiale à contribuer à la recherche du moyen le plus efficace de factoriser de grands nombres, une tâche qui demeure l'un des défis les plus importants du domaine.

Noyé(e) sous les articles dans votre domaine ?

Recevez des digests quotidiens des articles les plus récents correspondant à vos mots-clés de recherche — avec des résumés techniques, dans votre langue.

Essayer Digest →