Informatique Quantique — Fondements
Préface
L’informatique quantique est un terme qu’on entend de plus en plus régulièrement aujourd’hui. Elle porte de grands espoirs pour l’avenir de la technologie en promettant d’aborder des problèmes actuellement hors de notre portée, ou en révolutionnant certains domaines de l’informatique classique, par exemple la cryptographie.
Le développement de l’informatique quantique ressemble au développement de l’informatique traditionnelle, lorsque les physiciens travaillaient avec les ingénieurs pour construire les premiers transistors. On peut espérer que l’informatique quantique, bien qu’elle n’ait pas les mêmes objectifs que l’informatique classique, bénéficiera autant à l’Humanité.
Introduction
Voici le premier article d’une série de trois à propos d’informatique quantique dont l’organisation est la suivante :
- Informatique Quantique — Fondements (celui-là)
- Informatique Quantique — Programmation Quantique
- Informatique Quantique —Apprentissage Automatique Quantique
Avant même de définir précisément ce qui est entendu par Informatique Quantique, nous allons discuter d’un problème bien connu en informatique. Ce problème va nous permettre d’illustrer l’intérêt de l’informatique quantique et d’introduire la notion de complexité algorithmique.
Le problème dont nous allons parler s’appelle le problème du voyageur de commerce. Le voici :
Étant donnés n points et les distances qui séparent ces points, trouver un chemin de longueur minimale qui passe par chacun des points une seule fois et qui revient au point de départ.
Bien que l’énoncé soit très simple, il présente une difficulté fondamentale relative à ce que l’on appelle la complexité algorithmique. La complexité correspond à la quantité de ressources (la mémoire ou le nombre d’instructions processeur par exemple) nécessaire à la résolution d’un problème par un ordinateur.
Pour résoudre ce problème, une manière simple serait de parcourir tous les chemins possibles, de comparer leur taille puis de choisir le plus court. La complexité d’un tel algorithme dépend, on le comprend, du nombre de chemins possibles.
L’exemple le plus évident est le cas où il n’y a que trois points. S’il y a trois points, il n’existe qu’un seul chemin les reliant tous (le chemin A-B-C-A est le même que A-C-B-A, en sens inverse).
Si l’on ajoute un point, il existe maintenant 3 chemins différents : A-B-C-D-A, A-C-B-D-A, A-B-D-C-A.
Pour 5 points, il existe 12 chemins différents, pour 6 il y en a 60, pour 7, 360…
En fait, le nombre de chemins augmente comme suit :
On constate une augmentation extrêmement rapide, à tel point que l’on atteint pour n = 71 points un nombre de chemins possibles plus importants que le nombre d’atomes dans l’univers observable (environ 10 puissance 80). Rappelons qu’il y a 36.000 communes en France, il est certain qu’on ne puisse même pas écrire le nombre de chemins qui existent entre ces communes.
La formule pour calculer le nombre de chemins en fonction du nombre de points est la suivante : 1/2 * (n-1)!.
On dit que la complexité de l’algorithme qui consiste à essayer toutes les combinaisons (recherche par force brute) est en n! (n factoriel). C’est à dire que la quantité d’opérations à effectuer est proportionnelle au factoriel du nombre de points. Il existe des algorithmes plus rapides cela dit, dont la complexité est “seulement” exponentielle, et qui sont donc malgré tout très coûteux.
Si l’on veut diminuer le temps nécessaire pour résoudre un problème, on utilise traditionnellement la parallélisation. C’est à dire que l’on fait fonctionner plusieurs processeurs en même temps. De cette manière, on peut diviser le temps de calcul par k, k étant le nombre de processeurs. C’est cette méthode qui est utilisée notamment pour l’apprentissage automatique, lorsque l’on utilise des processeurs graphiques.
Malheureusement, la parallélisation est un procédé qui réduit seulement linéairement le temps de calcul. Or, si la complexité est exponentielle, réduire linéairement la quantité de ressources ne sera jamais suffisant pour un jeu de données très grand. Pour s’en convaincre, il suffit d’observer le calcul de la limite suivante :
Pour aborder ces problèmes dont la complexité est exponentielle, il nous faudrait une manière de calculer qui soit elle-même exponentielle. Et c’est une différence de nature, pas une différence de degré, avec les ordinateurs actuels.
C’est l’espoir qui est aujourd’hui placé dans l’ordinateur quantique, apporter une puissance de calcul exponentielle.
Cette affirmation est à prendre avec des pincettes cependant, dans le sens où toutes les applications ne bénéficieront pas de l’arrivée des ordinateurs quantiques. En réalité, certains algorithmes, très séquentiels par exemple, ne verront aucune amélioration.
Physique Quantique
Avant de parler d’Informatique Quantique (IQ), nous devons aborder quelques concepts fondamentaux de la physique quantique, qui sous tendent le fonctionnement de l’Ordinateur Quantique (OQ).
Spin
Le spin est une propriété des particules qui, contrairement à la masse ou l’énergie, n’a pas d’équivalent en mécanique classique. On l’assimile en revanche souvent au moment cinétique (il est appelé le moment cinétique intrinsèque), qui serait directement lié au sens de rotation de la particule sur elle-même, si la particule agissait comme un objet classique.
Schématiquement, le spin est un vecteur, et le sens du spin correspond à l’axe de rotation.
On distingue deux sens de spin, le spin haut et le spin bas. Nous notons les spins de la manière suivante :
- |0⟩ : spin haut
- |1⟩ : spin bas
Ces deux sens de spin ont été mis en évidence par les physiciens Stern et Gerlach, dans l’expérience qui porte leurs noms. Pour ce faire, ils ont positionné deux aimants, l’un aimanté nord en haut, l’autre aimanté sud en bas.
Ils ont ensuite fait passer un faisceau d’atomes d’argent entre ces deux aimants. Si les atomes se comportaient comme des petits aimants eux-mêmes, alors ils seraient plus ou moins déviés par les aimants suivant l’orientation dans laquelle ils sont projetés, et l’on verrait une zone homogène de projection des atomes. Or, Stern et Gerlach observent que le faisceau incident est scindé très précisément en deux petits faisceaux, l’un vers le haut, l’autre vers le bas. Voici une illustration du dispositif :
Il en ressort que le spin est une propriété quantifiée, c’est à dire qu’il prend des valeurs discrètes lorsque mesuré, haut ou bas, et non continues. Bien qu’on lise parfois qu’il s’agirait d’une propriété qui émergerait de la rotation de l’électron sur lui-même, ce n’est pas exact. Le spin n’a pas d’équivalent macroscopique, il vaut mieux le considérer ainsi plutôt que de tenter de lui donner une fausse réalité illustrative qui ne correspond pas vraiment, et qui induit en erreur. Dans le cas de l’électron par exemple, bien qu’ayant une valeur de spin, l’électron ne tourne pas sur lui-même. Si c’était le cas, alors la vitesse de rotation à la périphérie de l’électron serait supérieure à celle de la lumière, violant ainsi la relativité restreinte.
Principe de Superposition
Le principe de superposition est le principe fondamental de la mécanique quantique. Pour bien l’appréhender, présentons la fameuse expérience de Stern et Gerlach, et donnons quelques explications. Cette expérience est composée de plusieurs situations.
Dans les situations qui suivent, la valeur de spin “haut” est en réalité la composante selon l’axe Z de la valeur de spin. La valeur de spin “bas” est donc la composante opposée. La valeur de spin “droit” est la composante selon l’axe X de la valeur du spin.
La première est la suivante : nous installons une boîte (la boîte contient deux aimants positionnés comme sur l’image plus haut) qui permet de tester le spin haut dans laquelle nous faisons passer un faisceau d’atomes. Les atomes dont le spin est haut sortiront à droite de la boîte, et ceux dont le spin est bas sortiront en bas de la boîte. A côté de cette première boîte, nous en installons une deuxième, identique, qui teste le spin haut. Nous connectons ces deux boites de sorte que les atomes qui sont sortis à droite de la première boite (spin haut) entrent dans la deuxième boite. Pour information, la première boîte nous permet de nous assurer de l’état des particules qui la quittent, on nomme cette partie du dispositif le “polariseur”. L’autre boîte effectue la mesure, et l’on appelle cette partie du dispositif “l’analyseur”.
Voici le dispositif :
Comme prévu, 100% des atomes qui sont entrés dans la deuxième boîte sont sortis à droite. Autrement dit, avoir un spin haut correspond bien à être mesuré avec un spin haut.
Voici notre deuxième situation : nous installons une boîte qui teste le spin haut. A côté de cette première boîte, nous en installons une deuxième, qui teste le spin bas. Les atomes qui ont un spin bas sortiront à droite, et ceux qui ont un spin haut sortiront en bas. Nous connectons ces deux boites de sorte que les atomes qui sont sortis à droite de la première boite (spin haut) entrent dans la deuxième boite.
Voici le dispositif :
On observe sans surprise que les atomes qui sont sortis à droite de la première boite, et qui ont donc un spin haut, sortent bien en bas de la deuxième boite. La valeur de spin haut et la valeur de spin bas sont mutuellement exclusives.
La troisième situation est un peu plus complexe, et surprenante. Nous installons 4 boîtes comme ceci : une qui mesure le spin haut, une dans laquelle on fait faire à l’aimant une rotation de 90 degrés afin de mesurer ce que l’on appellera le spin droit (la projection du spin selon une autre composante de l’espace), une troisième boîte pour mesurer le spin haut puis une dernière qui mesure à nouveau le spin droit. Voici le schéma :
Tous les atomes qui sortent de la première boîte ont un spin haut. On observe ensuite que la moitié des atomes sont mesurés avec un spin droit, et l’autre moitié avec un spin gauche. Ce qui se passe dans la troisième partie du dispositif est étonnant. Alors qu’après que les atomes aient été mesurés avec un spin haut par la première boîte, la moitié de ces atomes ont maintenant un spin bas. Comment est-ce possible que la mesure soit différente ?
Le système se comporte comme si la mesure faite par la deuxième boîte avait “effacé” la mesure faite par la première.
Ce phénomène est typique de la mécanique quantique : la mesure perturbe le système. Notez que ceci n’a rien à voir avec la qualité de l’appareil de mesure, c’est un principe fondamental.
La mesure perturbe le système.
Il s’avère qu’il est impossible de mesurer avec précision la composante du spin selon l’axe Z et selon l’axe X en même temps. On dit que ce sont des observables incompatibles. Toutes les paires d’observables (les propriétés que l’on peut tester) ne sont pas incompatibles, certaines seulement.
On peut retirer deux choses de ces expériences : le fait que la mesure perturbe le système mesuré, et le fait que dans le monde quantique, avant la mesure, les objets n’ont pas d’état comme on l’entend généralement. Si deux états sont possibles pour un objet, par exemple spin haut et spin bas, alors l’objet se trouve dans ce qui est appelé un état superposé. Dit grossièrement, l’objet est dans l’état spin haut et l’état spin bas à la fois. Lors de la mesure, l’objet va “choisir” l’un des états aléatoirement, suivant certaines probabilités dont nous allons parler.
Principe de superposition : un objet quantique peut se trouver dans une superposition d’états.
Formalisation
Mathématiquement, les états possibles d’un système quantique sont représentés par des vecteurs dans un espace de Hilbert (un espace vectoriel dans lequel on dispose du produit scalaire). Or l’on sait qu’il est possible d’effectuer deux opérations sur les vecteurs :
- les additionner : u + v
- les multiplier par une constante : a * u
Pour décrire l’état d’une particule, nous utilisons ce qui s’appelle un vecteur d’état. On note souvent le vecteur d’état psi :
Dans le cas du spin, nous avons deux états possibles : spin haut et spin bas. Le vecteur d’état d’une particule est donc la combinaison linéaire de ces deux états, notée comme suit :
Les deux vecteurs spin haut et spin bas forment une base de l’état du spin d’une particule, un peu à la manière des vecteurs x et y dans le plan.
Lorsque nous effectuons une mesure, la Nature “choisit” aléatoirement quel état nous observerons (c’est ce que l’on appelle la réduction du paquet d’onde). La probabilité avec laquelle nous observons un état plutôt qu’un autre lors de la mesure dépend des coefficients alpha 0 et alpha 1, que l’on appelle l’amplitude. Ce n’est pas forcément 50/50, nous pourrions trouver la valeur “spin haut” dans 99% des cas, et la valeur “spin bas” dans 1% des cas par exemple. En fait, toutes les combinaisons sont possibles.
On peut noter nos deux vecteurs de base comme ceci :
Grace à ces vecteurs, nous allons pouvoir effectuer les opérations mathématiques de l’algèbre linéaire.
Il y a quelques règles à respecter cependant :
- le produit scalaire de deux vecteurs orthogonaux fait toujours 0 : ⟨0|1⟩ = 0
- le produit scalaire d’un vecteur par lui-même fait 1 : ⟨u|u⟩ = 1
- pour obtenir la probabilité de mesurer un état d’un système, il faut élever au carré son coefficient d’amplitude
- la somme des carrés des amplitudes doit être égale à 1 (la somme des probabilités est toujours égale à 1)
Illustrons ces notations par l’exemple du spin droit, dont le vecteur d’état est le suivant :
Calculons la probabilité d’obtenir un spin bas au moment de la mesure :
On trouve bien 1/2, comme dans l’expérience.
Une petite précision s’impose. Les coefficients d’amplitude ne sont pas des nombres réels classiques, mais des nombres complexes. Cette propriété fait que l’on peut représenter une superposition d’états comme un point sur une sphère de diamètre 1, la sphère de Bloch. Voici à quoi elle ressemble :
Le vecteur d’état peut ainsi être représenté graphiquement sur la sphère.
Informatique Quantique
Bits vs Qubit
Il est maintenant temps de nous intéresser à comment nous pouvons utiliser les concepts que nous avons appris pour élaborer une nouvelle manière de calculer.
Dans l’ordinateur classique, l’unité élémentaire de calcul s’appelle le bit, contraction anglaise de binary digit (nombre binaire en français). Un bit peu prendre la valeur de 0, ou bien de 1. Électroniquement parlant, le bit peut être matérialisé de plusieurs manières. On peut utiliser la valeur de la tension dans une portion de circuit électrique, la polarisation magnétique ou même l’intensité lumineuse, comme dans la fibre optique.
En informatique quantique, le bit est remplacé par son équivalent quantique, le quantum binary digit, ou qubit. Ce qubit peut être la valeur de spin d’un électron par exemple. La discipline qui s’applique à stocker de l’information grâce au spin des électrons s’appelle la spintronique, ou l’électronique de spin.
Comme nous l’avons vu précédemment, un qubit, le spin d’un électron est défini par son vecteur d’état. Puisque le spin peut prendre deux valeur, alors deux coefficients d’amplitude sont utilisés pour définir cet état. Et ce sont ces coefficients qui vont servir à stocker l’information dans le qubit. Un qubit, étant dans une superposition de deux état, stocke ainsi deux valeurs en même temps.
Puisqu’un ordinateur n’a pas qu’un seul bit, nous devons nous intéresser à ce qui se passe lorsque plusieurs qubits interagissent ensemble.
Supposons deux qubits, a et b. Le qubit “a” est défini par son vecteur d’état |a⟩ et le qubit b est défini par son vecteur d’état |b⟩. Nous écrivons comme ceci :
Si l’on veut combiner ces deux qubits, nous utilisons une opération qui s’appelle le produit tensoriel. Il s’écrit de la manière suivante :
Voici un exemple concret :
Pour 3 qubits, nous aurions la formule suivante :
Pour 3 qubits, nous avons 8 coefficients, pour 4 qubits nous en aurions 16… Vous commencez maintenant à comprendre l’origine de la puissance du calcul quantique. Pour n qubits, le registre peut stocker 2^n coefficients à la fois.
Là où le registre d’un ordinateur classique peut prendre la valeur 000, OU la valeur 001, OU 010, etc, le registre d’un ordinateur quantique les prend toutes en même temps.
S’il nous était capable d’effectuer des opérations sur ces coefficients et de récupérer le résultat, alors nous disposerions réellement d’une puissance de calcul en parallèle exponentielle.
Mais comme vous vous en souvenez de la propriété fondamentale de la mesure, elle détruit la superposition. Si nous mesurons un système à 3 qubits, nous obtiendrons soit 000, soit 001, 010, etc, mais nous n’aurons jamais accès aux coefficients. Et c’est bien là un problème de taille.
Intrication Quantique
Avant de terminer cet article, je dois revenir rapidement sur le phénomène étonnant qu’est l’intrication quantique.
Lorsque j’ai donné la formule du produit tensoriel, on remarque que les coefficients alpha et bêta sont multipliés entre eux. Or, le système à deux qubits doit être considéré comme un système à part entière.
Si le registre à deux qubits peut prendre les valeurs 00, 01, 10 et 11, alors il peut prendre toutes les combinaisons linéaires de ces valeurs. Et s’il peut prendre toutes les combinaisons linéaires de ces valeurs, alors il peut prendre, entre autres, la combinaison |01⟩ + |10⟩. Mais remarquez que dans la formule du produit tensoriel, le fait de prendre cette combinaison implique que les coefficients de la valeur |00⟩ et de la valeur |11⟩ soient nuls. Et pour que ces coefficients soient nuls, il est nécessaire que :
Or si alpha_0 ou bêta_0 est nul, alors on ne devrait pas pouvoir avoir la valeur de spin |01⟩, puisque son coefficient est alpha_0 * bêta_1.
Et pourtant on peut l’obtenir !
Autrement dit, le fait de “lier” deux qubits crée un nouveau système, le système à deux qubits, et les propriétés de ce système ne peuvent pas être réduites à la somme des propriétés des deux sous systèmes que l’on a liés. Le système global gagne des propriétés supplémentaires, qui émergent du fait de la liaison.
C’est cette liaison que l’on appelle l’intrication. Les deux qubits sont intriqués, lié par une “force” (non locale) et n’évolueront plus jamais indépendamment l’un de l’autre.
Conclusion
Nous sommes arrivés à la fin de ce premier article d’introduction à l’informatique quantique à travers les principes de base de la physique quantique, et comment ils sont utilisés pour fabriquer des qubits, composants élémentaires de l’ordinateur quantique.
Le prochain article traitera de la manière dont on programme un algorithme quantique. Vous verrez que les contraintes n’ont rien à voir avec celles de la programmation classique, et donc que tous nos programmes informatiques ne peuvent pas simplement être “recompilés” pour fonctionner sur l’ordinateur quantique.
Merci d’avoir pris le temps de la lecture.
