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é par un vecteur d'état à 2 ⁿ 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 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 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 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 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→ 0 ou 1→ 1 ; NOT : 0→ 1 ou 1→0), la valeur d'un qubit est quant à elle indéterminée car 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 d'onde ip, notée \ψ) selon le formalisme bra-ket de Dirac, dans un espace de Hilbert. La fonction d'onde |i/>) s'écrit sous forme d'une combinaison linéaire des valeurs possibles du qubit :

Où |0) et |1) représentent les valeurs 0 et 1 (ou état de base) d'un bit classique, et où les coefficients a et /?, dénommés « amplitudes de probabilité », sont des nombres complexes normalisés selon la relation suivante :

D'un point de vue géométrique, un qubit peut être représenté par un point positionné à la surface d'une sphère dite de Bloch (de rayon 1), dont les coordonnées sphériques sont Θ (0 < θ≤ π) et φ (0 < φ≤ 2π).

Dans ces conditions, l'état l^} du qubit peut s'écrire sous forme de l'équation suivante :

...ou sous forme du vecteur d'état suivant :

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 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.

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 β, 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 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 \ψ) généralisée dans un espace de Hilbert à 2 ⁿ dimensions :

Où \i) représente les valeurs possibles (ou états de base) des combinaisons de bits classiques, et où les coefficients a _t sont les amplitudes de probabilité de chaque valeur, normalisés selon la relation suivante :

Ainsi, pour deux qubits (n = 2) :

Avec :

A la différence d'un ordinateur classique traitant un unique état du registre parmi l'ensemble de ses états possibles, l'ordinateur quantique est en théorie capable de traiter simultanément l'ensemble des états possibles du registre, soit 2 ⁿ . 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 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 2 ³³⁰ ≤ 10 ⁹⁰ , ce qui correspond au nombre estimé de particules dans notre univers observable.

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.

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 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, Proceedings of Symposia in Applied Mathematics, Université du 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 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 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 : Opération Matrix) de taille 2 ⁿ x 2 ⁿ et qui, appliquée à un vecteur d'état E initial de taille 2 ⁿ , fournit en sortie un vecteur d'état final E', également de taille 2 ⁿ et produit matriciel de E par U :

Cette modélisation est testée notamment dans Gerdt et al, A Mathematica Program for Constructing Quantum Circuits and Computing 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, 103- 129, a évalué la capacité mémoire (correspondant au nombre de bits 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 préfixes k, M et T correspondant respectivement aux opérateurs kilo, mega et Tera) :

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é n _m , de qubits simulables n'est pas supérieur à :

Une technique connue, pour limiter la capacité mémoire nécessaire au calcul (ou, à capacité mémoire équivalente, pour augmenter le nombre n _m de qubits simulables), consiste à une effectuer une approximation de la matrice opération U en réduisant sa dimension au moyen d'une 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 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 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 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 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 :

- soit d'un plus grand nombre de qubits à capacité mémoire équivalente, 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 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 G _k (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 une mémoire à circuit intégré sur semi-conducteur, chaque modèle de porte quantique étant associé à une matrice U _k 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 :

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 ;

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 L _k adjacentes 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 :

• 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 ;

• Porte de type dense, qui n'est ni de type classique ni de type diagonal ; Une phase de calcul, qui comprend la répétition, pour ; = 1 à j = 2 ⁿ (j un entier) des opérations suivantes :

a) définir un vecteur d'état des n qubits à l'entrée du circuit quantique, qui comprend une série de 2 ⁿ coefficients d'amplitude (i un entier, 0 < i < 2 ⁿ - 1) valant 0 ou 1, et tels que :

répéter, pour k = 1 à k = d, la séquence suivante :

b1) prendre en compte un vecteur d'état des n qubits à l'entrée de la couche L _k , ce vecteur comprenant une série de 2 ⁿ coefficients d'amplitude ;

b2) identifier la porte G _k comprise dans la couche L _k ;

b3) prendre en compte le type de la porte G _k ;

b4) si la porte G _k est de type diagonal, attribuer au vecteur d'état des n qubits sortant de la couche L _k la valeur

du vecteur d'état des n qubits entrant dans celle-ci :

b5) si la porte G _k est de type classique :

o détecter dans sa matrice de transfert chaque opérateur valant 1 et déterminer son numéro / de ligne et son numéro c de colonne (l et c des entiers tels que 0≤ l≤ 2 ⁿ , 0≤ c≤ 2 ⁿ et l≠ c) ;

o attribuer aux coefficients d'amplitude du

vecteur d'état des n qubits sortant de la couche

L _k les valeurs suivantes :

o mémoriser le vecteur dans un registre dédié

d'une mémoire à circuit intégré sur semi-conducteur ; b6) si la porte G _k est de type dense : o déterminer l'ensemble des valeurs possibles du vecteur d'état des n qubits sortant de la couche

L _k tel que :

o mémoriser chaque valeur possible du vecteur

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 vecteur

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 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 ;

- 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 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.

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 semi-conducteur » désigne tout processeur (également dénommé microprocesseur) comprenant des ensembles de transistors obtenus 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 (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 public.

Les avancées théoriques permises notamment par Hilbert, Dirac et Schrôdinger 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 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 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 particule (ici l'électron).

On n'expliquera pas ici la nature exacte des phénomènes physiques à l'œuvre (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.

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.

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 \ψ) la 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 s'écrit :

|0) et |1) 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 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.

et β, dénommés « amplitudes de probabilité » ou « coefficients d'amplitude », sont des nombres complexes qui relatent chacun la probabilité d'occurrence de la valeur correspondante (respectivement |0) pour a et |1) pour /?).

et β vérifient la relation dite de « normalisation » suivante :

La fonction d'onde \ψ) (ou état) du qubit unitaire peut également s'écrire sous forme d'un vecteur (matrice colonne) :

Dans cette notation, les états |0) et |1) s'écrivent de la manière suivante :

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 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 \ψ) généralisée. Dans un espace Hilbertien de dimension n la fonction d'onde (ou état) s'écrit :

\i) représente, en notation bra-ket (notation de Dirac) et en binaire, les valeurs possibles (ou états de base) des combinaisons de bits classiques.

Les coefficients 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 ensemble la relation suivante :

Avec, pour tout i :

Nous avons déjà présenté la fonction d'onde appliquée à un

unique qubit. Pour ce cas très simple, observons simplement, pour clarifier les notations, que a ₀ est noté a et a noté β.

Pour deux qubits (n = 2) :

Avec :

En notation vectorielle :

Pour trois qubits (n = 3) :

En notation vectorielle :

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 α _έ d'amplitude, mais sur une approche combinatoire qui tient compte de l'ensemble des valeurs possibles que peut prendre le vecteur d'état \ψ) (c'est-à-dire la fonction d'onde) tout en éliminant les valeurs improbables de ce vecteur d'état au fur et à mesure de la progression des qubits au travers du circuit quantique.

A titre liminaire, observons que, pour deux qubits (n = 2, voir ci- dessus), les valeurs possibles que peut prendre \ψ) sont :

...qui correspondent respectivement au valeurs suivantes des deux qubits pris ensemble :

Pour trois qubits (n = 3, voir ci-dessus), les valeurs possibles que peut prendre \x ) sont

...qui correspondent respectivement aux valeurs suivantes des trois qubits pris ensemble :

Un circuit quantique modifie la valeur du ou des 2 ⁿ qubits qui le traverse(nt).

Par convention, et pour la suite de l'exposé, on note \ψ) l'état des qubits entrant dans le circuit et \ψ') l'état des qubits qui en sortent. \ψ) et \xj)') sont liés par une fonction de transfert, opérée par le circuit quantique et décrite par une relation matricielle :

Où U est une matrice, dite de transfert, de taille 2 ⁿ x 2 ⁿ , correspondant à la fonction de transfert appliquée par le circuit quantique aux qubits entrants. La matrice de transfert U comprend des opérateurs u _xy (x et y des entiers, 0 < x≤ 2 ⁿ — 1, 0≤ y≤ 2 ⁿ - 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 quantique aux qubits entrants, tels que décrits par leur vecteur d'état

En notant :

...on peut écrire comme suit la relation entre \ψ') et \ψ) :

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 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

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 prédéterminée sur un ou plusieurs des qubits entrant dans la couche (mais pas nécessairement sur la totalité d'entre eux).

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.

On note k l'indice de chaque couche (k un entier tel que l≤k≤d), que l'on affecte à la lettre L pour désigner par L _k la k ^lème couche et à la lettre G pour désigner par G _k la k ^lème porte logique unitaire, contenue dans la couche L _k .

La littérature (cf. par ex. Nielsen & Chuang, op. cit.) a défini un 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 :

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 π), à un unique qubit et sont respectivement définies comme suit :

la porte « Controlled-NOT », notée CNOT, qui applique sa fonction de transfert (une inversion) à deux qubits et est définie comme suit :

la porte SWAP (ou qSWAP), qui applique sa fonction de transfert permutation) à deux qubits et est définie comme suit : la porte de phase contrôlée, notée fl^, associée à un angle noté φ (dans la notation employée pour décrire le qubit sur la sphère de Bloch), qui applique sa fonction de transfert (une rotation d'angle φ) à un unique qubit et est définie comme suit :

Pour faciliter la simulation d'un circuit quantique quelconque, les 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 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 :

• Z, βφ, 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 lieu, eu l'idée de minimiser les opérations effectuées sur les qubits transitant par chaque couche L _k 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 G _k résidant dans cette couche, en partant du triple postulat suivant :

Pour tout vecteur d'état des n qubits entrant dans la porte,

considéré selon ses valeurs possibles - c'est-à-dire que le vecteur d'état se présente sous forme d'une matrice colonne comprenant 2 ⁿ - 1 coefficients de coefficients d'amplitude de valeur 0 et un unique coefficient d'amplitude de valeur 1 (voir les exemples fournis ci- 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 contrôlée fl^, 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 des qubits entrants

- 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 a _c d'amplitude de valeur 1, depuis le rang i = c où se trouve ce coefficient dans le vecteur d'état des qubits entrants), vers le rang l dans le vecteur d'état des qubits sortant ;

3) Une porte logique de type dense effectue plusieurs transformations possibles du vecteur d'état des qubits entrants - c'est

notamment le cas de la matrice H, car sa matrice comprend des 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 ^en sortie de la porte, pour 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 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 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 qui applique au qubit qui la traverse une rotation d'angle

On a représenté sous la porte, dans des cases superposées, les quatre états possibles des qubits d'entrée : |00), |01), 110) et et, à même hauteur, les quatre états possibles des qubits de sortie : |00), |01), |10) et |11).

Si l'état d'entrée est |00), alors la seule valeur possible de l'état de sortie est également |00), les autres valeurs possibles, |01), |10) et |11>, é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.

On a représenté à titre d'illustration la transition d'état |0)→ |0) 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 : 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 : |0) et et, à même hauteur, les deux valeurs possibles du qubit de sortie : |0) et |1).

Si l'état du qubit d'entrée est |0>, alors le seul état possible du qubit de sortie est |1>, l'autre valeur possible, |0), étant improbable et pouvant être ignorée : la case correspondante apparaît grisée.

Inversement, si l'état du qubit d'entrée était |1), alors le seul état possible du qubit de sortie serait de |0), l'autre état possible, étant improbable (et pouvant être ignoré).

On a représenté à titre d'illustration la transition d'état |0)→ |1) 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 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 : |0) et |1), et, à même hauteur, les deux valeurs possibles du qubit de sortie : |0) et |1).

Quelle que soit l'état du qubit d'entrée, |0) ou |1), il est équiprobable que son état de sortie soit |0) (état inchangé) ou |1) (état modifié). En supposant l'état du qubit d'entrée à |0), on a représenté à titre d'illustration les deux transitions d'état possibles par deux flèches partant de la case |0) : l'une horizontale vers |0), signifiant la possibilité d'un maintien de l'état du qubit, l'autre oblique vers |1), signifiant la 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 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 U _k 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.

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 ;

o sélectionner les d modèles de portes quantiques, par ex. trois portes d'Hadamard, deux portes et une porte

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 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 à :

o diviser le circuit quantique en d couches L _k adjacentes destinées à être traversées successivement par les n qubits pris ensemble, chaque couche comprenant une unique porte quantique G _k élémentaire - ainsi, dans l'exemple de la FIG.4, où d = 6 :

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 G ₂ , G ₄ et G _S ;

• Porte de type classique, dont la matrice est non diagonale 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, de G _LT G ₃ et G ₆ .

Une fois cette analyse achevée, la simulation comprend une troisième phase de calcul, qui comprend la répétition, pour ; = 1 à = 2 ⁿ (j un entier ; dans l'exemple de la FIG.4, n = 3 de sorte que j varie de 1 à 2 ³ = 8) des opérations suivantes :

a) définir un vecteur \\pj) d'état des n qubits à l'entrée du circuit quantique - dans l'exemple de la FIG.4 le vecteur peut prendre chacun des huit états suivants :

...qui, en notation bra-ket (employée sur la FIG.4) peuvent être notés respectivement :

|000) ; |001) ; |010) ; |011) ; |100) ; |101) ; |110) ; |111)

(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 : b1) prendre en compte un vecteur d'état possible des n

qubits à l'entrée de la couche L _k , ce vecteur comprenant une série de 2 ⁿ coefficients d'amplitude

ainsi, dans le cas de la FIG.4, pour j = 1 et k = 1, l'état des n qubits à l'entrée de la couche L _x est |000), 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 G _k comprise dans la couche L _k - dans l'exemple de la FIG.4,

b3) prendre en compte le type de la porte G _k (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/c = 5 : porte diagonale ; pour k = 6 : porte dense ;

b4) si la porte G _k est de type diagonal (G ₂ , G ₄ , G ₅ dans l'exemple de la FIG.4), attribuer au vecteur d'état des n qubits

sortant de la couche L _k la valeur du vecteur d'état des

n qubits entrant dans celle-ci :

Dans l'exemple de la FIG.4, les flèches horizontales joignant les cases non grisées de part et d'autre des portes G ₂ , G ₄ , et G ₅ illustrent l'identité des états d'entrée et de sortie ; b5) si la porte G _k est de type classique :

Ô 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 (l et c des entiers tels que ;

attribuer aux coefficients d'amplitude du vecteur d'état des n qubits sortant de la couche

L _k les valeurs suivantes : o mémoriser le vecteur 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 ;

b6) si la porte G _k est de type dense :

o déterminer l'ensemble des valeurs possibles du vecteur d'état des n qubits sortant de la couche

L _k tel que :

Ainsi, dans l'exemple de la FIG.4, on voit que, pour les portes

G _lt G ₃ et G ₆ , 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 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 G ₃ , qui affecte le deuxième qubit seulement, et en partant, en entrée, de l'état |000), les seuls deux états possibles en sortie sont |000) et |010) ; les autres états sont improbables et ignorés dans les étapes suivantes de la simulation ;

o mémoriser chaque valeur possible du vecteur

dans un registre dédié d'une mémoire à circuit intégré sur semi-conducteur, ce qui permet, à cette étape, de 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 (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 mémoire (de type classique) nécessaire. 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 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 n _m de qubits supérieur à :

Ce nombre est supérieur d'un facteur 2 aux nombres connus, à capacité mémoire équivalente.