Le premier avantage quantique exponentiel pour un problème de streaming naturel

Comme le lièvre l’a appris de la tortue, la vitesse n’est pas tout. Des informaticiens théoriques des laboratoires nationaux Sandia et de l’université de Boston ont découvert que les ordinateurs quantiques sont sans égal pour résoudre un problème mathématique complexe. Fait inhabituel, ils ont prouvé que les ordinateurs quantiques ne sont pas plus rapides que les ordinateurs classiques ; au contraire, ils utilisent beaucoup moins de mémoire.

Cette découverte bouleverse l’idée reçue selon laquelle la valeur d’un ordinateur quantique réside dans sa capacité à résoudre certains problèmes beaucoup plus rapidement qu’un ordinateur normal. Elle pourrait également aider les chercheurs à trouver des applications plus concrètes à cette technologie en pleine évolution.

« C’est le premier avantage quantique exponentiel pour un problème de streaming naturel », a déclaré Ojas Parekh de Sandia, membre de l’équipe.

La mémoire est un élément important pour tout ordinateur. Plus il y a de mémoire, plus les problèmes qu’il peut résoudre sont importants. Pour les ordinateurs quantiques, qui stockent les informations dans des qubits, « l’espace est vraiment important car il est difficile de construire des ordinateurs quantiques avec beaucoup de qubits », a déclaré Parekh.

L’équipe a présenté ses résultats lors du Symposium sur la théorie de l’informatique, qui s’est tenu du 24 au 28 juin à Vancouver, en Colombie-Britannique. La preuve mathématique est disponible sur le site arXiv serveur de préimpression.

La valeur des ordinateurs quantiques pourrait résider dans l’efficacité de la mémoire, et pas seulement dans la vitesse

En 1994, le scientifique américain Peter Shor a surpris le monde en prouvant que les futurs ordinateurs quantiques seraient capables de déchiffrer les algorithmes de chiffrement standard à une vitesse alarmante. Au cours des 30 années qui ont suivi, les chercheurs n’ont cependant découvert qu’une poignée d’autres problèmes que ces ordinateurs peuvent résoudre plus rapidement que les ordinateurs normaux.

Les recherches menées par Sandia et l’Université de Boston pointent désormais vers un autre domaine où l’avantage quantique est possible.

« La recherche sur les avantages quantiques a principalement porté sur l’obtention d’un avantage temporel », a déclaré Nadezhda Voronova, doctorante au département d’informatique de l’université de Boston. « Les recherches sur les avantages quantiques par rapport à d’autres ressources, comme la mémoire, ont été relativement limitées. »

En portant l’attention sur ces autres attributs, comme l’efficacité, les scientifiques pourraient trouver des utilisations plus pratiques pour les ordinateurs quantiques.

« Passons-nous actuellement à côté d’avantages quantiques importants parce que nous nous concentrons ou sommes biaisés sur certains types de problèmes ? » a déclaré Parekh.

Qu’est-ce qu’un problème de streaming naturel et pourquoi est-ce important ?

Le problème mathématique au centre de l’affirmation de l’équipe, appelé coupure dirigée maximale, est important car il s’agit de ce que les chercheurs appellent un problème naturel.

« Lorsque nous parlons d’un problème naturel », a déclaré John Kallaugher de Sandia, « ce que nous voulons dire, c’est qu’il s’agit d’un problème d’intérêt indépendant, que les gens l’étudiaient déjà dans le cadre classique. »

Parekh a ensuite expliqué : « Le problème de la coupure maximale dirigée revient à trouver les deux groupes d’agents d’un réseau avec le plus de communication dirigée d’un groupe à l’autre. Ce problème trouve des applications dans la cybersécurité et l’analyse et la conception de réseaux sociaux. »

Les ordinateurs ont généralement besoin de beaucoup plus de mémoire à mesure que ce type de problème devient plus complexe. Mais ce n’est pas le cas des ordinateurs quantiques, a constaté l’équipe. Ils utilisent la mémoire de manière exponentiellement plus efficace, du moins lorsque les données arrivent sous forme de flux. Les calculs en flux sont utiles lorsque les ensembles de données sont trop volumineux pour tenir dans la mémoire d’un ordinateur ou lorsque les données sont créées en continu.

Kallaugher avait déjà publié un article selon lequel les ordinateurs quantiques pourraient présenter un avantage distinct, mais moindre, que celui que lui et son équipe ont prouvé jusqu’à présent. La nouvelle découverte d’un rapport exponentiel est importante, car un avantage doit être très important pour justifier le temps et l’argent nécessaires à la construction et au fonctionnement d’un ordinateur quantique.

Comme l’algorithme de Shor, la nouvelle découverte est encore théorique car elle n’a pas encore été démontrée sur ordinateur.

Une découverte laisse entrevoir les futurs rôles de l’informatique quantique

La coupure maximale dirigée n’est pas très utile en soi. Cependant, il s’agit d’un problème d’optimisation bien connu en mathématiques avancées, que l’équipe de recherche considère comme un indice des types d’utilisations pratiques que les ordinateurs quantiques pourraient avoir à l’avenir.

« En matière de cybersécurité, par exemple, la résolution efficace des problèmes d’optimisation pourrait conduire à une meilleure allocation des ressources, à des stratégies de réponse aux incidents améliorées et à des évaluations des risques plus précises », a déclaré Voronova.

Kallaugher a ajouté : « Cela pourrait ouvrir la voie à des algorithmes capables de gérer des problèmes trop importants pour être traités par un ordinateur classique. »

« Il pourrait y avoir davantage d’algorithmes comme celui-ci », a spéculé Voronova.

« Personne n’a vraiment une vue d’ensemble de la situation », a déclaré Parekh.