Événements
Jessica Lemieux : soutenance de thèse
Date : 13 décembre 2021 15:00
Type : Séminaires
Lieu : D3-2040
Titre : Estimation et réduction du coût d'algorithmes quantiques
Résumé de la thèse:
Plusieurs algorithmes ont été marquants dans le développement de l'informatique quantique : on peut penser notamment à l'algorithme de Shor ou à l'algorithme de Grover. Bien que pour ce dernier, par exemple, nous ayons une accélération quadratique prouvée, il n'est pas clair que ce sera suffisant pour offrir un avantage pratique par rapport aux algorithmes classiques. D'abord, celui-ci est formulé en termes d'oracle, une boîte noire qui cache une sous-routine non comprise dans le calcul du coût. Ensuite, lorsque l'on prend en considération le surcoût engendré notamment par la correction d'erreur quantique, il est possible de perdre l'accélération promise. Mais également, le temps d'une porte logique quantique est considérablement plus long que son homologue classique. Quel est le coût réel d'un algorithme quantique lorsque l'on prend en considération toutes les sous-routines ? À quand un ordinateur quantique utile qui surpassera les performances d'un superordinateur ?
Nous présenterons trois projets visant tous à estimer et réduire le coût d'algorithmes ou sous-routines quantiques. Les algorithmes abordés sont issus d'une discrétisation de l'évolution adiabatique. Le premier se concentre sur un algorithme de préparation d'état de système à N corps par une évolution adiabatique via l'effet Zénon. Le second porte sur une version quantique des algorithmes de marches aléatoires et de recuit simulé pouvant, par exemple, préparer un état stationnaire. Le dernier décrit un nouvel algorithme : une évolution adiabatique basée sur la réflexion. Celui-ci permet, entre autres, de résoudre des problèmes MAX-kSAT, une classe de problèmes NP-difficile. Avec ces projets, nous voulons, d'une part, proposer des algorithmes efficaces ainsi que leur implémentation de A à Z et, d'autre part, estimer les caractéristiques nécessaires à un ordinateur quantique utile (par ex. taille, résistance au bruit, vitesse d'opération).
Les résultats présentés démontrent le coût élevé associé aux algorithmes tolérants aux fautes. Bien qu'on s'attende à avoir une accélération par rapport au classique, lorsque l'on prend en considération le nombre de qubits physiques, le nombre d'opérations physiques et le temps de chacune de ces opérations, en incluant la correction d'erreur notamment, la taille des instances offrant un avantage réel est loin d'être atteignable pour les processeurs quantiques à court terme. Toutefois, en combinant des méthodes astucieuses et au moyen de différents procédés d'optimisation, il est possible de réduire considérablement le coût des algorithmes quantiques, et donc de réduire le délai pour atteindre la suprématie quantique.
Résumé de la thèse:
Plusieurs algorithmes ont été marquants dans le développement de l'informatique quantique : on peut penser notamment à l'algorithme de Shor ou à l'algorithme de Grover. Bien que pour ce dernier, par exemple, nous ayons une accélération quadratique prouvée, il n'est pas clair que ce sera suffisant pour offrir un avantage pratique par rapport aux algorithmes classiques. D'abord, celui-ci est formulé en termes d'oracle, une boîte noire qui cache une sous-routine non comprise dans le calcul du coût. Ensuite, lorsque l'on prend en considération le surcoût engendré notamment par la correction d'erreur quantique, il est possible de perdre l'accélération promise. Mais également, le temps d'une porte logique quantique est considérablement plus long que son homologue classique. Quel est le coût réel d'un algorithme quantique lorsque l'on prend en considération toutes les sous-routines ? À quand un ordinateur quantique utile qui surpassera les performances d'un superordinateur ?
Nous présenterons trois projets visant tous à estimer et réduire le coût d'algorithmes ou sous-routines quantiques. Les algorithmes abordés sont issus d'une discrétisation de l'évolution adiabatique. Le premier se concentre sur un algorithme de préparation d'état de système à N corps par une évolution adiabatique via l'effet Zénon. Le second porte sur une version quantique des algorithmes de marches aléatoires et de recuit simulé pouvant, par exemple, préparer un état stationnaire. Le dernier décrit un nouvel algorithme : une évolution adiabatique basée sur la réflexion. Celui-ci permet, entre autres, de résoudre des problèmes MAX-kSAT, une classe de problèmes NP-difficile. Avec ces projets, nous voulons, d'une part, proposer des algorithmes efficaces ainsi que leur implémentation de A à Z et, d'autre part, estimer les caractéristiques nécessaires à un ordinateur quantique utile (par ex. taille, résistance au bruit, vitesse d'opération).
Les résultats présentés démontrent le coût élevé associé aux algorithmes tolérants aux fautes. Bien qu'on s'attende à avoir une accélération par rapport au classique, lorsque l'on prend en considération le nombre de qubits physiques, le nombre d'opérations physiques et le temps de chacune de ces opérations, en incluant la correction d'erreur notamment, la taille des instances offrant un avantage réel est loin d'être atteignable pour les processeurs quantiques à court terme. Toutefois, en combinant des méthodes astucieuses et au moyen de différents procédés d'optimisation, il est possible de réduire considérablement le coût des algorithmes quantiques, et donc de réduire le délai pour atteindre la suprématie quantique.