FR 3064380 A1 20180928 FR 1770299 A 20170324 1 Procédé de simulation, sur un ordinateur classique, d'un circuit quantique L'invention a trait au domaine de l'informatique, et plus précisément à la simulation d'un circuit logique quantique au moyen d'un ordinateur structuré de manière classique - c'est-à-dire à l'aide de processeurs comprenant des portes logiques constituées chacune d'un circuit de transistors qui peuvent être traversés par des flux d'électrons. La conception d'un ordinateur (que l'on peut assimiler à un processeur, les deux termes étant ici synonymes) repose généralement sur une phase préalable de simulation algorithmique de son fonctionnement (c'est-à-dire du fonctionnement des circuits logiques qui le composent) pour en prédire d'une manière générale le comportement et, plus particulièrement, les résultats que l'ordinateur fournirait à l'issue de l'exécution d'un programme donné. Les opérations (par ex. addition, soustraction, multiplication) sont effectuées par des combinaisons de portes logiques élémentaires à transistors, qui réalisent des fonctions logiques appliquée à des bits d'entrée (de valeur 0 ou 1) et dont les résultats sont des bits de sortie (de valeur 0 ou 1). Citons à titre d'exemple les fonctions logiques NOT, AND, OR, NOR, NAND. La miniaturisation des transistors, rendue possible par la finesse croissante des procédés gravure des semi-conducteurs, a permis de multiplier la puissance de calcul et la capacité de stockage (ou mémoire) des ordinateurs. Suivant la conjecture (dite Loi) de Moore, la densité des transistors pouvant être gravés sur un semi-conducteur aurait plus ou moins doublé tous les deux ans depuis les années 1960. Tant que les transistors demeurent à l'échelle micrométrique, la physique classique (avec les lois de l'électricité) demeure applicable, et les fonctions réalisées par les portes logiques demeurent déterministes, ce qui permet d'appliquer dans l'algorithmique de simulation une algèbre simple, linéaire. Dans un ordinateur classique (au sens où il comprend des transistors fonctionnant conformément aux lois de l'électricité de la physique classique), la sortie (c'est-à-dire le résultat) d'un programme nécessitant n bits en entrée (chacun de valeur 0 ou 1) peut être modélisé 3064380 2 par un vecteur d'état à 2n composantes, qui représente l'ensemble des valeurs possibles des bits de sortie. On comprend par conséquent que l'ajout d'un bit d'entrée conduit à une multiplication par 2 du nombre de valeurs possibles des bits de 5 sortie. En d'autres termes, toute augmentation linéaire des entrées (ajout de bits) se traduit par une augmentation exponentielle de la capacité de calcul (et/ou de mémoire) requise. Compte tenu des besoins applicatifs croissants (par ex. médecine assistée par ordinateur, conduite des véhicules autonomes, traitement 10 de l'image à haute définition), la miniaturisation des circuits logiques se poursuit, et l'on atteint à présent les échelles nanométriques et même atomiques. A ces échelles, l'information n'est plus véhiculée par des flux électriques dont le comportement peut être déterminé et prédit par les 15 lois de la physique classique, mais par des particules (ou quanta) dont le comportement, en grande partie probabiliste, répond aux lois de la physique quantique. Dans un ordinateur quantique, c'est le qubit (contraction de quantum bit) qui représente l'unité élémentaire de stockage de l'information, par 20 analogie au bit qui, lui, représente l'unité élémentaire de stockage de l'information dans un ordinateur classique. Si la valeur d'un bit est toujours - et en permanence - de 0 ou 1 selon l'opération qui lui est appliquée (identité : 0 ou 1 1 ; NOT : 1 ou 1 0), la valeur d'un qubit est quant à elle indéterminée car 25 probabiliste. Une définition assez claire du qubit est proposée par Benenti et al, Principles of Quantum Computation and Information, Volume I Basic Concepts, World Scientific Publishing Co, 2004. Selon cette définition, un qubit est un système quantique dont l'état est décrit par une fonction 30 d'onde p, notée 11p) selon le formalisme bra-ket de Dirac, dans un espace de Hilbert. La fonction d'onde 11p) s'écrit sous forme d'une combinaison linéaire des valeurs possibles du qubit : 11p) = al0)+fi11) Où 10) et 11) représentent les valeurs 0 et 1 (ou état de base) d'un bit 35 classique, et où les coefficients a et fi, dénommés « amplitudes de 3064380 3 probabilité », sont des nombres complexes normalisés selon la relation suivante : 1cr12 if312 = D'un point de vue géométrique, un qubit peut être représenté par un 5 point positionné à la surface d'une sphère dite de Bloch (de rayon 1), dont les coordonnées sphériques sont 0 (0 0 ir) et .1) (0 .1) 27t). Dans ces conditions, l'état Ftp) du qubit peut s'écrire sous forme de l'équation suivante : 0 . 0 IV)) = cosi 10) + e'0 sin-2 11) 10 ...ou sous forme du vecteur d'état suivant : cos = e'0 sin- 2i Ces équations témoignent, contre-intuitivement, d'une continuité d'état du qubit, qui peut prendre une infinité d'états - tant qu'il n'est pas mesuré : dès lors sa valeur est déterminée (0 ou 1). Cette continuité fait 15 qu'en théorie un unique qubit est susceptible de stocker une quantité infinie d'information, ce qui laisse espérer pour l'ordinateur quantique des performances particulièrement intéressantes en termes de calcul et de stockage, alors même que sa compacité le rend attractif en tant qu' objet. 20 Cependant les lois de la mécanique quantique figent l'état du qubit dès sa lecture ; il est impossible de remonter aux valeurs des amplitudes a et fi, et donc impossible de connaître l'état instantané du qubit. Dans l'état actuel des connaissances, les qubits sont destinés à être utilisés d'une manière analogue aux bits classiques, c'est-à-dire à être 25 combinés en un registre de n qubits (n un entier) susceptibles d'être traités au sein d'un programme informatique. L'état de n qubits est décrit par une fonction d'onde Ilp) généralisée dans un espace de Hilbert à 2n dimensions : 2n-1 IP)_ ai li) i=0 30 Où Ii) représente les valeurs possibles (ou états de base) des combinaisons de bits classiques, et où les coefficients ai sont les 3064380 4 amplitudes de probabilité de chaque valeur, normalisés selon la relation suivante : 2n-1 iat 12 = 1 i=0 Ainsi, pour deux qubits (n = 2) : 5 11P) = ao100) + oti101) + ot2110) + ot3111) Avec : 1%12 + 1a112 + 10(212 + 1a312 = 1 A la différence d'un ordinateur classique traitant un unique état du registre parmi l'ensemble de ses états possibles, l'ordinateur quantique 10 est en théorie capable de traiter simultanément l'ensemble des états possibles du registre, soit 2n. En d'autres termes, l'ordinateur quantique effectue par nature ses calculs en parallèle. Il en découle que l'addition d'un qubit multiplie par 2 la puissance de calcul de l'ordinateur, celle-ci étant donc une fonction exponentielle de la taille du registre. Pour fixer 15 les idées, il suffit d'indiquer que pour n = 300 (soit 300 qubits), la taille du registre - et donc le nombre d'états (caractérisant chacun une information) de celui-ci que peut traiter simultanément l'ordinateur - est de 2330 1090, ce qui correspond au nombre estimé de particules dans notre univers observable. 20 Dans un avenir proche, et de manière réaliste, il est attendu des ordinateurs quantiques qu'ils puissent résoudre des problèmes actuellement insolubles par les ordinateurs classiques en raison de la capacité de calcul déraisonnable qu'il serait nécessaire de mobiliser - et du temps de calcul requis. 25 Un exemple bien connu de problème mathématique que les algorithmes classiques tournant sur les ordinateurs classiques ne parviennent à résoudre en des temps raisonnables est la factorisation d'un entier naturel N (typiquement 15 = 3x5). C'est cette relative incapacité des ordinateurs classiques à résoudre le problème de la 30 factorisation qui a rendu exploitable la cryptographie à chiffrement RSA (Rivest-Shamir-Aldeman), dont la génération des clés publiques repose en effet sur le produit de nombres entiers. L'algorithme quantique de Shor (cf. par ex. une présentation de cet algorithme dans Lomonaco, Shor's Quantum Factoring Algorithm, 35 Proceedings of Symposia in Applied Mathematics, Université du 3064380 5 Maryland, 2000) permet - en théorie - de résoudre le problème de la factorisation d'un entier naturel N en un temps dont l'ordre de grandeur est asymptotiquement algorithmique, c'est-à-dire (en notation dite « grand O » de Landau), de l'ordre de 0(log(N)). L'algorithme de Shore 5 repose sur l'utilisation d'une transformée de Fourier quantique, dont l'efficacité est très supérieure à celle des transformées de Fourier classiques. On voit donc l'intérêt qu'il y a à modéliser dès à présent, sur des ordinateurs classiques, les circuits logiques quantiques. Cependant le 10 l'espace mémoire et la puissance de calcul sont des facteurs limitants. Ainsi, une modélisation connue d'un circuit logique quantique à n qubits consiste à représenter mathématiquement ce circuit par une matrice (notée U, dite matrice opération - en anglais : Operation Matrix) de taille 2nx2n et qui, appliquée à un vecteur d'état E initial de taille 2n, 15 fournit en sortie un vecteur d'état final E', également de taille 2n et produit matriciel de E par U : E' =U - E Cette modélisation est testée notamment dans Gerdt et al, A Mathematica Program for Constructing Quantum Circuits and Computing 20 Their Unitary Matrices, Workshop on Quantum Physics and Communication, Oct. 2007. Cependant Patrzyk et al, Towards a Novel Environment for Simulation of Quantum Computing, Computer Science 16(1)2015, 103129, a évalué la capacité mémoire (correspondant au nombre de bits 25 pouvant être stockés dans la mémoire) nécessaire, pour un ordinateur classique, à la simulation d'un nombre donnés de qubits (et plus précisément au stockage de la matrice opération), et fourni une liste d'exemples numériques intéressants présentés dans le tableau (Table 1 p.106) reproduit ci-après (la mémoire est indiquée en Bytes (octets) ; les 30 préfixes k, M et T correspondant respectivement aux opérateurs kilo, mega et Tera) : Nombre de qubits 5 10 20 21 Mémoire (vecteur d'état) 512 B 16kB 16MB 32MB Mémoire (Matrice d'opération) 16B 16MB 16TB 64TB 3064380 6 L'on peut montrer que, si l'on note N la capacité mémoire d'un ordinateur classique nécessaire au stockage de la matrice opération U, le nombre maximum, noté nm, de qubits simulables n'est pas supérieur à: 5 log(N) 2log(2) Une technique connue, pour limiter la capacité mémoire nécessaire au calcul (ou, à capacité mémoire équivalente, pour augmenter le nombre nm de qubits simulables), consiste à une effectuer une approximation de la matrice opération U en réduisant sa dimension au moyen d'une 10 décomposition dite de Schmidt, dont la méthodologie est notamment décrite dans l'ouvrage de référence A. Nielsen & I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 10th Anniversary Edition, 2010, p.109 et suivantes. Mais on constate en pratique que, si cette approximation peut fournir des résultats 15 acceptables pour quelques circuits quantiques simples (par ex. pour une porte logique de type AND), elle manque cruellement de robustesse pour des circuits plus complexes (par ex. pour un circuit de Transformée de Fourrier quantique). Samad et Al, Memory Efficient Quantum Circuit Simulator Based on 20 Linked List Architecture, 2005, propose de s'affranchir d'une mémorisation complète de la matrice (notée U ci-dessus) du circuit logique quantique en prétendant subdiviser celle-ci en colonnes et en effectuant successivement le produit scalaire de chaque colonne avec le vecteur d'état représentant les qubits d'entrée, les colonnes étant 25 progressivement effacées de la mémoire au fur et à mesure qu'est réalisé leur produit scalaire (cf. Efficient implementation, p. 4-5). Cependant, bien que prétendant avoir appliqué avec succès cette méthode à l'algorithme de Shor, et bien que prétendant en outre avoir été capable de simuler 20 qubits en un temps raisonnable, Samad ne détaille 30 nullement cette méthode. On voit par conséquent que le besoin persiste d'une simulation (tournant sur un ordinateur classique) de circuit quantique, capable, par comparaison aux simulations connues, de meilleures performances, et plus précisément capable de rendre compte de l'état : 35 soit d'un plus grand nombre de qubits à capacité mémoire équivalente, 3064380 7 soit d'un même nombre de qubits à capacité mémoire plus raisonnable. A cet effet, il est proposé un procédé de simulation, sur une unité de traitement informatique à circuit intégré sur semi-conducteur, du 5 fonctionnement d'un modèle de circuit quantique configuré pour traiter un nombre prédéfini n (n un entier tel que n 2) de qubits en entrée et comprenant une série de d (d un entier tel que d 2) portes quantiques Gk (k un entier, 1 k d) élémentaires sélectionnées parmi une bibliothèque de modèles prédéfinis de portes quantiques stockés dans 10 une mémoire à circuit intégré sur semi-conducteur, chaque modèle de porte quantique étant associé à une matrice Uk de transfert comprenant des opérateurs ordonnés en lignes et colonnes et définissant l'ensemble des transitions d'état possibles de qubits transitant par cette porte, ce procédé comprenant : 15 - une phase de configuration du circuit quantique, qui comprend les opérations consistant à ; o définir le nombre n de qubits à traiter en entrée du modèle de circuit quantique ; o sélectionner les d modèles de portes quantiques ; 20 o agencer les d modèles de portes quantiques ainsi sélectionnés pour constituer le modèle de circuit quantique ; une phase d'analyse du modèle de circuit quantique ainsi configuré, qui comprend les opérations consistant à : o diviser le circuit quantique en d couches Lk adjacentes 25 destinées à être traversées successivement par les n qubits pris ensemble, chaque couche comprenant une unique porte quantique ; o attribuer à chaque porte quantique du circuit un type parmi trois types prédéfinis de portes quantiques : 30 - Porte de type diagonal, dont la matrice de transfert est diagonale ; - Porte de type classique, dont la matrice de transfert est non diagonale et comprend des opérateurs valant 0 ou 1 à raison d'un unique opérateur par ligne et par colonne ; 35 - Porte de type dense, qui n'est ni de type classique ni de type diagonal ; 3064380 8 Une phase de calcul, qui comprend la répétition, pour j= 1 à j= 2n (j un entier) des opérations suivantes : a) définir un vecteur km d'état des n qubits à l'entrée du circuit quantique, qui comprend une série de 2n coefficients 5 d'amplitude ail (i un entier, 0 i 2n - 1) valant 0 ou 1, et tels que : 2n-1 keij =1 i=0 b) répéter, pour k = 1 à k = d, la séquence suivante : b1) prendre en compte un vecteur lek) d'état des n qubits à 10 l'entrée de la couche Lk, ce vecteur bp",) comprenant une série de 2n coefficients d'amplitude Ce ; b2) identifier la porte Gk comprise dans la couche Lk ; b3) prendre en compte le type de la porte Gk ; b4) si la porte Gk est de type diagonal, attribuer au vecteur 15 Ilp",+i) d'état des n qubits sortant de la couche Lk la valeur du vecteur 11p1,) d'état des n qubits entrant dans celle-ci : 11P+i) = 11Pij) b5) si la porte Gk est de type classique : o détecter dans sa matrice de transfert chaque 20 opérateur valant 1 et déterminer son numéro l de ligne et son numéro c de colonne (/ et c des entiers tels que 0 / 2n, 0 C 2n et / c) ; o attribuer aux coefficients d'amplitude aj,k+1 du vecteur bp",+i) d'état des n qubits sortant de la couche 25 Lk les valeurs suivantes : j,k+1 j,k a = ai pour tout i # j,k+1 j,k a1 = a o mémoriser le vecteur Ltp",+i) dans un registre dédié d'une mémoire à circuit intégré sur semi-conducteur ; 30 b6) si la porte Gk est de type dense : 3064380 9 o déterminer l'ensemble des valeurs possibles du vecteur Ilp",+1) d'état des n qubits sortant de la couche Lk tel que : 11P+1) = Uk -11Pi) 5 o mémoriser chaque valeur possible du vecteur I",+1) dans un registre dédié d'une mémoire à circuit intégré sur semi-conducteur ; c) agréger, dans un registre unique d'une mémoire à circuit intégré sur semi-conducteur, l'ensemble des états possibles du 10 vecteur Ilp'i+1). Cette méthode permet de simuler avec plus d'efficacité (c'est-à-dire plus rapidement, et en mobilisant un moindre espace mémoire) un circuit quantique, par comparaison aux méthodes connues. L'invention va à présent être détaillée dans la description d'un mode 15 de réalisation, faite ci-après en référence aux dessins annexés dans lesquels : la FIG.1 est une représentation schématique d'un exemple de porte logique quantique de type diagonal, associé à un graphe de transition d'état de qubits transitant par cette porte ; 20 - la FIG.2 est une représentation schématique d'un exemple de porte logique quantique de type classique, associé à un graphe de transition d'état de qubits transitant par cette porte ; la FIG.3 est une représentation schématique d'un exemple de porte logique quantique de type dense, associé à un graphe de transition 25 d'état de qubits transitant par cette porte ; la FIG.4 est une représentation schématique d'un exemple de circuit logique quantique comprenant une série de portes logiques quantiques, associé à un graphe des transitions d'états de qubits traversant successivement ces portes logiques. 30 L'on souhaite simuler, sur une unité de traitement informatique à circuit intégré sur semi-conducteur, le fonctionnement d'un modèle (quelconque) de circuit quantique configuré pour traiter un nombre prédéfini n de qubits en entrée de ce circuit. L'expression « unité de traitement informatique à circuit intégré sur 35 semi-conducteur » désigne tout processeur (également dénommé microprocesseur) comprenant des ensembles de transistors obtenus 3064380 10 selon les techniques classiques de purification, gravure, dopage des matériaux semi-conducteurs (tel que le silicium) et aptes chacun à être traversé (ou non, selon l'état du transistor) par un flux de courant électrique pouvant être modélisé par les lois de la physique classique 5 (notamment la loi d'Ohm). Un transistor fournit, en sortie, un signal dont la valeur, déterminée par l'état du transistor, est égale par convention à 0 ou 1. Cette valeur est allouée à une unité de numération binaire appelée bit, base du codage des ordinateurs classiques actuellement connus (et utilisés) du grand 10 public. Les avancées théoriques permises notamment par Hilbert, Dirac et Schreidinger ont ouvert un champ d'investigation visant à concevoir un ordinateur quantique, c'est-à-dire un ordinateur dont le composant de base serait miniaturisé à l'échelle nanométrique voire atomique, et ne 15 verrait à cette échelle plus transiter des flux de courant comme le transistor que l'on connaît, mais des électrons à l'unité, qui fournissent chacun la valeur d'un bit (0 ou 1). Comme l'électron, considéré seul, a un comportement qui n'obéit plus aux lois classiques de la physique mais aux lois de la mécanique 20 quantique, probabilistes par nature, le composant en question fournit en sortie un signal dont la valeur est indéterminée mais qu'il est cependant possible de décrire au moyen des outils mathématiques développés pour la mécanique quantique, et notamment au moyen de l'équation relatant l'état (ou fonction d'onde) dit de superposition dans lequel se trouve la 25 particule (ici l'électron). On n'expliquera pas ici la nature exacte des phénomènes physiques à l'ceuvre (notamment s'agissant du spin, de la position et de la quantité de mouvement de l'électron), car cela non seulement est hors sujet, mais en outre demeure débattu dans la communauté scientifique. 30 On introduira cependant certaines notions physiques et mathématiques nécessaires à une explication raisonnée de la méthode de simulation proposée, qui permettent en outre de comprendre en quoi cette méthode présente de meilleures performances que les méthodes de simulation connues. 35 On reprend ici les conventions de notation adoptées par la littérature (voir les références mentionnées en introduction). Ainsi, on note Iii) la 3064380 11 fonction d'onde (en notation bra-ket de Dirac) décrivant l'état de la particule, ou des particules comme nous le verrons. En dimension 2, pour une particule simple appelée qubit susceptible de fournir deux valeurs (0 et 1), la fonction d'onde (ou état) du qubit 5 s'écrit : Itp) = a10) + fl11) 10) et 11) représentent, en notation bra-ket, les valeurs 0 et 1 (ou état de base) d'un bit classique, tout exprimant le fait que ces valeurs sont des valeurs probables (et non certaines) pouvant être adoptées par le 10 qubit, étant entendu que, conformément aux lois de la mécanique quantique, toute mesure effectuée sur un qubit (correspondant à une particule) fixe définitivement son état. a et fi, dénommés « amplitudes de probabilité » ou « coefficients d'amplitude », sont des nombres complexes qui relatent chacun la 15 probabilité d'occurrence de la valeur correspondante (respectivement 10) pour a et 11) pour /3). a et fl vérifient la relation dite de « normalisation » suivante : 1cr12 + if312 = 1 La fonction d'onde hp) (ou état) du qubit unitaire peut également 20 s'écrire sous forme d'un vecteur (matrice colonne) : 11P) = (afi) Dans cette notation, les états 10) et 11) s'écrivent de la manière suivante : Io) (0) 25 11) = (i) L'on pourrait se limiter à l'étude d'un unique qubit, puisque celui-ci est en théorie susceptible, aux dires de la littérature, de stocker une quantité infinie d'informations. Cependant, comme il est par nature impossible, à partir de la valeur 30 constatée (c'est-à-dire mesurée) d'un qubit, de déterminer sa (ses) valeur(s) initiale(s), on considère généralement, dans les recherches effectuées sur le comportement de l'ordinateur quantique, un nombre n (n un entier tel que n 2) de qubits pris ensemble, dont on cherche à déterminer l'état global par une fonction d'onde hp) généralisée. 3064380 12 Dans un espace Hilbertien de dimension n la fonction d'onde (ou état) [tp) s'écrit : 2n-1 = ai li) i=0 li) représente, en notation bra-ket (notation de Dirac) et en binaire, 5 les valeurs possibles (ou états de base) des combinaisons de bits classiques. Les coefficients ai sont les amplitudes de probabilité (ou coefficients d'amplitude) d'occurrence de chacune de ces valeurs ; ce sont des nombres complexes (au sens mathématique du terme), qui vérifient 10 ensemble la relation suivante : 2n-1 latI2 = 1 t=0 Avec, pour tout i : ai E {0; 1} Nous avons déjà présenté la fonction d'onde [tp) appliquée à un 15 unique qubit. Pour ce cas très simple, observons simplement, pour clarifier les notations, que ao est noté a et a1 noté fi. Pour deux qubits (n = 2) : Ltp)= a0100)+ a1l01) +a2110)+a3111) Avec : 20 1002 + 1a112 + 10(212 + 1a312 = 1 En notation vectorielle : 7a°) a1 a2 \a3 Pour trois qubits (n = 3) : = ao1000)+a11001)+ a21010)+ a31011)+a41100)+ a51101)+a61110)+a71111) 25 Avec : 10(012 + 1a112 + 10(212 + 1a312 + 1a412 + 1a512 + 1a612 + 1a712 = 1 En notation vectorielle : 3064380 13 te° \ a1 11P) = \a7/ Comme nous le verrons ci-après, la méthode de simulation d'un circuit quantique que l'on va décrire repose non sur une approche calculatoire tenant compte des notations complexes des coefficients ai 5 d'amplitude, mais sur une approche combinatoire qui tient compte de l'ensemble des valeurs possibles que peut prendre le vecteur d'état 11p) (c'est-à-dire la fonction d'onde) tout en éliminant les valeurs improbables de ce vecteur d'état 11p) au fur et à mesure de la progression des qubits au travers du circuit quantique. 10 A titre liminaire, observons que, pour deux qubits (n = 2, voir ci- dessus), les valeurs possibles que peut prendre 11p) sont : /1\ /0\ /00\ /00\ 0 0 1 ' 0 \Oi \Oi \Oi \1i ...qui correspondent respectivement au valeurs suivantes des deux qubits pris ensemble : 15 100) ;101) ;110) ;111) Pour trois qubits (n = 3, voir ci-dessus), les valeurs possibles que 700\ 700\ 700\ 700\ a2 a3 a4 a5 6 peut prendre 11p) sont : /0\ /00\ /00\ \ 1 /0 0 0 1 0 0 0 0 1 0 ' 0 ' 0 ' 0 0 0 0 0 0 0 0 0 \ol \ol \ol \ol 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 \ol \I31/ ...qui correspondent respectivement aux valeurs suivantes des trois 20 qubits pris ensemble : 1000) ; 1001) ; 1010) ; 1011) ; 1100) ; 1101) ; 1110) ; 1111) Un circuit quantique modifie la valeur du ou des 2r1 qubits qui le traverse(nt). Par convention, et pour la suite de l'exposé, on note 11p) l'état des 25 qubits entrant dans le circuit et Iii') l'état des qubits qui en sortent. 3064380 14 Ftp) et IP') sont liés par une fonction de transfert, opérée par le circuit quantique et décrite par une relation matricielle : = u - 11P) Où U est une matrice, dite de transfert, de taille 2nx2n, correspondant 5 à la fonction de transfert appliquée par le circuit quantique aux qubits entrants. La matrice de transfert U comprend des opérateurs uxy (x et y des entiers, 0 x 2n - 1, 0 y 2n - 1) qui se présentent sous forme de nombres complexes (au sens mathématique du terme). La matrice de transfert U représente l'ensemble des opérations appliquées par le circuit 10 quantique aux qubits entrants, tels que décrits par leur vecteur d'état hp). En notant : ao 11P) = a2n-i ai° = C112n -1 U= ( U00 U0(2n-1) 11(2n -1)0 - - - 11(2n-1)(2n-1) 15 ...on peut écrire comme suit la relation entre hp') et Ilp) : ( ( u00 u0(2n_i) ao '5112n-2 u(2n-1)0 X 11(2n-1)(2n-1) C12n-2 Dénombrer, même en algèbre linéaire, l'ensemble des états possibles des qubits en sortie du circuit, requiert pour un ordinateur classique des ressources très importantes dès lors que le nombre de 20 qubits entrants est élevé. En fait, l'espace mémoire nécessaire croît exponentiellement avec le nombre de qubits à traiter. On souhaite donc éviter de devoir constituer entièrement la matrice de transfert U (correspondant au circuit quantique étudié) et de devoir effectuer le calcul matriciel IO = U-11p). 25 A cet effet, les inventeurs ont eu, en premier lieu, l'idée de subdiviser le circuit quantique en plusieurs couches successives adjacentes, par lesquelles transitent l'ensemble des qubits entrant dans le circuit et contenant chacune une porte logique quantique élémentaire prédéterminée effectuant chacune une opération également 30 prédéterminée sur un ou plusieurs des qubits entrant dans la couche (mais pas nécessairement sur la totalité d'entre eux). 3064380 15 On note d (d un entier tel que d 2) le nombre de portes logiques quantiques élémentaires du circuit. On décrète que d 2 car une porte logique élémentaire correspond à une opération matricielle simple dont le résultat est aisément résolu par les simulations connues. 5 On note k l'indice de chaque couche (k un entier tel que 1 k d), que l'on affecte à la lettre L pour désigner par Lk la eine couche et à la lettre G pour désigner par Gk la eine porte logique unitaire, contenue dans la couche Lk. La littérature (cf. par ex. Nielsen & Chuang, op.cit.) a défini un 10 certain nombre de modèles de portes logiques quantiques élémentaires, chacune associée à une matrice de transfert déterminée. Citons à titre d'exemple : la porte d'Hadamard, notée H, qui applique sa fonction de transfert à un unique qubit et est définie comme suit : 15 H (1 1 V7 -1) les portes de Pauli, notées X (ou NOT), Y et Z, qui appliquent leurs fonctions de transfert (respectivement une permutation et deux rotations d'angle 7r), à un unique qubit et sont respectivement définies comme suit : 20 X (NOT) A Cl 0) Y A 0 -i) 0 ) ( Z A 1 0) 0 -1) la porte « Controlled-NOT », notée CNOT, qui applique sa fonction de transfert (une inversion) à deux qubits et est définie comme suit : /1 0 0 0\ 0 1 0 0 1 25 CNOT A `0 0 0 1 \O 0 1 0/ la porte SWAP (ou qSWAP), qui applique sa fonction de transfert (une permutation) à deux qubits et est définie comme suit : /1 0 0 0\ 0 0 1 01 0 1 0 0 4 0 0 1/ la porte de phase contrôlée, notée Ro, associée à un angle noté 0 30 (dans la notation employée pour décrire le qubit sur la sphère de qSWAP 3064380 16 Bloch), qui applique sa fonction de transfert (une rotation d'angle 0) à un unique qubit et est définie comme suit : Ro /1 0 0 4 0 1 0 0 0 0 1 0 0\ 0 1 0 e'l'i Pour faciliter la simulation d'un circuit quantique quelconque, les 5 inventeurs ont, en deuxième lieu, eu l'idée de classifier les différents modèles de portes élémentaires (pouvant servir à configurer le circuit quantique) en trois types : - Porte de type diagonal, dont la matrice est diagonale ; - Porte de type classique, dont la matrice est non diagonale 10 et comprend des opérateurs valant 0 ou 1 à raison d'un unique opérateur égal à 1 par ligne et par colonne ; - Porte de type dense, qui n'est ni de type classique ni de type diagonal. Selon cette classification : 15 - Z, Ro, notamment, sont des portes de type diagonal ; - X, Y, CNOT, SWAP, notamment, sont des portes de type classique ; - H, notamment, est une porte de type dense. Pour faciliter encore la simulation, les inventeurs ont, en troisième 20 lieu, eu l'idée de minimiser les opérations effectuées sur les qubits transitant par chaque couche Lk du circuit quantique, en simplifiant autant que possible les calculs résultant de l'application de la fonction de transfert réalisée par la porte logique élémentaire Gk résidant dans cette couche, en partant du triple postulat suivant : 25 Pour tout vecteur hpk) d'état des n qubits entrant dans la porte, considéré selon ses valeurs possibles - c'est-à-dire que le vecteur hpk) d'état se présente sous forme d'une matrice colonne comprenant 2n - 1 coefficients de coefficients d'amplitude de valeur 0 et un unique coefficient d'amplitude de valeur 1 (voir les exemples fournis ci- 30 dessous) : 1) Une porte logique de type diagonal ne modifie pas la valeur du vecteur d'état (considéré selon ses valeurs possibles) - c'est notamment le cas de la porte de Pauli Z et des portes de phase 3064380 17 contrôlée Ro, car une matrice diagonale n'affecte pas la valeur des coefficients d'amplitude du vecteur d'état des qubits entrants ; 2) Une porte logique de type classique effectue une unique transformation possible du vecteur d'état Ipk) des qubits entrants 5 - c'est notamment le cas des portes X (NOT), Y, CNOT et SWAP - car une matrice non diagonale comprenant des opérateurs valant 0 ou 1 à raison d'un unique opérateur égal à 1 par ligne et par colonne effectue un déplacement du coefficient ac d'amplitude de valeur 1, depuis le rang i = c où se trouve ce coefficient dans le vecteur 10 d'état Ipk) des qubits entrants), vers le rang / dans le vecteur d'état hpk+1) des qubits sortant ; 3) Une porte logique de type dense effectue plusieurs transformations possibles du vecteur d'état hpk) des qubits entrants - c'est notamment le cas de la matrice H, car sa matrice comprend des 15 valeurs non nulles sur au moins une ligne et/ou une colonne. Ce triple postulat permet de simplifier considérablement les calculs lors de la simulation du passage de chaque porte par les n qubits, car il permet d'éliminer - c'est-à-dire de ne pas prendre en compte - les valeurs improbables du vecteur d'état Itpk+i) en sortie de la porte, pour 20 ne retenir (et mémoriser dans un registre de mémoire dédié) que les valeurs probables. Pour l'illustrer, appliquons ce postulat pour chaque type de porte logique, en référence respectivement aux FIG.1, FIG.2 et FIG.3 sur lesquelles on a représenté diverses portes quantiques élémentaires en 25 employant les règles de représentation connues (décrites notamment dans Nielsen & Chuang, op.cit.), selon lesquelles le cheminement de chaque qubit est représenté par une ligne horizontale, et chaque porte quantique élémentaire est superposée sur une ligne. Un trait vertical aboutissant à un point sur une autre ligne que celle sur laquelle se trouve 30 la porte signifie que la celle-ci est contrôlée par le qubit représenté par cette autre ligne. On a représenté sur la FIG.1 un circuit comprenant une unique porte quantique élémentaire de type diagonal traversée par un unique qubit : il s'agit d'une phase contrôlée Rit, qui applique au qubit qui la traverse une 2 35 rotation d'angle 2. 3064380 18 On a représenté sous la porte, dans des cases superposées, les quatre états possibles des qubits d'entrée : 100), IO 1), 110) et 111), et, à même hauteur, les quatre états possibles des qubits de sortie : 100), IO 1), 110) et 11 1). 5 Si l'état d'entrée est 100), alors la seule valeur possible de l'état de sortie est également 100), les autres valeurs possibles, IO 1), 110) et 111), étant improbables et pouvant être ignorées : les cases correspondantes sont à cet effet grisées pour illustrer l'abandon de ces hypothèses de calcul. 10 On a représenté à titre d'illustration la transition d'état 10) 10) par une flèche horizontale, qui signifie que la porte quantique considérée ne modifie pas la valeur des qubits traités. On a représenté sur la FIG.2 un circuit comprenant une unique porte quantique élémentaire de type classique, traversée par un unique qubit : 15 il s'agit ici d'une porte X. On a représenté sous la porte, dans des cases superposées, les deux états possibles du qubit d'entrée : 10) et Il), et, à même hauteur, les deux valeurs possibles du qubit de sortie : 10) et I1). Si l'état du qubit d'entrée est 10), alors le seul état possible du qubit 20 de sortie est Il), l'autre valeur possible, 10), étant improbable et pouvant être ignorée : la case correspondante apparaît grisée. Inversement, si l'état du qubit d'entrée était Il), alors le seul état possible du qubit de sortie serait de 10), l'autre état possible, Il), étant improbable (et pouvant être ignoré). 25 On a représenté à titre d'illustration la transition d'état 10) Il) par une flèche oblique, qui signifie que la porte quantique considérée modifie l'état du qubit entrant en lui assignant le seul autre état possible. On a représenté sur la FIG.3 un circuit comprenant une unique porte quantique élémentaire de type dense, traversée par un unique qubit : il 30 s'agit ici d'une porte H (Hadamard). On a représenté sous la porte, dans des cases superposées, les deux états possibles du qubit d'entrée : 10) et 11), et, à même hauteur, les deux valeurs possibles du qubit de sortie : 10) et I1). Quelle que soit l'état du qubit d'entrée, 10) ou 11), il est équiprobable 35 que son état de sortie soit 10) (état inchangé) ou 11) (état modifié). 3064380 19 En supposant l'état du qubit d'entrée à 10), on a représenté à titre d'illustration les deux transitions d'état possibles par deux flèches partant de la case 10) : l'une horizontale vers 10), signifiant la possibilité d'un maintien de l'état du qubit, l'autre oblique vers 11), signifiant la 5 possibilité de changement de l'état du qubit. Ces conventions d'illustration permettent d'illustrer sous forme d'un graphe le procédé de simulation employé, que l'on décrit à présent de manière détaillée en référence à un exemple représenté sur la FIG.4. On fait la supposition qu'avant d'entamer la simulation, on dispose 10 d'une bibliothèque de modèles prédéfinis de portes quantiques stockés dans une mémoire à circuit intégré sur semi-conducteur, chaque modèle de porte quantique étant associé à une matrice Uk de transfert comprenant des opérateurs ordonnés en lignes et colonnes et définissant l'ensemble des transitions d'état possibles de qubits transitant par cette 15 porte. La simulation comprend une première phase de configuration, qui comprend les opérations consistant à : o définir le nombre n de qubits à traiter en entrée du modèle de circuit quantique - par exemple n = 3 ; 20 o sélectionner les d modèles de portes quantiques, par ex. trois portes d'Hadamard, deux portes Rit et une porte Rit ; 2 4 o agencer les d modèles de portes quantiques ainsi sélectionnés pour constituer le modèle de circuit quantique - par exemple, comme illustré sur la FIG.4, un circuit modélisant une 25 transformée de Fourrier rapide quantique (QFFT : Quantum Fast Fourrier Transform). Une fois ainsi configuré le circuit quantique à simuler, la simulation comprend une deuxième phase d'analyse du modèle de circuit quantique ainsi configuré, qui comprend les opérations consistant à : 30 o diviser le circuit quantique en d couches Lk adjacentes destinées à être traversées successivement par les n qubits pris ensemble, chaque couche comprenant une unique porte quantique Gk élémentaire - ainsi, dans l'exemple de la FIG.4, où d = 6 : 35 L1 A G1 = H L2 A G2 = Rit 2 3064380 20 L3 A G3 = H L4 A G4 = Rit 4 L5 A G5 = Rit 2 L6 A G6 = H 5 o attribuer à chaque porte quantique du circuit un type parmi trois types prédéfinis de portes quantiques : - Porte de type diagonal, dont la matrice est diagonale - il en va ainsi, dans l'exemple de la FIG.4, de G2, G4 et G5 ; - Porte de type classique, dont la matrice est non diagonale 10 et comprend des opérateurs valant 0 ou 1 à raison d'un unique opérateur par ligne et par colonne (aucune porte concernée dans l'exemple de la FIG.4) ; - Porte de type dense, qui n'est ni de type classique ni de type diagonal - il en va ainsi, dans l'exemple de la FIG.4, 15 de G1, G3 et G6. Une fois cette analyse achevée, la simulation comprend une troisième phase de calcul, qui comprend la répétition, pour j = 1 à j= 2r1 (j un entier ; dans l'exemple de la FIG.4, n = 3 de sorte que j varie de 1 à 23 = 8) des opérations suivantes : 20 a) définir un vecteur bp,) d'état des n qubits à l'entrée du circuit quantique - dans l'exemple de la FIG.4 le vecteur km peut prendre chacun des huit états suivants : /01 /\ /01 / CO /0\ CO /0\ CO /0\ CO /0\ 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 ' 0 ' 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 \OI \OI \OI \OI \OI \OI \OI \01/ ...qui, en notation bra-ket (employée sur la FIG.4) peuvent être notés 25 respectivement : 1000) ; 1001) ; 1010) ; 1011) ; 1100) ; 1101) ; 1110) ; 1111) (empilés dans des cases superposées sur la FIG.4) b) répéter, pour k = 1 à k = d (ici pour k = 1 à k = 6), la séquence suivante : 3064380 21 b1) prendre en compte un vecteur le d'état possible des n qubits à l'entrée de la couche Lk, ce vecteur 11p1,) comprenant une série de 2n coefficients d'amplitude Crj:k ainsi, dans le cas de la FIG.4, pour j = 1 et k= 1, l'état des 5 n qubits à l'entrée de la couche L1 est 1000), les autres états apparaissant en grisé pour signifier qu'ils ne sont pas pris en compte dans la présente itération sur k; b2) identifier la porte Gk comprise dans la couche Lk - dans l'exemple de la FIG.4, G1=H; G2 = RIT ; G3= H; G4= Rit ; G5 = Rit ; 2 4 2 10 G6= H ; b3) prendre en compte le type de la porte Gk (dans l'exemple de la FIG.4, et pour k= 1 : porte dense ; pour k= 2 : porte diagonale ; pour k = 3 : porte dense ; pour k = 4 : porte diagonale ; pour k = 5 : porte diagonale ; pour k = 6 : porte 15 dense ; b4) si la porte Gk est de type diagonal (G2, G4, G5 dans l'exemple de la FIG.4), attribuer au vecteur d'état des n qubits sortant de la couche Lk la valeur du vecteur Ilp",) d'état des n qubits entrant dans celle-ci : 20 = 11Pi) Dans l'exemple de la FIG.4, les flèches horizontales joignant les cases non grisées de part et d'autre des portes G2, G4, et G5 illustrent l'identité des états d'entrée et de sortie ; b5) si la porte Gk est de type classique : 25 o détecter dans sa matrice de transfert chaque opérateur valant 1 et déterminer son numéro l de ligne et son numéro c de colonne (/ et c des entiers tels que 0 / 2n, 0 C 2n et / # c) ; o attribuer aux coefficients d'amplitude ai:k+1 du 30 vecteur bp",+i) d'état des n qubits sortant de la couche Lk les valeurs suivantes : j,k+1 j, a = aik pour tout i # j,k+1 j,k a1 = a 3064380 22 o mémoriser le vecteur Ltp",+i) dans un registre dédié d'une mémoire à circuit intégré sur semi-conducteur, ce qui permet d'effectuer chaque étape de calcul en parallèle ; 5 b6) si la porte Gk est de type dense : o déterminer l'ensemble des valeurs possibles du vecteur [tp",+i) d'état des n qubits sortant de la couche Lk tel que : 11P+1) = Uk - 1P ) 10 Ainsi, dans l'exemple de la FIG.4, on voit que, pour les portes G1, G3 et G6, le qubit entrant dans la porte d'Hadamart peut prendre toute valeur en sortie, tandis que les deux autres bits sont inchangés : cela explique qu'une double flèche parte de la case contenant l'état possible des qubits en entrée de la porte 15 et aboutisse aux deux seuls états possibles en sortie de la porte, selon la valeur du qubit affecté par la fonction de transfert de la porte : dans le cas, par ex. de la porte G3, qui affecte le deuxième qubit seulement, et en partant, en entrée, de l'état 1000), les seuls deux états possibles en sortie sont 1000) 20 et 1010) ; les autres états sont improbables et ignorés dans les étapes suivantes de la simulation ; o mémoriser chaque valeur possible du vecteur Ltp",+i) dans un registre dédié d'une mémoire à circuit intégré sur semi-conducteur, ce qui permet, à cette étape, de 25 poursuivre en parallèle les sous-calculs issus des calculs précédents ; c) lorsque les itérations précédentes sont achevées, agréger, dans un registre unique d'une mémoire à circuit intégré sur semi-conducteur, l'ensemble des états possibles du vecteur 30 Itp!i+i) (mémorisées dans des registres séparés, comme nous venons de le voir). Le fait de ne pas tenir compte des états improbables des qubits à chaque passage de porte permet de réduire considérablement le nombre d'itérations (et donc la puissance le temps de calcul), ainsi que l'espace 35 mémoire (de type classique) nécessaire. 3064380 23 Pour illustrer ces avantages, la simulation qui vient d'être décrite a pu être effectuée sur un circuit du type de la FIG.4 (Transformée quantique de Fourrier rapide), pour n = 18 à n = 24. En comparaison des algorithmes connus, on a pu accélérer la 5 simulation par un facteur compris entre 20 et 40. Plus précisément, en notant N la capacité mémoire disponible de l'ordinateur sur lequel est effectuée la simulation, la méthode permet de traiter un nombre maximal nm de qubits supérieur à : log(N) log(2) 10 Ce nombre est supérieur d'un facteur 2 aux nombres connus, à capacité mémoire équivalente. REVENDICATIONS1. Procédé de simulation, sur une unité de traitement informatique à circuit intégré sur semi-conducteur, du fonctionnement d'un modèle de circuit quantique configuré pour traiter un nombre prédéfini n (n un entier tel que n 2) de qubits en entrée et comprenant une série de d (d un entier tel que 2) portes quantiques Gk (k un entier, 1