.svg)
Rendre les algorithmes quantiques universitaires automatiquement exécutables
Les constructions de modélisation quantique et les fortes capacités de synthèse comblent le fossé entre l'intention des concepteurs d'algorithmes quantiques, telle qu'elle est publiée dans les articles universitaires, et les implémentations réelles qui peuvent être exécutées sur des ordinateurs quantiques, des simulateurs et des estimateurs de ressources.
Introduction
Au cours des trente dernières années, les algorithmes quantiques ont été en grande partie une activité académique. Les théoriciens ont publié des algorithmes bien définis et éprouvés et les ont décrits dans un langage scientifique solide. Cette description comprend des figures, des légendes, du texte, des équations et d'autres outils mis à la disposition des scientifiques pour décrire formellement et prouver l'exactitude de leur travail. Malheureusement, cette description repose sur une compréhension mutuelle entre les chercheurs et est basée sur un langage scientifique formel. Ce langage n'est pas suffisamment formel pour que les compilateurs puissent comprendre et produire une description de l'algorithme quantique exécutable par un ordinateur quantique.
Dans cet article, nous présentons de nouvelles constructions de modélisation et de nouveaux idiomes qui résultent d'un examen approfondi de nombreux algorithmes quantiques et d'implémentations publiés au fil des ans. Même dans des algorithmes aussi singuliers que ceux de Shor, Grover ou HHL - qui peuvent tous être énoncés relativement simplement en faisant abstraction de toute structure interne - une multitude de complexités apparaissent lorsqu'on examine le niveau de détail suivant - l'exponentiation modulaire dans l'algorithme de Shor, l'oracle dans celui de Grover et la forme des équations linéaires dans celui de HHL. Nous suivrons ci-dessous l'exemple de l'algorithme de Shor, car il est le plus simple à comprendre pour quiconque suit un cours d'introduction aux algorithmes quantiques. En utilisant l'estimateur de ressources quantiques Azure de Microsoft, nous montrons que l'exécution de l'algorithme de Shor avec quatre additions modulaires nécessite 354 562 qubits physiques, et nous identifions les nombres de portes spécifiques nécessaires. Dans cet exemple, nous ne montrerons que les constructions de modélisation que nous avons trouvées pertinentes dans un large éventail d'algorithmes quantiques.
La valeur globale de notre méthode est déterminée par le degré de ressemblance du modèle avec le circuit quantique tel qu'il a été décrit par le concepteur, par exemple dans un article universitaire, et par la capacité du modèle à capturer sans ambiguïté toutes les exigences formelles du circuit.
Les constructions de modélisation, ainsi que le moteur de synthèse capable de comprendre formellement le modèle et de produire une mise en œuvre concrète et optimisée du circuit quantique, ont tous été mis en œuvre dans la plateforme de conception d'algorithmes quantiques de Classiq, atteignant ainsi pour la première fois la capacité de créer des algorithmes quantiques complexes, de la pensée à l'exécution. Les algorithmes quantiques (par exemple, les implémentations de l'algorithme de Shor) créés par la plateforme Classiq sont de loin les algorithmes quantiques les plus complexes et les plus grands jamais créés.
Mise en œuvre de l'algorithme de Shor
Nous passons en revue les principaux concepts et outils utilisés dans la modélisation graphique de Classiq pour générer un circuit implémentant l'algorithme de Shor factorisant un nombre N représenté par n bits. Le circuit suit l'implémentation de Beauregard(https://arxiv.org/pdf/quant-ph/0205095 [1]) et nécessite 4n+2 qubits. La différence entre les deux circuits est que le circuit original de Beauregard implémente le circuit QFT inverse final sur un seul qubit en mesurant et en préparant à nouveau un seul qubit 2n fois (ce qui nécessite 2n+3 qubits), alors que notre implémentation utilise la QFT "régulière" sur 2n qubits.
Le circuit met en œuvre la partie quantique de l'algorithme de Shor. Rappelons que dans l'algorithme de Shor, pour trouver un facteur d'un nombre n-qubit donné N, on choisit un nombre aléatoire a plus petit que N et on calcule pgcd(a,N), où pgcd désigne le plus grand dénominateur commun. Si pgcd(a, N) >1, nous avons terminé - pgcd(a,N) est un facteur de N. Sinon, nous effectuons la partie quantique de l'algorithme - dont l'essentiel consiste à calculer $|a^xmodN\rangle$ (la partie quantique est suivie d'un post-traitement classique supplémentaire du résultat mesuré).
Pour construire un tel circuit pour un n donné, il faut pouvoir exprimer le circuit de manière hiérarchique en commençant par les blocs quantiques de base au niveau le plus bas (les blocs quantiques sont des portes et des fonctions de base reconnues par le moteur de synthèse) jusqu'au circuit entier au niveau le plus élevé. En outre, il faut pouvoir travailler avec des registres plutôt qu'avec des qubits individuels, c'est-à-dire appliquer des portes à des registres tout en conservant la possibilité de découper des registres et d'appliquer des portes à des qubits sélectionnés. Les outils qui permettent une telle modélisation d'un circuit sont démontrés dans chacune des principales hiérarchies/couches du circuit qui sont :
- Un additionneur modulaire dans l'espace de Fourier construit à partir de portes de base (principalement des portes à phase, à phase contrôlée et à double phase contrôlée) et de QFT.
- Multiplication modulaire construite à partir de n additionneurs modulaires.
- Exponentiation modulaire construite à partir de n circuits de multiplication modulaire.
Le circuit de l'additionneur modulaire contrôlé
Dans l'additionneur modulaire, le nombre a est ajouté à un registre quantique de (n+1) qubits (le registre b). L'état d'entrée du registre est celui où le bit le plus significatif (MSB) de b a la valeur zéro. Ce qubit est utilisé comme bit de débordement. En outre, le circuit comprend deux bits de contrôle et un bit auxiliaire qui est nul à l'entrée et à la sortie. L'additionneur modulaire est donné par le circuit suivant. La barre noire épaisse distingue l'additionneur (barre de droite) de son inverse, la soustraction (barre de gauche) :
Pour c1=c2=1, le fonctionnement du circuit est le suivant (pour d'autres valeurs de ci, les opérations commandées ne sont pas activées et le reste des opérations s'annule).
o Sous-circuit A : Ajoute a au registre b de (n+1) qubits portant $\Phi(b)$.
o Sub-circuit B: Subtracts N from a+b and then adds N again if N < a+b – this is done by checking the MSB of a+b-N.
$$|1,1,\NPhi (b),0\rangle \Nrightarrow |1,1,\NPhi (b+a),0\rangle$$$
Notez qu'à ce stade, le registre b est dans l'état (a+b)mod N, alors qu'en général, il est enchevêtré avec le qubit auxiliaire.
o Sous-circuit C : réinitialise le dernier qubit auxiliaire à $|0\rangle$ (en le dissociant du registre b) en soustrayant a du registre et en vérifiant le bit le plus significatif du registre b(en retournant le bit auxiliaire si nécessaire) et en ajoutant à nouveau a au registre.
Le fonctionnement de l'ensemble du circuit sur les états d'entrée "légaux" (où le MSB de b est zéro) est requis :
$$|1,1,\NPhi (b),0\rangle \Nrightarrow |1,1,\NPhi ((b+a) mod N),0\rangle .$$$
Le principal élément constitutif de l'additionneur modulaire est un circuit additionneur (dans la base de Fourier), qui ajoute le nombre a (plus petit que N) à un registre quantique de (n+1) qubits, et son inverse (avec et sans contrôle). L'additionneur (non contrôlé) est construit uniquement à partir de portes de phase à qubit unique (ici - $|\Phi(b)\rangle = QFT|b\rangle $) :
Le nombre a est ici "classique" dans le sens où il n'est pas porté par un registre quantique mais encodé dans les phases. Dans notre plateforme, l'additionneur est réalisé directement par l'outil de modélisation en cascade avec lequel une opération est dupliquée verticalement : elle est appliquée à tous les qubits d'un registre, comme illustré ci-dessous (la raison pour laquelle on l'appelle cascade et non, par exemple, forall, apparaîtra plus tard).
L'entrée et la sortie ci-dessus sont des registres de W qubits avec W, un paramètre défini en haut de la hiérarchie, et l'instruction de cascade applique la porte de phase à qubit unique à chaque qubit dans le registre. Une phase différente est introduite dans chacun des qubits. Ces phases sont introduites dans le circuit par l'utilisateur dans le cadre de la modélisation. Les noms de port formels des portes sont target_in et target_out.
Un autre bloc de construction utilisé dans le sous-circuit additionneur modulaire (figure 1) est l'additionneur contrôlé et doublement contrôlé, où les portes de phase sont remplacées par des portes à phase contrôlée (CPhase). Dans cette porte, un seul qubit contrôle les phases des qubits cibles. Pour appliquer une porte de manière répétée au même registre, nous utilisons l'instruction instances. Dans la mise en œuvre de l'additionneur contrôlé, cependant, les phases sont introduites séquentiellement dans tous les qubits du registre cible, et il faut donc utiliser à la fois la cascade (répétition sur les qubits) et les instances (répétition des portes).
Le qubit unique du registre de contrôle participe à toutes les W portes de la phase CP de la séquence, tandis que chacun des W qubits du registre cible participe à une seule porte.
Le schéma complet réalisant le circuit de l'additionneur modulaire de la figure 1 est illustré ci-dessous. Remarquez à quel point ce circuit est similaire au dessin académique de la figure 1, à la différence près, bien sûr, que ce circuit est entièrement exécutable et optimisable jusqu'à la meilleure implémentation concrète grâce au moteur de synthèse.
Le circuit se compose de cinq additionneurs (y compris les additionneurs contrôlés et inversés) et de deux fonctions "twoQFT", qui mettent en œuvre les deux constructions du circuit ci-dessus, en vérifiant le qubit MSB dans le registre b et en inversant le qubit auxiliaire si nécessaire (chacune de ces constructions comprend deux fonctions QFT qui amènent le registre b dans l'espace de Fourier et le quittent). Cette convention de dénomination est illustrée à la figure 5 et expliquée dans la légende ci-dessous.
Le circuit multiplicateur modulaire contrôlé
Le circuit mettant en œuvre la multiplication modulaire peut être construit en répétant n fois la fonction de l'additionneur modulaire, comme indiqué ci-dessous :
Notez que dans la figure 6, les contrôles sur le $\Phi$ADD(2j )mod N ne sont pas complètement "légaux" (bien qu'il soit graphiquement bien défini dans [1] comme le circuit de la figure 1), puisque le contrôle n'est pas appliqué à toutes les portes à l'intérieur du sous-circuit $\Phi$ADD(2j )mod N et que l'évolution contrôlée correcte n'est obtenue que pour les entrées "légales" où le bit de débordement est à 0.
L'ensemble des opérations des n additionneurs modulaires est effectué dans l'espace de Fourier, c'est pourquoi des QFT et QFT inverses supplémentaires sont nécessaires dans et hors de l'espace de Fourier. Ce circuit peut être implémenté directement par le modeleur graphique comme indiqué ci-dessous :
Il convient de noter que le circuit additionneur modulaire (figure 5) reçoit deux registres à qubit unique comme commandes, tandis qu'à la couche supérieure de multiplication (figure 7), le registre c2 comprend n qu bits qui sont ensuite mis en cascade à la couche inférieure d'addition modulaire.
L'exponentiation modulaire est mise en œuvre en répétant la multiplication modulaire 2n fois pour différentes puissances de a . Dans le circuit de multiplication modulaire, le registre b est initialement à l'état 0, et afin de le réutiliser dans chacune des 2n multiplications modulaires, il doit être renvoyé à 0. Cela peut être fait en appliquant une permutation contrôlée entre les registres b et x, puis en appliquant la multiplication modulaire inverse pour la valeur inverse de la puissance de a appropriée.
Exponentiation modulaire
L'exponentiation modulaire est effectuée en entrant le nombre 1 dans le registre b, en préparant un registre de 2n qubits supérieurs (par une transformation de Hadamard) et en appliquant directement la paire de constructions de multiplication modulaire ci-dessus 2n fois - en cascadant le registre de 2n qubits supérieurs de sorte que chaque qubit dans le registre contrôle l'opération de multiplication modulaire appropriée et en appliquant une QFT inverse au registre supérieur (le résultat de la partie quantique est obtenu en mesurant ce registre). L'algorithme de Shor dans son ensemble, dont la principale partie de modélisation est l'exponentiation modulaire, est illustré à la figure 8.
Synthèse
Le moteur de synthèse, qui prend le modèle décrit ci-dessus en entrée et produit un circuit d'implémentation optimal conforme au modèle fonctionnel, dépasse le cadre de cet article. Nous mentionnons seulement ici que pour chaque bloc fonctionnel du modèle, il existe de nombreuses implémentations fonctionnellement équivalentes (par exemple, manifestant les compromis entre le nombre de qubits auxiliaires implémentant le bloc, sa profondeur, le nombre de portes à 2 qubits qu'il contient, et sa précision globale). Le moteur de synthèse a pour tâche de trouver la meilleure implémentation pour le circuit global en fonction d'un budget de qubits, de profondeur, de temps d'exécution, de fidélité globale, de précision algorithmique et d'objectif global. Nous notons également que l'optimisation à ce niveau fonctionnel est beaucoup plus puissante que l'optimisation au niveau du transpondeur, car le transpondeur doit conserver intacte la sémantique de bas niveau du circuit - par opposition à la préservation de la seule sémantique fonctionnelle du circuit lorsqu'il a accès à cette sémantique. Une implémentation finale de l'algorithme de Shor est présentée à la figure 9.
Estimation des ressources pour une réalisation tolérante aux fautes du circuit de Shor
Les circuits mettant en œuvre l'exponentiation modulaire et l'algorithme de Shor, comme la mise en œuvre ci-dessus, nécessitent des ressources importantes en termes de nombre de portes et de profondeur du circuit. Par conséquent, la réalisation de ces circuits nécessiterait nécessairement l'utilisation de codes correcteurs d'erreurs, ce qui augmenterait les ressources nécessaires de plusieurs ordres de grandeur.
Un outil récemment disponible pour l'estimation des ressources de la mise en œuvre tolérante aux pannes des algorithmes quantiques - l'Azure Quantum Resource Estimator - a été appliqué au circuit ci-dessus, ce qui nous a permis de comparer les ressources requises pour la réalisation bruyante "normale" du circuit et sa réalisation tolérante aux pannes. Un code de surface a été utilisé dans cette analyse.
Ressources nécessaires à la mise en œuvre régulière
Notre implémentation du circuit de Beauregard [1] nécessite 4n+2 qubits. Le circuit comprend 4n2 sous-circuits additionneurs modulaires (y compris les circuits inverses). Chaque additionneur modulaire comprend n+1 portes de phase, n+1 portes de cphase, 3(n+1) portes de cphase et en plus 4 fonctions QFT (et QFT inverse). Comme chaque QFT comprend n(n+1)/2 portes de cphase et n portes de Hadamard, le circuit entier comprend :
o $O(n^4)$ portes à cphase
o $O(n^3)$ portes de ccphase, de phase et de Hadamard
o $O(n^2)$ ccx, cx, et x gates.
Résultats de l'estimateur de ressources Azure pour n=4
En utilisant le moteur de modélisation graphique et de synthèse Classiq, l'implémentation Shor a été générée pour n=4 (nécessitant 18 qubits au total) au format QIR. Le circuit comprend les portes de phase suivantes :
o 3 244 portes de phase
o 920 ccphase gates
o 320 portes de phase.
Azure Resource Estimator a été appliqué au circuit avec des arguments par défaut - en supposant un taux d'erreur de 0,001 pour les portes à un et deux qubits, ainsi que pour les portes en T et les mesures à un qubit. L'erreur globale totale requise pour le circuit (budget d'erreur total) était de 0,33.
Selon l'estimateur de ressources, pour respecter ce budget d'erreur, la distance de code de surface requise est d=13 et le taux d'erreur requis pour les qubits logiques est de 5,1 * 10^{-9}$. En outre, 25 usines d'état T (travaillant en parallèle) sont nécessaires. Le taux d'erreur requis pour les états T est de 1,35 * 10^{-7}$.
Le nombre de qubits physiques pour un qubit logique est donné par 2d2 = 338. Le nombre total de qubits logiques dans un circuit tolérant aux pannes est de 16 562 (une disposition planaire du circuit original nécessite 49 qubits, chacun nécessitant 338 qubits physiques). Ces qubits transportent l'information tout au long du calcul. En outre, de nombreux autres qubits sont nécessaires pour générer et distiller les états T par les usines T. Ces états T sont utilisés chaque fois que l'on a besoin d'un état T ou d'un autre. Ces états T sont utilisés chaque fois qu'une porte T est appliquée dans le circuit tolérant aux fautes (c'est-à-dire que les états T interagissent et s'emmêlent avec les qubits du circuit logique, puis les démêlent de manière mesurée des qubits du circuit logique). Pour distiller les états T avec le taux d'erreur requis, il faut 13 520 qubits physiques par état T. Le nombre total de qubits physiques est donc de 1,5 million. Le nombre total de qubits physiques requis pour les états T est donc de 338 000.
Le nombre total de qubits physiques (qubits de l'état T + qubits du circuit) est de 354 562. Il est à noter que les qubits de l'état T sont réutilisés plusieurs fois au cours de l'application du circuit.
Selon les résultats de l'estimateur de ressources, il est important de noter qu'un circuit tolérant aux pannes comprendrait 50 471 rotations de qubits uniques, provenant des différentes portes de phase (y compris cphase et ccphase) dans le circuit d'origine. Ces rotations de qubits simples consommeraient la quasi-totalité des états T requis pour l'ensemble du circuit. Ces résultats suggèrent qu'il serait avantageux de réduire le nombre des différentes portes de phase dans le circuit. Cela peut être réalisé, par exemple, en utilisant les fonctions QFT approximatives (au lieu de la QFT exacte) dans le circuit. Par ailleurs, une implémentation différente de l'algorithme de Shor, qui n'est pas basée sur l'addition dans la base de Fourier mais sur d'autres types de circuits additionneurs, peut également s'avérer avantageuse.
Résumé
Nous avons montré comment les descriptions académiques des algorithmes quantiques peuvent être modélisées de manière formelle, tout en conservant la structure et le mode de pensée de l'algorithme présenté scientifiquement. Dans cet article, nous avons discuté de deux constructions principales de modélisation que nous avons trouvées omniprésentes dans la plupart des algorithmes quantiques : la cascade et les instances. Nous avons constaté qu'un ordre d'environ dix constructions de ce type, toutes simples à comprendre, couvre presque tous les algorithmes publiés à ce jour. Le fait de disposer de telles constructions de modélisation nous permet de combler le fossé entre la présentation scientifique des algorithmes et leur exécution réelle sur du matériel et des simulateurs - en couplant des outils algorithmiques, tels que des synthétiseurs pour construire des circuits concrets à partir du modèle d'algorithme quantique, avec des estimateurs de ressources, tels que l'outil récemment présenté par Microsoft.
Les constructions de modélisation quantique et les fortes capacités de synthèse comblent le fossé entre l'intention des concepteurs d'algorithmes quantiques, telle qu'elle est publiée dans les articles universitaires, et les implémentations réelles qui peuvent être exécutées sur des ordinateurs quantiques, des simulateurs et des estimateurs de ressources.
Introduction
Au cours des trente dernières années, les algorithmes quantiques ont été en grande partie une activité académique. Les théoriciens ont publié des algorithmes bien définis et éprouvés et les ont décrits dans un langage scientifique solide. Cette description comprend des figures, des légendes, du texte, des équations et d'autres outils mis à la disposition des scientifiques pour décrire formellement et prouver l'exactitude de leur travail. Malheureusement, cette description repose sur une compréhension mutuelle entre les chercheurs et est basée sur un langage scientifique formel. Ce langage n'est pas suffisamment formel pour que les compilateurs puissent comprendre et produire une description de l'algorithme quantique exécutable par un ordinateur quantique.
Dans cet article, nous présentons de nouvelles constructions de modélisation et de nouveaux idiomes qui résultent d'un examen approfondi de nombreux algorithmes quantiques et d'implémentations publiés au fil des ans. Même dans des algorithmes aussi singuliers que ceux de Shor, Grover ou HHL - qui peuvent tous être énoncés relativement simplement en faisant abstraction de toute structure interne - une multitude de complexités apparaissent lorsqu'on examine le niveau de détail suivant - l'exponentiation modulaire dans l'algorithme de Shor, l'oracle dans celui de Grover et la forme des équations linéaires dans celui de HHL. Nous suivrons ci-dessous l'exemple de l'algorithme de Shor, car il est le plus simple à comprendre pour quiconque suit un cours d'introduction aux algorithmes quantiques. En utilisant l'estimateur de ressources quantiques Azure de Microsoft, nous montrons que l'exécution de l'algorithme de Shor avec quatre additions modulaires nécessite 354 562 qubits physiques, et nous identifions les nombres de portes spécifiques nécessaires. Dans cet exemple, nous ne montrerons que les constructions de modélisation que nous avons trouvées pertinentes dans un large éventail d'algorithmes quantiques.
La valeur globale de notre méthode est déterminée par le degré de ressemblance du modèle avec le circuit quantique tel qu'il a été décrit par le concepteur, par exemple dans un article universitaire, et par la capacité du modèle à capturer sans ambiguïté toutes les exigences formelles du circuit.
Les constructions de modélisation, ainsi que le moteur de synthèse capable de comprendre formellement le modèle et de produire une mise en œuvre concrète et optimisée du circuit quantique, ont tous été mis en œuvre dans la plateforme de conception d'algorithmes quantiques de Classiq, atteignant ainsi pour la première fois la capacité de créer des algorithmes quantiques complexes, de la pensée à l'exécution. Les algorithmes quantiques (par exemple, les implémentations de l'algorithme de Shor) créés par la plateforme Classiq sont de loin les algorithmes quantiques les plus complexes et les plus grands jamais créés.
Mise en œuvre de l'algorithme de Shor
Nous passons en revue les principaux concepts et outils utilisés dans la modélisation graphique de Classiq pour générer un circuit implémentant l'algorithme de Shor factorisant un nombre N représenté par n bits. Le circuit suit l'implémentation de Beauregard(https://arxiv.org/pdf/quant-ph/0205095 [1]) et nécessite 4n+2 qubits. La différence entre les deux circuits est que le circuit original de Beauregard implémente le circuit QFT inverse final sur un seul qubit en mesurant et en préparant à nouveau un seul qubit 2n fois (ce qui nécessite 2n+3 qubits), alors que notre implémentation utilise la QFT "régulière" sur 2n qubits.
Le circuit met en œuvre la partie quantique de l'algorithme de Shor. Rappelons que dans l'algorithme de Shor, pour trouver un facteur d'un nombre n-qubit donné N, on choisit un nombre aléatoire a plus petit que N et on calcule pgcd(a,N), où pgcd désigne le plus grand dénominateur commun. Si pgcd(a, N) >1, nous avons terminé - pgcd(a,N) est un facteur de N. Sinon, nous effectuons la partie quantique de l'algorithme - dont l'essentiel consiste à calculer $|a^xmodN\rangle$ (la partie quantique est suivie d'un post-traitement classique supplémentaire du résultat mesuré).
Pour construire un tel circuit pour un n donné, il faut pouvoir exprimer le circuit de manière hiérarchique en commençant par les blocs quantiques de base au niveau le plus bas (les blocs quantiques sont des portes et des fonctions de base reconnues par le moteur de synthèse) jusqu'au circuit entier au niveau le plus élevé. En outre, il faut pouvoir travailler avec des registres plutôt qu'avec des qubits individuels, c'est-à-dire appliquer des portes à des registres tout en conservant la possibilité de découper des registres et d'appliquer des portes à des qubits sélectionnés. Les outils qui permettent une telle modélisation d'un circuit sont démontrés dans chacune des principales hiérarchies/couches du circuit qui sont :
- Un additionneur modulaire dans l'espace de Fourier construit à partir de portes de base (principalement des portes à phase, à phase contrôlée et à double phase contrôlée) et de QFT.
- Multiplication modulaire construite à partir de n additionneurs modulaires.
- Exponentiation modulaire construite à partir de n circuits de multiplication modulaire.
Le circuit de l'additionneur modulaire contrôlé
Dans l'additionneur modulaire, le nombre a est ajouté à un registre quantique de (n+1) qubits (le registre b). L'état d'entrée du registre est celui où le bit le plus significatif (MSB) de b a la valeur zéro. Ce qubit est utilisé comme bit de débordement. En outre, le circuit comprend deux bits de contrôle et un bit auxiliaire qui est nul à l'entrée et à la sortie. L'additionneur modulaire est donné par le circuit suivant. La barre noire épaisse distingue l'additionneur (barre de droite) de son inverse, la soustraction (barre de gauche) :
Pour c1=c2=1, le fonctionnement du circuit est le suivant (pour d'autres valeurs de ci, les opérations commandées ne sont pas activées et le reste des opérations s'annule).
o Sous-circuit A : Ajoute a au registre b de (n+1) qubits portant $\Phi(b)$.
o Sub-circuit B: Subtracts N from a+b and then adds N again if N < a+b – this is done by checking the MSB of a+b-N.
$$|1,1,\NPhi (b),0\rangle \Nrightarrow |1,1,\NPhi (b+a),0\rangle$$$
Notez qu'à ce stade, le registre b est dans l'état (a+b)mod N, alors qu'en général, il est enchevêtré avec le qubit auxiliaire.
o Sous-circuit C : réinitialise le dernier qubit auxiliaire à $|0\rangle$ (en le dissociant du registre b) en soustrayant a du registre et en vérifiant le bit le plus significatif du registre b(en retournant le bit auxiliaire si nécessaire) et en ajoutant à nouveau a au registre.
Le fonctionnement de l'ensemble du circuit sur les états d'entrée "légaux" (où le MSB de b est zéro) est requis :
$$|1,1,\NPhi (b),0\rangle \Nrightarrow |1,1,\NPhi ((b+a) mod N),0\rangle .$$$
Le principal élément constitutif de l'additionneur modulaire est un circuit additionneur (dans la base de Fourier), qui ajoute le nombre a (plus petit que N) à un registre quantique de (n+1) qubits, et son inverse (avec et sans contrôle). L'additionneur (non contrôlé) est construit uniquement à partir de portes de phase à qubit unique (ici - $|\Phi(b)\rangle = QFT|b\rangle $) :
Le nombre a est ici "classique" dans le sens où il n'est pas porté par un registre quantique mais encodé dans les phases. Dans notre plateforme, l'additionneur est réalisé directement par l'outil de modélisation en cascade avec lequel une opération est dupliquée verticalement : elle est appliquée à tous les qubits d'un registre, comme illustré ci-dessous (la raison pour laquelle on l'appelle cascade et non, par exemple, forall, apparaîtra plus tard).
L'entrée et la sortie ci-dessus sont des registres de W qubits avec W, un paramètre défini en haut de la hiérarchie, et l'instruction de cascade applique la porte de phase à qubit unique à chaque qubit dans le registre. Une phase différente est introduite dans chacun des qubits. Ces phases sont introduites dans le circuit par l'utilisateur dans le cadre de la modélisation. Les noms de port formels des portes sont target_in et target_out.
Un autre bloc de construction utilisé dans le sous-circuit additionneur modulaire (figure 1) est l'additionneur contrôlé et doublement contrôlé, où les portes de phase sont remplacées par des portes à phase contrôlée (CPhase). Dans cette porte, un seul qubit contrôle les phases des qubits cibles. Pour appliquer une porte de manière répétée au même registre, nous utilisons l'instruction instances. Dans la mise en œuvre de l'additionneur contrôlé, cependant, les phases sont introduites séquentiellement dans tous les qubits du registre cible, et il faut donc utiliser à la fois la cascade (répétition sur les qubits) et les instances (répétition des portes).
Le qubit unique du registre de contrôle participe à toutes les W portes de la phase CP de la séquence, tandis que chacun des W qubits du registre cible participe à une seule porte.
Le schéma complet réalisant le circuit de l'additionneur modulaire de la figure 1 est illustré ci-dessous. Remarquez à quel point ce circuit est similaire au dessin académique de la figure 1, à la différence près, bien sûr, que ce circuit est entièrement exécutable et optimisable jusqu'à la meilleure implémentation concrète grâce au moteur de synthèse.
Le circuit se compose de cinq additionneurs (y compris les additionneurs contrôlés et inversés) et de deux fonctions "twoQFT", qui mettent en œuvre les deux constructions du circuit ci-dessus, en vérifiant le qubit MSB dans le registre b et en inversant le qubit auxiliaire si nécessaire (chacune de ces constructions comprend deux fonctions QFT qui amènent le registre b dans l'espace de Fourier et le quittent). Cette convention de dénomination est illustrée à la figure 5 et expliquée dans la légende ci-dessous.
Le circuit multiplicateur modulaire contrôlé
Le circuit mettant en œuvre la multiplication modulaire peut être construit en répétant n fois la fonction de l'additionneur modulaire, comme indiqué ci-dessous :
Notez que dans la figure 6, les contrôles sur le $\Phi$ADD(2j )mod N ne sont pas complètement "légaux" (bien qu'il soit graphiquement bien défini dans [1] comme le circuit de la figure 1), puisque le contrôle n'est pas appliqué à toutes les portes à l'intérieur du sous-circuit $\Phi$ADD(2j )mod N et que l'évolution contrôlée correcte n'est obtenue que pour les entrées "légales" où le bit de débordement est à 0.
L'ensemble des opérations des n additionneurs modulaires est effectué dans l'espace de Fourier, c'est pourquoi des QFT et QFT inverses supplémentaires sont nécessaires dans et hors de l'espace de Fourier. Ce circuit peut être implémenté directement par le modeleur graphique comme indiqué ci-dessous :
Il convient de noter que le circuit additionneur modulaire (figure 5) reçoit deux registres à qubit unique comme commandes, tandis qu'à la couche supérieure de multiplication (figure 7), le registre c2 comprend n qu bits qui sont ensuite mis en cascade à la couche inférieure d'addition modulaire.
L'exponentiation modulaire est mise en œuvre en répétant la multiplication modulaire 2n fois pour différentes puissances de a . Dans le circuit de multiplication modulaire, le registre b est initialement à l'état 0, et afin de le réutiliser dans chacune des 2n multiplications modulaires, il doit être renvoyé à 0. Cela peut être fait en appliquant une permutation contrôlée entre les registres b et x, puis en appliquant la multiplication modulaire inverse pour la valeur inverse de la puissance de a appropriée.
Exponentiation modulaire
L'exponentiation modulaire est effectuée en entrant le nombre 1 dans le registre b, en préparant un registre de 2n qubits supérieurs (par une transformation de Hadamard) et en appliquant directement la paire de constructions de multiplication modulaire ci-dessus 2n fois - en cascadant le registre de 2n qubits supérieurs de sorte que chaque qubit dans le registre contrôle l'opération de multiplication modulaire appropriée et en appliquant une QFT inverse au registre supérieur (le résultat de la partie quantique est obtenu en mesurant ce registre). L'algorithme de Shor dans son ensemble, dont la principale partie de modélisation est l'exponentiation modulaire, est illustré à la figure 8.
Synthèse
Le moteur de synthèse, qui prend le modèle décrit ci-dessus en entrée et produit un circuit d'implémentation optimal conforme au modèle fonctionnel, dépasse le cadre de cet article. Nous mentionnons seulement ici que pour chaque bloc fonctionnel du modèle, il existe de nombreuses implémentations fonctionnellement équivalentes (par exemple, manifestant les compromis entre le nombre de qubits auxiliaires implémentant le bloc, sa profondeur, le nombre de portes à 2 qubits qu'il contient, et sa précision globale). Le moteur de synthèse a pour tâche de trouver la meilleure implémentation pour le circuit global en fonction d'un budget de qubits, de profondeur, de temps d'exécution, de fidélité globale, de précision algorithmique et d'objectif global. Nous notons également que l'optimisation à ce niveau fonctionnel est beaucoup plus puissante que l'optimisation au niveau du transpondeur, car le transpondeur doit conserver intacte la sémantique de bas niveau du circuit - par opposition à la préservation de la seule sémantique fonctionnelle du circuit lorsqu'il a accès à cette sémantique. Une implémentation finale de l'algorithme de Shor est présentée à la figure 9.
Estimation des ressources pour une réalisation tolérante aux fautes du circuit de Shor
Les circuits mettant en œuvre l'exponentiation modulaire et l'algorithme de Shor, comme la mise en œuvre ci-dessus, nécessitent des ressources importantes en termes de nombre de portes et de profondeur du circuit. Par conséquent, la réalisation de ces circuits nécessiterait nécessairement l'utilisation de codes correcteurs d'erreurs, ce qui augmenterait les ressources nécessaires de plusieurs ordres de grandeur.
Un outil récemment disponible pour l'estimation des ressources de la mise en œuvre tolérante aux pannes des algorithmes quantiques - l'Azure Quantum Resource Estimator - a été appliqué au circuit ci-dessus, ce qui nous a permis de comparer les ressources requises pour la réalisation bruyante "normale" du circuit et sa réalisation tolérante aux pannes. Un code de surface a été utilisé dans cette analyse.
Ressources nécessaires à la mise en œuvre régulière
Notre implémentation du circuit de Beauregard [1] nécessite 4n+2 qubits. Le circuit comprend 4n2 sous-circuits additionneurs modulaires (y compris les circuits inverses). Chaque additionneur modulaire comprend n+1 portes de phase, n+1 portes de cphase, 3(n+1) portes de cphase et en plus 4 fonctions QFT (et QFT inverse). Comme chaque QFT comprend n(n+1)/2 portes de cphase et n portes de Hadamard, le circuit entier comprend :
o $O(n^4)$ portes à cphase
o $O(n^3)$ portes de ccphase, de phase et de Hadamard
o $O(n^2)$ ccx, cx, et x gates.
Résultats de l'estimateur de ressources Azure pour n=4
En utilisant le moteur de modélisation graphique et de synthèse Classiq, l'implémentation Shor a été générée pour n=4 (nécessitant 18 qubits au total) au format QIR. Le circuit comprend les portes de phase suivantes :
o 3 244 portes de phase
o 920 ccphase gates
o 320 portes de phase.
Azure Resource Estimator a été appliqué au circuit avec des arguments par défaut - en supposant un taux d'erreur de 0,001 pour les portes à un et deux qubits, ainsi que pour les portes en T et les mesures à un qubit. L'erreur globale totale requise pour le circuit (budget d'erreur total) était de 0,33.
Selon l'estimateur de ressources, pour respecter ce budget d'erreur, la distance de code de surface requise est d=13 et le taux d'erreur requis pour les qubits logiques est de 5,1 * 10^{-9}$. En outre, 25 usines d'état T (travaillant en parallèle) sont nécessaires. Le taux d'erreur requis pour les états T est de 1,35 * 10^{-7}$.
Le nombre de qubits physiques pour un qubit logique est donné par 2d2 = 338. Le nombre total de qubits logiques dans un circuit tolérant aux pannes est de 16 562 (une disposition planaire du circuit original nécessite 49 qubits, chacun nécessitant 338 qubits physiques). Ces qubits transportent l'information tout au long du calcul. En outre, de nombreux autres qubits sont nécessaires pour générer et distiller les états T par les usines T. Ces états T sont utilisés chaque fois que l'on a besoin d'un état T ou d'un autre. Ces états T sont utilisés chaque fois qu'une porte T est appliquée dans le circuit tolérant aux fautes (c'est-à-dire que les états T interagissent et s'emmêlent avec les qubits du circuit logique, puis les démêlent de manière mesurée des qubits du circuit logique). Pour distiller les états T avec le taux d'erreur requis, il faut 13 520 qubits physiques par état T. Le nombre total de qubits physiques est donc de 1,5 million. Le nombre total de qubits physiques requis pour les états T est donc de 338 000.
Le nombre total de qubits physiques (qubits de l'état T + qubits du circuit) est de 354 562. Il est à noter que les qubits de l'état T sont réutilisés plusieurs fois au cours de l'application du circuit.
Selon les résultats de l'estimateur de ressources, il est important de noter qu'un circuit tolérant aux pannes comprendrait 50 471 rotations de qubits uniques, provenant des différentes portes de phase (y compris cphase et ccphase) dans le circuit d'origine. Ces rotations de qubits simples consommeraient la quasi-totalité des états T requis pour l'ensemble du circuit. Ces résultats suggèrent qu'il serait avantageux de réduire le nombre des différentes portes de phase dans le circuit. Cela peut être réalisé, par exemple, en utilisant les fonctions QFT approximatives (au lieu de la QFT exacte) dans le circuit. Par ailleurs, une implémentation différente de l'algorithme de Shor, qui n'est pas basée sur l'addition dans la base de Fourier mais sur d'autres types de circuits additionneurs, peut également s'avérer avantageuse.
Résumé
Nous avons montré comment les descriptions académiques des algorithmes quantiques peuvent être modélisées de manière formelle, tout en conservant la structure et le mode de pensée de l'algorithme présenté scientifiquement. Dans cet article, nous avons discuté de deux constructions principales de modélisation que nous avons trouvées omniprésentes dans la plupart des algorithmes quantiques : la cascade et les instances. Nous avons constaté qu'un ordre d'environ dix constructions de ce type, toutes simples à comprendre, couvre presque tous les algorithmes publiés à ce jour. Le fait de disposer de telles constructions de modélisation nous permet de combler le fossé entre la présentation scientifique des algorithmes et leur exécution réelle sur du matériel et des simulateurs - en couplant des outils algorithmiques, tels que des synthétiseurs pour construire des circuits concrets à partir du modèle d'algorithme quantique, avec des estimateurs de ressources, tels que l'outil récemment présenté par Microsoft.
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.
