Trente ans plus tard, l'affacturage quantique gagne en vitesse

L'algorithme de Shor permettra aux futurs ordinateurs quantiques de factoriser rapidement de grands nombres, compromettant ainsi de nombreux protocoles de sécurité en ligne. Un chercheur a désormais démontré comment y parvenir encore plus rapidement.

L'algorithme de Peter Shor est une méthode quantique permettant de factoriser rapidement de grands nombres. Cet algorithme, développé dans les années 1990 menace la cryptographie à clé publique utilisée pour la sécurité sur Internet.

La nouvelle avancée d'Oded Regev

Oded Regev, un informaticien de l'Université de New York, a développé une nouvelle variante de l'algorithme de Shor qui améliore la relation entre la taille du nombre à factoriser et le nombre d'opérations quantiques nécessaires. C'est la première fois qu'une telle amélioration est réalisée depuis la découverte de l'algorithme original.

Regev a combiné l'algorithme de Shor avec des techniques de cryptographie basée sur les réseaux (lattices), qui traitent de la géométrie de haute dimension.

Fonctionnement de l'algorithme de Regev

L'algorithme de Regev généralise la fonction périodique au cœur de l'algorithme de Shor en utilisant plusieurs dimensions. Au lieu de multiplier un seul grand nombre plusieurs fois, il multiplie des paires de petits nombres ensemble, puis multiplie les résultats entre eux. Cela réduit considérablement le nombre de multiplications de grands nombres nécessaires, ce qui accélère le calcul quantique.

Implications et défis

Bien que l'algorithme de Regev accélère la partie quantique du calcul, il nécessite plus de qubits (bits quantiques) que l'algorithme de Shor original. Les qubits sont fragiles et sujets aux erreurs, ce qui rend la gestion d'un grand nombre de qubits difficile.

Cependant, des travaux récents ont permis de réduire le nombre de qubits requis par l'algorithme de Regev, le rendant plus proche d'une implémentation pratique.

Il faut souligner que l'amélioration de l'algorithme de Shor par Regev montre qu'il est toujours possible de faire des découvertes surprenantes dans le domaine de l'informatique quantique, même sur des problèmes étudiés depuis des décennies. Il reste encore beaucoup d'algorithmes quantiques à découvrir.

Accélération quantique découverte pour une vaste classe de problèmes difficiles

Il a toujours été difficile de trouver des questions importantes auxquelles les ordinateurs quantiques peuvent répondre plus rapidement que les machines classiques, mais un nouvel algorithme semble le faire pour certaines tâches d'optimisation critiques.

Les chercheurs en informatique quantique ont développé un nouvel algorithme, Decoded Quantum Interferometry (DQI), capable de résoudre une vaste classe de problèmes d'optimisation plus rapidement que toutes les méthodes classiques connues. Cette avancée marque une rupture dans la compétition entre approches quantiques et classiques, où les avantages quantiques restaient jusqu'ici éphémères ou contestés.

Fonctionnement clé de DQI

Inspiration et méthode

1 Traduction quantique :

- Les solutions potentielles sont converties en ondes quantiques via une transformée de Fourier quantique.

- Les meilleures solutions correspondent aux amplitudes quantiques les plus élevées.

2 Intégration de techniques de décodage :

L'algorithme s'appuie sur des méthodes de correction d'erreurs (décodage) issues de la cryptographie, initialement conçues pour identifier et corriger des messages bruités.

3 Optimisation par interférences :

Les interférences constructives/destructrices des ondes quantiques amplifient les bonnes solutions tout en atténuant les mauvaises.

Avantages par rapport aux méthodes classiques

Aspect                         Approche classique                     DQI (Quantique)

Complexité                  Sous-exponentielle                      Polynomiale

Exploration                  Séquentielle                                 Parallèle 

                                    (méthodes heuristiques)              (superposition quantique)

Applications clés          Cryptographie, logistique            Cryptographie post-quantique, correction d'erreurs

Validations et limites

Vérifications : 

- L'équipe a collaboré avec Mary Wootters (experte en théorie des codes) pour exclure l'existence d'un équivalent classique efficace.

- Extension réussie à une classe étendue de problèmes d'optimisation (ex. : chemins optimaux).

Défis persistants :

- Matériel quantique insuffisant : Aucun ordinateur quantique actuel ne peut exécuter DQI en raison du nombre élevé de qubits requis.

- Risque de "déquantisation" : Possibilité qu'un algorithme classique égalisant DQI soit découvert ultérieurement.

Implications et réactions

Impact scientifique

Cryptographie : Menace accrue sur les systèmes RSA actuels, accélérant la transition vers des standards post-quantiques.

Théorie de l'information : Nouveaux outils pour l'encodage résilient aux erreurs dans les communications quantiques.

Réactions de la communauté

Gil Kalai (sceptique historique) : Qualifie DQI de "percée", soulignant sa rareté dans le domaine.

Ronald de Wolf (CWI) : Optimiste mais prudent, rappelant que la supériorité quantique reste à prouver empiriquement.

Ewin Tang (UC Berkeley) : Encourage les chercheurs classiques à étudier DQI pour inspirer de nouveaux algorithmes.

Perspectives

Bien que théorique, DQI ouvre des pistes pour :

- Concevoir des algorithmes hybrides (quantique-classique) exploitables sur les ordinateurs NISQ actuels.

- Repenser l'optimisation dans des domaines comme la logistique ou la chimie quantique.

- Stimuler l'innovation matérielle en identifiant des cas d'usage concrets pour les futurs qubits topologiques ou photoniques.

Conclusion : DQI représente une avancée majeure vers des avantages quantiques incontestables, tout en illustrant la nécessité de collaborations interdisciplinaires (physique, théorie des codes, IA) pour matérialiser le potentiel quantique.