.svg)
Le moteur CLASSIQ : je peux obtenir une certaine satisfaction
Avez-vous déjà résolu un puzzle Sudoku ? Ce jeu a été très populaire au début des années 2000. Pour une raison ou une autre, tout le monde les résolvait sans cesse. Il faut dire qu'il s'agissait d'une époque bien antérieure aux smartphones. Les gens n'avaient tout simplement pas mieux à faire. Si vous n'en avez jamais entendu parler, dans un Sudoku, l'objectif est de remplir une grille 9X9 avec des chiffres de telle sorte que dans chaque ligne et chaque colonne, chaque chiffre n'apparaisse qu'une seule fois. Ce type d'énigme est un exemple de problème de satisfaction de contraintes (CSP). Il s'agit de problèmes dans lesquels vous devez "remplir les blancs" avec un élément (par exemple, un chiffre) parmi un ensemble de possibilités (par exemple, les chiffres de 1 à 9) sans enfreindre un ensemble de règles (par exemple, pas de répétition d'un chiffre), et ils sont plus courants qu'on ne le pense.
La classe des CSP a d'autres exemples, sans doute plus intéressants, sous la forme de jeux (n'importe quel mot croisé), de mathématiques (coloriage de cartes[https://en.wikipedia.org/wiki/Four_color_theorem]), et ainsi de suite. Il y a une raison pour laquelle tout cela est important pour nous, et ce n'est pas parce que nous voulons prouver un théorème mathématique. C'est beaucoup plus pratique que cela. Du moins si vous travaillez dans le domaine de la conception d'algorithmes quantiques.
Optimisation des circuits quantiques
Il n'y a pas de repas gratuit, mais il est agréable d'en avoir pour son argent. C'est la raison d'être des techniques d'optimisation : trouver le moyen de maximiser (ou de minimiser) certains paramètres d'un problème. Il existe de nombreux types de problèmes de ce type. Parfois, la chose que vous essayez d'optimiser prend des valeurs continues, tandis que d'autres fois, ces valeurs sont discrètes. Votre espace d'optimisation peut être fini ou infini, et il peut également varier de différentes manières. Dans les CSP, vous disposez d'un ensemble de contraintes que vous souhaitez satisfaire au mieux. Cette sous-classe de CSP peut être appelée CSOP, où "O" signifie "Optimisation".
Nous voulons concevoir un algorithme quantique et faire en sorte que nos blocs de construction soient de "haut niveau". Nous voulons donc travailler avec autre chose que des portes quantiques individuelles. Nous souhaitons plutôt utiliser un appel de fonction qui est ensuite converti en la séquence de portes correcte. Cette étape, au cours de laquelle les appels de fonction de haut niveau sont remplacés par des séquences de portes, est appelée synthèse. Ce n'est pas la seule chose qui se passe ici, mais pour des raisons de simplicité, n'en considérons qu'un aspect. Lors de la synthèse, nous sommes principalement limités par le matériel quantique. Nous disposons d'un nombre fini de qubits, d'une limite supérieure à la profondeur du circuit que nous pouvons exécuter avant que le bruit ne nous submerge, etc.
Le jeu auquel nous sommes confrontés est le suivant : Allouer des ressources (nombre de qubits, profondeur de circuit, etc...) aux fonctions de manière à respecter au mieux les contraintes spécifiées.
Atteindre vos objectifs, mais le terrain est mouvant
Dans un cas simple, chaque appel de fonction est un "masque", qui peut être remplacé par une séquence de portes fixe. Vous placez ces séquences l'une après l'autre et vous obtenez un circuit. Cela serait ennuyeux et laisserait peu de marge de manœuvre pour la synthèse. Dans ce cas, la séquence d'appels de fonctions détermine de manière unique le circuit résultant. Heureusement, il se passe ici quelque chose de beaucoup plus intéressant et de plus difficile.
Il s'agit d'un problème plus intéressant que vous ne le supposez, car il existe plus d'une implémentation correcte pour certaines fonctions. Différentes implémentations sont possibles pour diverses raisons. Un exemple est celui des implémentations dépendantes du matériel. Celles-ci sont dues à des jeux de portes natifs différents dans les processeurs quantiques à ions piégés de ceux des processeurs quantiques à atomes neutres (ou d'autres types de qubits). Une autre raison est la carte de connectivité des qubits. Ces cartes spécifient sur quelles paires de qubits les opérations conditionnelles peuvent se produire, et elles varient entre les architectures de puces à qubits (même pour un type de qubit donné).
Les mises en œuvre multiples ne sont pas seulement dues à des différences matérielles. Un exemple est celui du circuit additionneur. Cet élément de circuit permet d'additionner les nombres représentés par différents registres (ensembles de qubits). Il s'agit d'un composant fondamental de tout ordinateur, y compris les ordinateurs classiques. Il est tout aussi précieux pour les calculs quantiques. La mise en œuvre de cet élément peut être représentée de plusieurs manières, sous la forme de portes logiques quantiques. L'objectif de l'additionneur peut être atteint par un circuit à portage ondulatoire(https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder) ou par l'utilisation de la transformée de Fourier quantique (voir cet article : https://arxiv.org/pdf/1411.5949.pdf). Les différentes implémentations ont des caractéristiques différentes en termes de nombre de qubits utilisés, de profondeur de circuit, de nombre d'opérations à deux qubits effectuées, etc.
Réduire, réutiliser, recycler
Les ressources sont rares en informatique, qu'elle soit quantique ou autre. À moins de résoudre des problèmes vraiment faciles, vous vous heurtez généralement à l'un des deux murs suivants : soit vous n'avez pas assez de vitesse, soit vous n'avez pas assez d'espace. Soit vous n'avez pas assez de vitesse, soit vous n'avez pas assez d'espace. Il est souvent possible de convertir l'un de ces problèmes en l'autre, mais seulement parfois, et cela n'est utile que dans certains cas.
C'est pourquoi le développement de méthodes permettant une utilisation parcimonieuse des ressources est une tradition ancienne (et nécessaire) en informatique. Une gestion efficace de la mémoire ou du ramassage des ordures est essentielle et permet aux programmes de réutiliser de manière répétée les mêmes morceaux d'espace physique dans un programme. L'automatisation de ces tâches est le domaine des logiciels d'automatisation de la conception électronique (EDA), qui a été une source d'inspiration pour le moteur CLASSIQ.
Lors de la synthèse de programmes quantiques, un élément particulièrement délicat du puzzle est de savoir ce qu'il faut faire avec les qubits auxiliaires. Une fois de plus, concentrons notre attention sur ce que le moteur de synthèse doit faire.
Le moteur sélectionne une implémentation de la fonction de haut niveau et la "connecte" ensuite à l'implémentation de la fonction suivante. Si cette fonction possède un (ou plusieurs) qubit(s) auxiliaire(s), c'est-à-dire un qubit qui a été utilisé et qui n'est plus pertinent, il peut être réutilisé par une autre fonction. S'il ne peut pas être réutilisé et que la fonction suivante a également besoin d'un qubit auxiliaire, nous devrons allouer un nouveau qubit à cette fonction (que nous n'avons peut-être pas sous la main !).
Cette réutilisation des qubits auxiliaires rend le problème de satisfaction des contraintes (et d'optimisation) que nous essayons de résoudre "non local", dans un certain sens. Et si le choix d'une implémentation (et d'un câblage de qubits auxiliaires) au début du circuit, qui semblait être une bonne idée à l'époque, m'obligeait à choisir une implémentation moins appropriée par la suite ? Une implémentation qui est globalement moins bonne pour l'optimisation de ma cible ? Vous faites un choix, et l'objectif final évolue dans une direction ou une autre, ce qui vous oblige à réévaluer vos décisions et à les modifier rétrospectivement. Si seulement la vie réelle vous donnait de telles libertés.
Des stratégies simples pour réussir
Il existe de nombreuses façons d'organiser les fonctions et d'allouer des ressources à chacune d'entre elles. Ce nombre augmente de manière exponentielle avec le nombre de fonctions, comme les choses quantiques ont tendance à le faire. Cela signifie qu'avec une approche brute, vous ne résoudrez pas le problème si vous avez beaucoup d'appels de fonctions, à moins que (peut-être) vous ayez déjà un ordinateur quantique fonctionnel pour accélérer la recherche des possibilités de manière efficace. Il faudrait encore les stocker d'une manière ou d'une autre, de sorte que même un ordinateur quantique pourrait ne pas suffire !
Il existe plusieurs façons de s'attaquer à ce problème difficile. La première approche, qui est lente mais au moins méthodique, est celle des algorithmes de backtracking(https://en.wikipedia.org/wiki/Backtracking). Il s'agit d'une méthode incrémentale (récursive) pour construire le circuit couche par couche. Pour améliorer cette méthode, il existe de meilleurs algorithmes, dont certains sont basés sur des heuristiques astucieuses. Nous reviendrons sur ces techniques dans de futurs articles de blog.
Quelle est la prochaine étape ?
Aujourd'hui, nous avons eu un petit aperçu du monde du CSP et de la façon dont il s'applique au problème de la synthèse de circuits d'algorithmes quantiques. Ou, comme nous l'appelons à CLASSIQ : le pain et le beurre.
Nous avons pris connaissance de la configuration du problème et de ce que l'on pourrait naïvement faire pour commencer à s'y attaquer. Mais le moteur de CLASSIQ pousse ces idées beaucoup plus loin. Au-delà de l'application de méthodes plus complexes et plus intelligentes pour sélectionner rapidement et efficacement l'implémentation des blocs, il existe des extensions du problème dues aux défis spécifiques posés par la nature quantique des circuits que nous devons construire.
Comment résoudre un CSOP lorsqu'il est possible d'effectuer des mesures à mi-circuit ? Comment des considérations telles que le bruit cohérent et incohérent devraient-elles être intégrées dans un moteur de synthèse ? Comment le traitement de l'information dans un flux de travail hybride de calcul classique et quantique peut-il alimenter, au moment de l'exécution, la synthèse ou la re-synthèse de circuits ? Il s'agit là de questions difficiles et fascinantes. Dans les prochains articles, nous plongerons plus profondément dans le monde de la synthèse de circuits et dans les défis algorithmiques qu'elle pose.
Avez-vous déjà résolu un puzzle Sudoku ? Ce jeu a été très populaire au début des années 2000. Pour une raison ou une autre, tout le monde les résolvait sans cesse. Il faut dire qu'il s'agissait d'une époque bien antérieure aux smartphones. Les gens n'avaient tout simplement pas mieux à faire. Si vous n'en avez jamais entendu parler, dans un Sudoku, l'objectif est de remplir une grille 9X9 avec des chiffres de telle sorte que dans chaque ligne et chaque colonne, chaque chiffre n'apparaisse qu'une seule fois. Ce type d'énigme est un exemple de problème de satisfaction de contraintes (CSP). Il s'agit de problèmes dans lesquels vous devez "remplir les blancs" avec un élément (par exemple, un chiffre) parmi un ensemble de possibilités (par exemple, les chiffres de 1 à 9) sans enfreindre un ensemble de règles (par exemple, pas de répétition d'un chiffre), et ils sont plus courants qu'on ne le pense.
La classe des CSP a d'autres exemples, sans doute plus intéressants, sous la forme de jeux (n'importe quel mot croisé), de mathématiques (coloriage de cartes[https://en.wikipedia.org/wiki/Four_color_theorem]), et ainsi de suite. Il y a une raison pour laquelle tout cela est important pour nous, et ce n'est pas parce que nous voulons prouver un théorème mathématique. C'est beaucoup plus pratique que cela. Du moins si vous travaillez dans le domaine de la conception d'algorithmes quantiques.
Optimisation des circuits quantiques
Il n'y a pas de repas gratuit, mais il est agréable d'en avoir pour son argent. C'est la raison d'être des techniques d'optimisation : trouver le moyen de maximiser (ou de minimiser) certains paramètres d'un problème. Il existe de nombreux types de problèmes de ce type. Parfois, la chose que vous essayez d'optimiser prend des valeurs continues, tandis que d'autres fois, ces valeurs sont discrètes. Votre espace d'optimisation peut être fini ou infini, et il peut également varier de différentes manières. Dans les CSP, vous disposez d'un ensemble de contraintes que vous souhaitez satisfaire au mieux. Cette sous-classe de CSP peut être appelée CSOP, où "O" signifie "Optimisation".
Nous voulons concevoir un algorithme quantique et faire en sorte que nos blocs de construction soient de "haut niveau". Nous voulons donc travailler avec autre chose que des portes quantiques individuelles. Nous souhaitons plutôt utiliser un appel de fonction qui est ensuite converti en la séquence de portes correcte. Cette étape, au cours de laquelle les appels de fonction de haut niveau sont remplacés par des séquences de portes, est appelée synthèse. Ce n'est pas la seule chose qui se passe ici, mais pour des raisons de simplicité, n'en considérons qu'un aspect. Lors de la synthèse, nous sommes principalement limités par le matériel quantique. Nous disposons d'un nombre fini de qubits, d'une limite supérieure à la profondeur du circuit que nous pouvons exécuter avant que le bruit ne nous submerge, etc.
Le jeu auquel nous sommes confrontés est le suivant : Allouer des ressources (nombre de qubits, profondeur de circuit, etc...) aux fonctions de manière à respecter au mieux les contraintes spécifiées.
Atteindre vos objectifs, mais le terrain est mouvant
Dans un cas simple, chaque appel de fonction est un "masque", qui peut être remplacé par une séquence de portes fixe. Vous placez ces séquences l'une après l'autre et vous obtenez un circuit. Cela serait ennuyeux et laisserait peu de marge de manœuvre pour la synthèse. Dans ce cas, la séquence d'appels de fonctions détermine de manière unique le circuit résultant. Heureusement, il se passe ici quelque chose de beaucoup plus intéressant et de plus difficile.
Il s'agit d'un problème plus intéressant que vous ne le supposez, car il existe plus d'une implémentation correcte pour certaines fonctions. Différentes implémentations sont possibles pour diverses raisons. Un exemple est celui des implémentations dépendantes du matériel. Celles-ci sont dues à des jeux de portes natifs différents dans les processeurs quantiques à ions piégés de ceux des processeurs quantiques à atomes neutres (ou d'autres types de qubits). Une autre raison est la carte de connectivité des qubits. Ces cartes spécifient sur quelles paires de qubits les opérations conditionnelles peuvent se produire, et elles varient entre les architectures de puces à qubits (même pour un type de qubit donné).
Les mises en œuvre multiples ne sont pas seulement dues à des différences matérielles. Un exemple est celui du circuit additionneur. Cet élément de circuit permet d'additionner les nombres représentés par différents registres (ensembles de qubits). Il s'agit d'un composant fondamental de tout ordinateur, y compris les ordinateurs classiques. Il est tout aussi précieux pour les calculs quantiques. La mise en œuvre de cet élément peut être représentée de plusieurs manières, sous la forme de portes logiques quantiques. L'objectif de l'additionneur peut être atteint par un circuit à portage ondulatoire(https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder) ou par l'utilisation de la transformée de Fourier quantique (voir cet article : https://arxiv.org/pdf/1411.5949.pdf). Les différentes implémentations ont des caractéristiques différentes en termes de nombre de qubits utilisés, de profondeur de circuit, de nombre d'opérations à deux qubits effectuées, etc.
Réduire, réutiliser, recycler
Les ressources sont rares en informatique, qu'elle soit quantique ou autre. À moins de résoudre des problèmes vraiment faciles, vous vous heurtez généralement à l'un des deux murs suivants : soit vous n'avez pas assez de vitesse, soit vous n'avez pas assez d'espace. Soit vous n'avez pas assez de vitesse, soit vous n'avez pas assez d'espace. Il est souvent possible de convertir l'un de ces problèmes en l'autre, mais seulement parfois, et cela n'est utile que dans certains cas.
C'est pourquoi le développement de méthodes permettant une utilisation parcimonieuse des ressources est une tradition ancienne (et nécessaire) en informatique. Une gestion efficace de la mémoire ou du ramassage des ordures est essentielle et permet aux programmes de réutiliser de manière répétée les mêmes morceaux d'espace physique dans un programme. L'automatisation de ces tâches est le domaine des logiciels d'automatisation de la conception électronique (EDA), qui a été une source d'inspiration pour le moteur CLASSIQ.
Lors de la synthèse de programmes quantiques, un élément particulièrement délicat du puzzle est de savoir ce qu'il faut faire avec les qubits auxiliaires. Une fois de plus, concentrons notre attention sur ce que le moteur de synthèse doit faire.
Le moteur sélectionne une implémentation de la fonction de haut niveau et la "connecte" ensuite à l'implémentation de la fonction suivante. Si cette fonction possède un (ou plusieurs) qubit(s) auxiliaire(s), c'est-à-dire un qubit qui a été utilisé et qui n'est plus pertinent, il peut être réutilisé par une autre fonction. S'il ne peut pas être réutilisé et que la fonction suivante a également besoin d'un qubit auxiliaire, nous devrons allouer un nouveau qubit à cette fonction (que nous n'avons peut-être pas sous la main !).
Cette réutilisation des qubits auxiliaires rend le problème de satisfaction des contraintes (et d'optimisation) que nous essayons de résoudre "non local", dans un certain sens. Et si le choix d'une implémentation (et d'un câblage de qubits auxiliaires) au début du circuit, qui semblait être une bonne idée à l'époque, m'obligeait à choisir une implémentation moins appropriée par la suite ? Une implémentation qui est globalement moins bonne pour l'optimisation de ma cible ? Vous faites un choix, et l'objectif final évolue dans une direction ou une autre, ce qui vous oblige à réévaluer vos décisions et à les modifier rétrospectivement. Si seulement la vie réelle vous donnait de telles libertés.
Des stratégies simples pour réussir
Il existe de nombreuses façons d'organiser les fonctions et d'allouer des ressources à chacune d'entre elles. Ce nombre augmente de manière exponentielle avec le nombre de fonctions, comme les choses quantiques ont tendance à le faire. Cela signifie qu'avec une approche brute, vous ne résoudrez pas le problème si vous avez beaucoup d'appels de fonctions, à moins que (peut-être) vous ayez déjà un ordinateur quantique fonctionnel pour accélérer la recherche des possibilités de manière efficace. Il faudrait encore les stocker d'une manière ou d'une autre, de sorte que même un ordinateur quantique pourrait ne pas suffire !
Il existe plusieurs façons de s'attaquer à ce problème difficile. La première approche, qui est lente mais au moins méthodique, est celle des algorithmes de backtracking(https://en.wikipedia.org/wiki/Backtracking). Il s'agit d'une méthode incrémentale (récursive) pour construire le circuit couche par couche. Pour améliorer cette méthode, il existe de meilleurs algorithmes, dont certains sont basés sur des heuristiques astucieuses. Nous reviendrons sur ces techniques dans de futurs articles de blog.
Quelle est la prochaine étape ?
Aujourd'hui, nous avons eu un petit aperçu du monde du CSP et de la façon dont il s'applique au problème de la synthèse de circuits d'algorithmes quantiques. Ou, comme nous l'appelons à CLASSIQ : le pain et le beurre.
Nous avons pris connaissance de la configuration du problème et de ce que l'on pourrait naïvement faire pour commencer à s'y attaquer. Mais le moteur de CLASSIQ pousse ces idées beaucoup plus loin. Au-delà de l'application de méthodes plus complexes et plus intelligentes pour sélectionner rapidement et efficacement l'implémentation des blocs, il existe des extensions du problème dues aux défis spécifiques posés par la nature quantique des circuits que nous devons construire.
Comment résoudre un CSOP lorsqu'il est possible d'effectuer des mesures à mi-circuit ? Comment des considérations telles que le bruit cohérent et incohérent devraient-elles être intégrées dans un moteur de synthèse ? Comment le traitement de l'information dans un flux de travail hybride de calcul classique et quantique peut-il alimenter, au moment de l'exécution, la synthèse ou la re-synthèse de circuits ? Il s'agit là de questions difficiles et fascinantes. Dans les prochains articles, nous plongerons plus profondément dans le monde de la synthèse de circuits et dans les défis algorithmiques qu'elle pose.
A propos de "The Qubit Guy's Podcast" (Le podcast du gars de Qubit)
Animé par The Qubit Guy (Yuval Boger, notre directeur marketing), le podcast accueille des leaders d'opinion de l'informatique quantique pour discuter de questions commerciales et techniques qui ont un impact sur l'écosystème de l'informatique quantique. Nos invités fournissent des informations intéressantes sur les logiciels et algorithmes d'ordinateurs quantiques, le matériel informatique quantique, les applications clés de l'informatique quantique, les études de marché de l'industrie quantique et bien plus encore.
Si vous souhaitez proposer un invité pour le podcast, veuillez nous contacter.
