Une représentante a hâte de rentrer chez elle pour voir sa famille, mais elle doit d’abord terminer son circuit de visites professionnelles.

Elle pourrait compléter ce circuit beaucoup plus rapidement si Xiu-Zhe (Roger) Luo, doctorant à l’Institut Périmètre et à l’Université de Waterloo, atteignait son objectif d’écrire des algorithmes qui accéléreront les ordinateurs quantiques.

La représentante n’est évidemment pas une personne réelle, mais un personnage mathématique dans ce que l’on appelle un problème d’optimisation combinatoire, problème bien réel à notre ère du commerce électronique.

Dans l’exemple de la représentante, celle-ci doit trouver le trajet le plus rapide pour aller dans un grand nombre de villes, sans passer 2 fois par la même ville. Une classe similaire de problèmes consiste à trouver la manière optimale de mettre dans un sac à dos ou une boîte un grand nombre d’objets de différentes formes, tailles, valeurs ou utilités, sans dépasser un certain poids ou une certaine limite de charge.

Presque tous les domaines du commerce — y compris la logistique des livraisons, les réseaux de télécommunications, la conception d’automobiles ou d’avions, les transactions financières et la gestion de portefeuille — font face à des problèmes d’optimisation. Partout, on veut créer des produits et services plus efficaces, plus rentables et mieux adaptés.

L’ennui, c’est que les problèmes d’optimisation sont difficiles à résoudre.

Beaucoup de problèmes d’optimisation peuvent être ramenés à ce que l’on appelle en théorie des graphes le problème de l’ensemble indépendant maximal : l’ordinateur doit trouver dans un graphe l’ensemble indépendant comptant le plus d’éléments possible, un ensemble indépendant étant tel que 2 sommets ne sont jamais adjacents.

Lorsqu’il y a de nombreuses configurations possible, il n’y a pas de moyen facile d’obtenir la meilleure solution sans examiner toutes les possibilités. C’est un travail long et fastidieux, même pour un ordinateur quantique.

C’est pourquoi, dans le monde entier, les spécialistes de l’informatique quantique tentent de concevoir des algorithmes pouvant accélérer ce travail. C’est là qu’interviennent les recherches de doctorat de M. Luo pour comprendre la physique qui sous-tend des algorithmes quantiques.

M. Luo fait partie du Laboratoire d’intelligence quantique de l’Institut Périmètre (en abrégé PIQuIL pour Perimeter Institute Quantum Intelligence Lab), centre de recherche et pôle de formation que dirige Roger Melko — professeur associé à l’Institut Périmètre et professeur à l’Université de Waterloo, ainsi que directeur de thèse de M. Luo.

M. Luo a terminé récemment un stage chez QuEra Computing, entreprise située à Boston, près de l’Université Harvard. Il a fait partie d’une équipe de scientifiques de QuEra, de Harvard, du MIT, de l’Université d’Innsbruck et d’autres institutions, qui a réussi à l’aide du calcul quantique une résolution plus rapide du problème de l’ensemble indépendant maximal.

Un article portant sur ces travaux, intitulé Quantum optimization of maximum independent set using Rydberg atom arrays (Optimisation quantique de l’ensemble indépendant maximal à l’aide de réseaux d’atomes de Rydberg) et dont M. Luo est l’un des auteurs, a été récemment publié dans la revue Science. Ces travaux ont été dirigés conjointement par : Mikhail Lukin, professeur George-Vasmer-Leverett de physique à l’Université Harvard et codirecteur de l’Initiative quantique de Harvard; Markus Greiner, également professeur George-Vasmer-Leverett de physique à l’Université Harvard; Vladan Vuletic, professeur Lester-Wolfe de physique au MIT.

Un objectif important de la recherche en informatique quantique est de comprendre quels problèmes les ordinateurs quantiques peuvent résoudre plus rapidement que les ordinateurs classiques (non quantiques) et de combien cette résolution peut être plus rapide selon les algorithmes quantiques employés.

Dans les récents travaux dont il est question ici, l’équipe a mis à l’épreuve ses propres algorithmes et différents autres algorithmes. Avec un de ses algorithmes, elle a réussi une « accélération quantique supralinéaire » de la résolution d’un problème d’ensemble indépendant maximal. Autrement dit, son ordinateur quantique de 289 qubits a pu résoudre le problème en moins d’étapes qu’il ne faudrait à un ordinateur classique faisant appel au même nombre de processeurs.

Madelyn Cain, étudiante diplômée à l’Université Harvard et qui fait partie des auteurs principaux de l’article, a déclaré : « Grâce à une compréhension profonde de la physique qui sous-tend l’algorithme quantique ainsi que des limites fondamentales de son pendant classique, nous avons pu faire en sorte que l’ordinateur quantique permette cette accélération. »

Même s’il travaille encore à sa thèse de doctorat (qu’il espère compléter en 2024), M. Luo a déjà été récompensé pour ses travaux sur la compréhension de la physique qui sous-tend les algorithmes conçus pour des ordinateurs quantiques.

L’an dernier, il a remporté le premier prix quantique Wittek pour le logiciel libre. Administré par la Quantum Open Source Foundation (Fondation pour le logiciel libre quantique), ce prix récompense les contributeurs de logiciel libre en informatique quantique. M. Luo l'a remporté parmi plus de 50 candidats.

Les liens de M. Luo avec Roger Melko et l’Institut Périmètre lui ont été utiles pour en apprendre davantage sur le fonctionnement de l’ordinateur quantique de QuEra. M. Melko et son équipe du PIQuIL travaillent souvent en collaboration avec Mikhail Lukin et d’autres scientifiques de QuEra; c’est grâce à ces contacts que M. Luo a pu avoir un stage chez QuEra.

« Mon objectif personnel était d’en apprendre davantage sur QuEra et sur le fonctionnement de son matériel, dit-il. J’ai beaucoup appris. Dorénavant, je vais travailler sur d’autres théories. » [traduction]

Il y a quelques années, Google a atteint l’objectif longtemps recherché de l’« avantage quantique », en démontrant que son ordinateur quantique peut résoudre un certain type de problème mathématique, qui fait intervenir des nombres aléatoires, d’une manière plus efficace que des ordinateurs classiques.

« Mais la tâche exécutée alors avait été soigneusement choisie et n’avait pas d’application pratique, dit M. Luo. Nos travaux visent à résoudre plus rapidement avec un ordinateur quantique des problèmes qui ont des applications utiles. »

Ces efforts se poursuivent. « Pour la prochaine étape, dit M. Luo, nous espérons obtenir une accélération quadratique. » Une accélération quadratique signifie que l’ordinateur quantique pourrait résoudre en un millier d’étapes un problème qu’un ordinateur classique résoudrait normalement en un million d’étapes.

Selon M. Melko, la contribution de Xiu-Zhe Luo à ces récents travaux montre le potentiel des collaborations que l’Institut Périmètre et l’équipe du PIQuIL entretiennent avec des partenaires du milieu universitaire et du secteur privé.

À l’heure actuelle, l’équipe du PIQuIL travaille sur des algorithmes de pointe et sur l’utilisation d’ordinateurs quantiques pour améliorer les systèmes d’intelligence artificielle (IA) utilisés dans un grand nombre de secteurs de l’économie. « Nous aidons autant des universitaires que des entreprises avec des systèmes avancés d’IA », dit M. Melko. Pour sa part, l’IA peut aider à la mise au point d’algorithmes qui amélioreront les systèmes informatiques quantiques.

M. Melko ajoute que ces collaborations sont également importantes pour les étudiants diplômés de l’Institut Périmètre, parce qu’elles ouvrent des possibilités dans le secteur privé en même temps que les étudiants poursuivent leurs objectifs universitaires. De telles possibilités peuvent se présenter plus difficilement dans des milieux universitaires plus traditionnels.

M. Melko fait remarquer que le Canada est reconnu depuis longtemps comme un chef de file en informatique quantique.

Une jeune entreprise canadienne, Xanadu, a récemment déclaré avoir obtenu un avantage quantique, c’est-à-dire que son ordinateur quantique a effectué une tâche de calcul spécifique qui aurait été hors de portée pour un ordinateur classique.

Une autre entreprise canadienne, D-Wave, a mis au point pour la première fois un processus dit de recuit quantique et a été la première à utiliser cette méthode pour résoudre des problèmes d’optimisation pour le secteur privé.

Par contre, le système de D-Wave exige de l’hélium liquide pour refroidir les puces quantiques et les amener près du zéro absolu. D’autres entreprises intéressées par le domaine de l’optimisation adoptent des méthodes différentes pour résoudre ces problèmes pratiques d’une manière moins énergivore et moins coûteuse. À titre d’exemple, QuEra utilise des laser capables de piéger et de refroidir des atomes individuels dans un montage qui tient sur une table.

L’économie de l’avenir dépendra de la capacité à accroître la puissance des ordinateurs quantiques tout en les rendant moins coûteux. « Nous commençons à aborder la question de savoir si nous pouvons augmenter la puissance des ordinateurs quantiques de telle sorte qu’ils puissent résoudre des problèmes utiles même en ayant l’air petits », dit Roger Melko.

Il ajoute que les chercheurs du PIQuIL travaillent avec des entreprises et des partenaires universitaires pour les aider à atteindre cet objectif.

« Le Canada mène le bal en informatique quantique depuis des années, dit M. Melko, mais c’est bien d’entretenir des collaborations internationales avec des universitaires et des entreprises. »

La course est lancée pour réaliser des ordinateurs quantiques à la fois petits et puissants pour des applications commerciales. « C’est le défi de notre siècle », dit Xiu-Zhe Luo.