Note: Descriptions are shown in the official language in which they were submitted.
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
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é
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
2
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 : 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 zp, notée lip) selon le formalisme bra-ket de Dirac, dans un espace
de Hilbert. La fonction d'onde lip) s'écrit sous forme d'une combinaison
linéaire des valeurs possibles du qubit :
10) = al()) + fill)
Où 10) et 11) représentent les valeurs 0 et 1 (ou état de base) d'un bit
classique, et où les coefficients a et je, dénommés amplitudes de
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
3
probabilité , sont des nombres complexes normalisés selon la relation
suivante :
lai2
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 (0 < 0 < 7) et 0 (0 4 < 271-).
Dans ces conditions, l'état Io> du qubit peut s'écrire sous forme de
l'équation suivante :
0 0
hi)) = cos ¨210) + ei0 sin-211)
...ou sous forme du vecteur d'état suivant :
cos-8 \
2
IO) = 0
\ei0
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 le, 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 10) généralisée
dans un espace de Hilbert à 271 dimensions :
2n-1
I1P) = ai
i=0
Où Ii) représente les valeurs possibles (ou états de base) des
combinaisons de bits classiques, et où les coefficients ai sont les
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
4
amplitudes de probabilité de chaque valeur, normalisés selon la relation
suivante :
2n-1
lail2 = 1
i=0
Ainsi, pour deux qubits (n = 2) :
a0100)+ a1101)+ a2110)+ (13111)
Avec :
1%12 + + la212 + 1ct312 = 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
est en théorie capable de traiter simultanément l'ensemble des états
possibles du registre, soit r. 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 23" a 1090, 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 = 3 x 5). 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
CA 03057734 2019-09-23
WO 2018/172629 PCT/FR2018/000057
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 0 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
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 2n X 2n et qui, appliquée à un vecteur d'état E initial de taille
2n,
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 Pro gram for Constructing Quantum Circuits and Computing
Their Unitary Matrices, Workshop on Quantum Physics and
Communication, Oct. 2007.
Cependant Patrzyk et al, Towards a Nove! 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) :
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
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
= 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é 11m, de qubits simulables n'est pas supérieur
à :
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
nin 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,
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
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
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
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 :
¨ 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 Lk 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 ;
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
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 pi) d'état des n qubits à l'entrée du circuit
quantique, qui comprend une série de 2n coefficients
d'amplitude al (i un entier, 0 < j < 2 ¨1) valant 0 ou 1, et tels
que :
2n-1
/ lai'2 = 1
i=0
b) répéter, pour k =1 à k= d, la séquence suivante :
b1) prendre en compte un vecteur ki,) d'état des n qubits à
l'entrée de la couche Lk, ce vecteur 'Ob comprenant une
série de 2n coefficients d'amplitude Cri'le ;
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
101,41) d'état des n qubits sortant de la couche Lk la valeur
du vecteur 1.1pb d'état des n qubits entrant dans celle-ciIi :
=
b5) si la porte Gk 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 (1 et c des entiers
tels que 0< / < 2, 0 < < 2n et /* c) ;
o attribuer aux coefficients d'amplitude aiLk 1 du
vecteur liptc+i) d'état des n qubits sortant de la couche
Lk les valeurs suivantes :
aj,k+1 j,k
1 = ai pour tout i # 1
aj,k+1 = aj,k
1 c
O mémoriser le vecteur Ithic+i) dans un registre dédié
d'une mémoire à circuit intégré sur semi-conducteur ;
b6) si la porte Gk est de type dense :
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
9
o
déterminer l'ensemble des valeurs possibles du
vecteur Ilpic+i) d'état des n qubits sortant de la couche
Lk tel que :
let, 1)=uk = liPb
o mémoriser chaque
valeur possible du vecteur Itp+i)
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
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
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
Schrtidinger 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'oeuvre (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 Ii/') la
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
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
s'écrit :
10) = al0)+16'11)
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
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 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 10)
pour a et 11) pour fl).
a et fi vérifient la relation dite de normalisation suivante :
1a12 + 11912 = 1
La fonction d'onde Itp) (ou état) du qubit unitaire peut également
s'écrire sous forme d'un vecteur (matrice colonne) :
IO) = Ga)
Dans cette notation, les états 10) et 11) s'écrivent de la manière
suivante :
IO) = (01)
0
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
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 10) généralisée.
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
12
Dans un espace Hilbertien de dimension n la fonction d'onde (ou
état) ltp) s'écrit :
2n-1
10) = aiii)
i=o
Ii) 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 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
ensemble la relation suivante :
2n-1
lail2 = 1
i=0
Avec, pour tout i :
ai e {0; 1}
Nous avons déjà présenté la fonction d'onde 10) appliquée à un
unique qubit. Pour ce cas très simple, observons simplement, pour
clarifier les notations, que ao est noté a et ai noté fl.
Pour deux qubits (n=2) :
IO) = %I00) + a1101)+ a2110) + a3111)
Avec :
1%12 + 142 la2 12 + la312 = 1
En notation vectorielle :
7a0\
10) =2
a3/
Pour trois qubits (n= 3) :
10) = ao1000)+ 4001) + a21010) + a31011) + a41100) + a51101) + a61110) +
a71111)
Avec :
a012 + 1a112 + la212 + 1a312 + 1a412 + la512 + la612 + la712 = 1
En notation vectorielle :
CA 03057734 2019-09-23
WO 2018/172629 PCT/FR2018/000057
13
ict \
a2
a3
hi') = a4
a5
\a71
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
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 10) 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 lip) sont :
/1\ /0\ /0\ /0\
0.1Ø0
0 't ' 1 ' 0
\0/ \01 \0/ \1/
...qui correspondent respectivement au valeurs suivantes des deux qubits
pris ensemble :
100) ;101) ;110) ;111)
Pour trois qubits (n = 3, voir ci-dessus), les valeurs possibles que
peut prendre 10) sont :
/0\ /0\ /0\ /0\ /0\
/ 0 0 /0 / 0' 0
0 0 1 0 0 0 0 0
1 . 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
\01 \01 \01 \OI \01 ()1 \1i
...qui correspondent respectivement aux valeurs suivantes des trois
qubits pris ensemble :
000>; 1001>; 1010) ; 1011>; 1100>; 1101>; 1110>; 1111)
Un circuit quantique modifie la valeur du ou des 2n qubits qui le
traverse(nt).
Par convention, et pour la suite de l'exposé, on note 1-0) l'état des
qubits entrant dans le circuit et hp') l'état des qubits qui en sortent.
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
14
ltp) et Iip') sont liés par une fonction de transfert, opérée par le circuit
quantique et décrite par une relation matricielle :
Ith = U = 11P)
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,), (x et y des entiers, 0 x 2n ¨ 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 Itp).
En notant :
( ao )
IO> =
a2n-i.
10,) = ( a;
)
\a'2n-il
' ( uoo === 2/0(2n_i)
U =
22(2n-1)0 === U(2n-1)(2n-1)
...on peut écrire comme suit la relation entre lip') et lzp) :
( do
= 1200 === 2/0(2n_i) x ( a.0 )
Cri2n-2 U(2n-1)0 = = = U(2n-1)(2n-
1) ce2n-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
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 W)= U=10).
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
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
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
5 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 1 < k < d),
que l'on affecte à la lettre L pour désigner par Lk la kièrne couche et à la
lettre G pour désigner par Gk la kième porte logique unitaire, contenue dans
10 la couche Lk.
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 :
15 ¨ la porte d'Hadamard, notée H, qui applique sa fonction de transfert
à un unique qubit et est définie comme suit :
H A 1 (1 1
¨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 :
X (NOT) (01 1)
Y =A ( .
O
ZA
-'O ¨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\
CNOT
0 1 0 0
A
i 0 0 0 1
\O 0 1 Oi
¨ 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 0
qSWAP
0 1 0 0
\O 0 0 11
CA 03057734 2019-09-23
WO 2018/172629 PCT/FR2018/000057
16
¨ la porte de phase contrôlée, notée Ro, associée à un angle noté 0
(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 0)
à un unique qubit et est définie comme suit :
/1 0 0 0\
0 1 0 0
RO = i0 0 1 0
\O 0 0
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, 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
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 :
Pour tout vecteur 10k) d'état des n qubits entrant dans la porte,
considéré selon ses valeurs possibles ¨ c'est-à-dire que le vecteur 10k)
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-
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
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
17
notamment le cas de la porte de Pauli Z et des portes de phase
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 lzpk) 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, d'amplitude de valeur 1,
depuis le rang i= c où se trouve ce coefficient dans le vecteur
d'état I1/k) des qubits entrants), vers le rang 1 dans le vecteur d'état
lipk+1) des qubits sortant ;
3) Une porte logique de type dense effectue plusieurs transformations
possibles du vecteur d'état I1/'k) 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 Itpk4.1) 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 Rx , qui applique au qubit qui la traverse une
2
rotation d'angle
CA 03057734 2019-09-23
WO 2018/172629 PCT/FR2018/000057
18
On a représenté sous la porte, dans des cases superposées, les
quatre états possibles des qubits d'entrée : 100), 101), 110) et 11 1), et, à
.
même hauteur, les quatre états possibles des qubits de sortie : 100), 101),
110) et Iii).
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, 101), 110) et Iii),
é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 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 :
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 11), et, à même hauteur, les
deux valeurs possibles du qubit de sortie : 10) et 11).
Si l'état du qubit d'entrée est 10), alors le seul état possible du qubit
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 11), alors le seul état
possible du qubit de sortie serait de 10), l'autre état possible, 11), étant
improbable (et pouvant être ignoré).
On a représenté à titre d'illustration la transition d'état 10) 11) 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 : 10) et 11), et, à même hauteur, les
deux valeurs possibles du qubit de sortie : 10) et 11).
Quelle que soit l'état du qubit d'entrée, 10) ou 11), il est équiprobable
que son état de sortie soit 10) (état inchangé) ou 11) (état modifié).
CA 03057734 2019-09-23
WO 2018/172629 PCT/FR2018/000057
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
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 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.
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 Rit et une porte Rit ;
2 4
0 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 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 :
L1G1=H
L2 - G2 = Rit
2
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
L3 A G3 = H
L4 A G4 = R71-
L5 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= 2n
(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 Ilpi) d'état des n qubits à l'entrée du circuit
quantique ¨ dans l'exemple de la FIG.4 le vecteur ipi) peut
prendre chacun des huit états suivants :
0 0 1 0 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/ \0/ \0/ \0 \0/ \0/ \0/ \1/
...qui, en notation bra-ket (employée sur la FIG.4) peuvent être notés
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=là k =d (ici pour k = 1 à k = 6), la séquence
suivante :
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
21
b1) prendre en compte un vecteur lipb d'état possible des n
qubits à l'entrée de la couche Lk, ce vecteur Pb
comprenant une série de 2n coefficients d'amplitude ail'k ¨
ainsi, dans le cas de la FIG.4, pour] = 1 et k = 1, l'état des
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 = ;
G3 = H; G4 = Rit; G5 = Rit;
2 4 2
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
dense ;
b4) si la porte Gk est de type diagonal (G2, G4, G5 dans l'exemple
de la FIG.4), attribuer au vecteur pp) d'état des n qubits
sortant de la couche Lk la valeur du vecteur Ithi,) 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 G2, G4,
et G5 illustrent l'identité des états d'entrée et de sortie ;
b5) si la porte Gk est de type classique :
0 détecter dans sa
matrice de transfert chaque
opérateur valant 1 et déterminer son numéro I de
ligne et son numéro c de colonne (/ et c des entiers
tels que 0 < I < 2, 0 < c < 2n et l# ;
o
attribuer aux coefficients d'amplitude alm+1 du
vecteur Ithic+i) d'état des n qubits sortant de la couche
Lk les valeurs suivantes :
aj,k+1 ,k
= a!'' pour tout i # /
aj,k+1 j,k
= a
1
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
22
o mémoriser le vecteur 1.01,.+1) 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 Gk est de type dense :
o déterminer l'ensemble des valeurs possibles du
vecteur I+i) d'état des n qubits sortant de la couche
Lk tel que :
IV)1+1) Uk = 11Pic)
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
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)
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 lip)
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
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
mémoire (de type classique) nécessaire.
CA 03057734 2019-09-23
WO 2018/172629
PCT/FR2018/000057
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
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 ni, de qubits supérieur à :
log(N)
log(2)
Ce nombre est supérieur d'un facteur 2 aux nombres connus, à
capacité mémoire équivalente.
