QAOA à l'échelle utilitaire

Regarde la vidéo sur le QAOA à l'échelle utilitaire d'Olivia Lanes, ou ouvre la vidéo dans une fenêtre séparée sur YouTube.

Aperçu de la leçon :

Jusqu'ici dans ce cours, nous espérons t'avoir fourni une base solide sur le cadre et les outils nécessaires pour résoudre des problèmes à l'échelle utilitaire sur un ordinateur quantique. Maintenant, nous allons enfin voir ces outils en action.

Dans cette leçon, nous allons nous salir les mains avec un exemple à l'échelle utilitaire du problème Max-Cut, qui est un problème célèbre en théorie des graphes portant sur la meilleure façon de partitionner un graphe en deux. Nous commencerons par un graphe simple à cinq nœuds pour développer notre intuition sur la manière dont un ordinateur quantique peut nous aider à résoudre ce problème, puis nous appliquerons cela à une version à l'échelle utilitaire du problème.

Cette leçon servira de vue d'ensemble de l'approche que nous adoptons pour résoudre ce problème. Il ne s'agira pas d'une présentation ligne par ligne du code. En accompagnement de cette leçon, il y a cependant un tutoriel avec du code réel que tu peux exécuter pour résoudre le problème Max-Cut sur un ordinateur quantique.

Le problème

Pour rappel, tous les problèmes de calcul ne sont pas adaptés à l'informatique quantique. Les « problèmes faciles » ne tireront aucun avantage de cette technologie, car les ordinateurs classiques sont déjà parfaitement capables de les résoudre.

Les trois cas d'utilisation qui nous rendent les plus optimistes sont :

1. la simulation de la nature
2. le traitement de données à structure complexe
3. l'optimisation

Aujourd'hui, nous allons nous concentrer sur le troisième cas d'utilisation : l'optimisation. Dans un problème d'optimisation, on cherche généralement la valeur la plus grande ou la plus petite possible pour une fonction donnée. La difficulté de trouver ces extrema avec des méthodes classiques peut croître de façon exponentielle à mesure que la taille du problème augmente.

Le problème d'optimisation qui nous intéresse aujourd'hui s'appelle Max-Cut, que nous allons résoudre avec un algorithme appelé Quantum Approximate Optimization Algorithm (QAOA).

Qu'est-ce que Max-Cut ?

On part d'un graphe, qui est constitué d'un ensemble de sommets (ou nœuds), dont certains sont reliés par des arêtes. Dans le problème, on nous demande de diviser les nœuds du graphe en deux sous-ensembles en « coupant » les arêtes qui les relient. On cherche la partition qui maximise le nombre d'arêtes ainsi coupées — d'où le nom « Max-Cut ».

Par exemple, la figure ci-dessus montre un graphe à cinq nœuds avec une solution Max-Cut à droite. Elle coupe cinq arêtes, ce qui est le mieux que l'on puisse faire avec ce graphe.

Comme un graphe à cinq nœuds est très petit, il n'est pas trop difficile de trouver le Max-Cut mentalement ou en essayant quelques coupes sur une feuille de papier. Mais comme tu peux l'imaginer, le problème devient de plus en plus difficile à mesure que le nombre de sommets augmente — en partie parce que le nombre de coupes possibles à considérer croît de façon exponentielle avec le nombre de nœuds. Et à partir d'un certain point, même les supercalculateurs ont du mal à le résoudre avec les algorithmes classiques connus.

Nous aimerions trouver un moyen de résoudre le problème Max-Cut pour ces graphes plus grands et plus complexes, car le problème a de nombreuses applications pratiques, notamment la détection de fraude en finance, le regroupement de graphes, la conception de réseaux et l'analyse des réseaux sociaux. Max-Cut est souvent rencontré comme sous-problème dans une approche particulière d'un problème plus large. Il est donc bien plus courant qu'on ne pourrait le penser naïvement.

La solution

Maintenant, nous allons parcourir l'approche que nous utilisons pour résoudre le problème Max-Cut sur un ordinateur quantique. Nous le ferons avec un graphe simple à cinq nœuds. Tu peux suivre à l'aide du tutoriel en notebook Python. Après cet exemple simple, le tutoriel te guidera à travers une version à l'échelle utilitaire du problème.

La première étape consiste à créer notre graphe en définissant le nombre de nœuds et les arêtes qui relient deux nœuds. Tu peux faire ça en important un package appelé rustworkx, comme illustré dans le tutoriel. Le résultat sera un graphe qui ressemble à ceci :

Nous allons utiliser le cadre Qiskit patterns pour trouver les solutions Max-Cut de ce graphe sur notre ordinateur quantique.

Mapper

Nous devons mapper le problème sur notre ordinateur quantique. Pour ce faire, notons d'abord que maximiser le nombre de coupes dans un graphe peut s'écrire mathématiquement comme :

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Où $i$ et $j$ sont des nœuds du graphe, et $x_i$ et $x_j$ valent 0 ou 1, selon de quel côté de la partition se trouve chaque nœud (un groupe est étiqueté « 0 » et l'autre « 1 »). Quand $x_i$ et $x_j$ sont du même côté de la partition, l'expression dans la somme est égale à zéro. Quand ils sont de côtés opposés, c'est-à-dire qu'il y a une coupe entre eux, l'expression est égale à un. Maximiser le nombre de coupes revient donc à maximiser la somme.

On peut aussi retourner ça et chercher le minimum en multipliant chacune des valeurs par moins un.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Nous sommes maintenant prêts à mapper. Passer d'un graphe comme celui que nous venons de dessiner à un circuit quantique peut sembler intimidant. Mais nous allons le faire étape par étape.

Rappelle-toi, nous allons essayer de résoudre Max-Cut en utilisant QAOA. Dans la méthodologie QAOA, on veut in fine disposer d'un opérateur (autrement dit, un Hamiltonien) qui représente la fonction de coût de notre algorithme hybride, ainsi qu'un circuit paramétré (l'ansatz) que nous utilisons pour représenter les solutions possibles au problème.

QUBO

Nous pouvons échantillonner ces solutions candidates et les évaluer à l'aide de la fonction de coût. Pour ce faire, nous tirons parti d'une série de reformulations mathématiques, dont la notation QUBO (Quadratic Unconstrained Binary Optimization), une façon utile d'encoder des problèmes d'optimisation combinatoire. En QUBO, on cherche à trouver :

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

où $Q$ est une matrice $n\times n$ de nombres réels, et $n$ correspond au nombre de nœuds dans notre graphe, ici cinq.

Pour appliquer QAOA, nous devons formuler notre problème sous forme d'Hamiltonien — c'est-à-dire une fonction ou matrice représentant l'énergie totale d'un système. Plus précisément, nous voulons créer un Hamiltonien de fonction de coût ayant la propriété que l'état fondamental corresponde à la valeur minimale de la fonction. Ainsi, pour résoudre notre problème d'optimisation, nous allons essayer de préparer l'état fondamental de $H$ sur un ordinateur quantique. Ensuite, échantillonner depuis cet état donnera la solution à $\min 𝑓(𝑥)$ avec une haute probabilité.

Mapper vers un Hamiltonien de fonction de coût

Il s'avère que nous avons de la chance, car le problème QUBO est très étroitement lié, et en fait computationnellement équivalent, à l'un des Hamiltoniens les plus célèbres et omniprésents en physique : l'Hamiltonien d'Ising.

Pour écrire le problème QUBO sous la forme de l'Hamiltonien d'Ising, tout ce que nous avons à faire est un simple changement de variables :

$$x_i = \frac{1-z_i}{2}.$$

Nous n'allons pas parcourir toutes les étapes ici, mais elles sont expliquées dans le notebook joint. En fin de compte, la minimisation de l'expression QUBO est la même que la minimisation de cette expression :

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

En réécrivant légèrement, nous obtenons notre Hamiltonien de fonction de coût, où le minimum de l'expression représente l'état fondamental, Z est l'opérateur de Pauli Z, et $b$ est un coefficient scalaire réel :

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Maintenant que nous avons notre Hamiltonien, nous devons le réécrire en termes d'opérateurs de Pauli ZZ à deux corps locaux, que nous pouvons facilement convertir en portes à deux qubits dans notre circuit quantique. Nous obtiendrons six objets — ou chaînes de Pauli — où chacun correspond à chacune des six arêtes du graphe. Chacun des cinq éléments d'une chaîne représente une opération sur un nœud — l'identité si le nœud n'est pas connecté à cette arête particulière, et l'opérateur de Pauli Z s'il l'est. Dans Qiskit, les chaînes de bits représentant les qubits sont indexées à l'envers. Par exemple, une arête entre les nœuds 0 et 1 est encodée comme IIIZZ, et une arête entre 2 et 4 est encodée comme ZIZII.

Construire le circuit quantique

Notre Hamiltonien étant écrit en termes d'opérateurs de Pauli, nous sommes prêts à construire notre circuit quantique, qui nous permet d'échantillonner de bonnes solutions à l'aide d'un ordinateur quantique :

L'algorithme QAOA s'inspire du théorème adiabatique, qui stipule que si l'on part de l'état fondamental d'un Hamiltonien dépendant du temps, que ce Hamiltonien évolue suffisamment lentement et qu'on lui laisse assez de temps, l'état final sera l'état fondamental du Hamiltonien final. QAOA peut être vu comme la version discrète et trotterisée de cet algorithme quantique adiabatique, où chaque étape de Trotter représente une couche de l'algorithme QAOA. Ainsi, au lieu de passer d'un état à l'autre, à chaque couche, nous allons alterner entre notre Hamiltonien de fonction de coût et un Hamiltonien dit « mixer », que nous aborderons plus loin dans cette leçon.

L'avantage du QAOA est qu'il est plus rapide que l'algorithme quantique adiabatique, mais il renvoie des solutions approximatives plutôt qu'optimales. Dans la limite où le nombre de couches tend vers l'infini, QAOA converge vers le cas QAA, mais cela est bien sûr très coûteux en calcul.

Pour créer notre circuit quantique, nous allons appliquer des opérateurs alternés, paramétrés par $\gamma$ et $\beta$, qui représenteront la discrétisation de l'évolution temporelle.

Ainsi, les trois parties principales du circuit QAOA sont :

1. l'état d'essai initial, en gris, qui est l'état fondamental du mixer, créé en appliquant une porte Hadamard à chaque qubit
2. l'évolution par la fonction de coût, que nous avons discutée précédemment, en violet foncé
3. l'évolution sous le Hamiltonien mixer, que nous n'avons pas encore abordé, en violet clair.

Notre Hamiltonien de départ est appelé le Mixer car son état fondamental est la superposition de toutes les chaînes de bits possibles d'intérêt : il impose ainsi un mélange de toutes les solutions possibles au départ.

Le Hamiltonien mixer est la somme simple des opérations de Pauli-X sur chaque nœud du graphe. Qiskit te permet d'utiliser un opérateur mixer personnalisé différent si tu le souhaites, mais nous allons utiliser l'opérateur standard ici. Encore une fois, tu peux voir qu'avec Qiskit, une grande partie du travail est déjà fait pour nous, ce qui rend triviale la définition du Hamiltonien mixer et de l'état de départ. Le seul travail que nous avions à faire était de trouver la fonction de coût.

Chaque itération de ces opérateurs est appelée une couche. Ces couches peuvent être vues comme une discrétisation de l'évolution temporelle du système, comme décrit précédemment. Le motif alternant découle de la décomposition de Trotter et approxime les fonctions exponentielles de matrices non commutantes. En général, plus on inclut de couches ou d'étapes, plus on se rapproche de l'évolution temporelle continue, comme dans QAA, donc en théorie, plus le résultat sera précis. Mais pour cet exemple, nous allons commencer par échantillonner avec une seule couche. Rappelle-toi que le Hamiltonien de fonction de coût et le mixer sont tous deux paramétrés — nous devons encore trouver des valeurs optimales pour $\gamma$ et $\beta.$

Optimiser

Bien que le circuit que nous venons de créer paraisse assez simple et soit utile pour développer une compréhension intuitive, souviens-toi que la puce quantique ne comprend pas ce qu'est la porte QAOA. Nous devons convertir cela en une série de portes natives à un ou deux qubits qui peuvent être exécutées directement sur le matériel. Les portes natives sont celles qui peuvent être exécutées directement sur les qubits. De tels circuits sont dits écrits dans l'architecture d'ensemble d'instructions (ISA) du backend.

La bibliothèque Qiskit offre une série de passes de transpilation adaptées à un large éventail de transformations de circuits. Nous voulons nous assurer que le circuit est optimisé pour notre usage.

Rappelle-toi de notre leçon précédente que le processus de transpilation comporte plusieurs étapes :

• Le mappage initial des qubits du circuit (c'est-à-dire les variables de décision) vers les qubits physiques du dispositif.
• Le déroulement des instructions du circuit quantique vers les instructions natives du matériel que le backend comprend.
• Le routage de tout qubit du circuit qui interagit vers des qubits physiques adjacents les uns aux autres.

Et comme toujours, plus de détails à ce sujet peuvent être trouvés dans la documentation.

Avant de transpiler, cependant, nous devons choisir sur quel backend nous allons exécuter notre circuit, car le transpiler optimise différemment selon les processeurs. C'est là encore une raison pour laquelle il est important d'utiliser un transpiler automatisé — tu ne voudrais pas passer par le processus fastidieux d'optimisation manuelle de ton circuit, pour réaliser ensuite que tu veux en fait l'exécuter sur un processeur différent aux propriétés différentes.

Passe le backend de ton choix dans la fonction de transpilation et spécifie ton niveau d'optimisation. Dans le tutoriel, tu sélectionneras le niveau 3, qui est le niveau le plus élevé et le plus approfondi.

Et avec ça, nous avons un circuit transpilé prêt à être exécuté sur le matériel !

Exécuter

Jusqu'ici, nous avons transpilé le circuit en laissant les paramètres gamma et beta inchangés — mais nous ne pouvons pas vraiment exécuter le circuit sans spécifier ces paramètres. Dans le workflow QAOA, les paramètres QAOA optimaux sont trouvés dans une boucle d'optimisation itérative, où nous exécutons une série d'évaluations du circuit puis utilisons un optimiseur classique pour trouver les paramètres optimaux 𝛽 et 𝛾. Cependant, il faut bien commencer quelque part, donc nous faisons une estimation initiale de $\gamma=\pi/2$ et $\beta=\pi.$

Modes d'exécution

Nous sommes maintenant presque prêts à exécuter le circuit — promis ! Mais d'abord, il est important de noter que tu peux envoyer ta tâche de différentes façons, que l'on appelle les modes d'exécution.

• Mode Job : Une seule requête primitive de l'estimateur ou du sampler est effectuée sans gestionnaire de contexte. Les circuits et les entrées sont regroupés en blocs unifiés primitifs (PUBs) et soumis comme tâche d'exécution sur l'ordinateur quantique.

• Mode batch : Un gestionnaire multi-tâches pour exécuter efficacement une expérience composée d'un ensemble de tâches indépendantes. Utilise le mode batch pour soumettre plusieurs tâches primitives simultanément.

• Mode session : Une fenêtre dédiée pour exécuter une charge de travail multi-tâches. Cela permet aux utilisateurs d'expérimenter avec des algorithmes variationnels de manière plus prévisible, et même d'exécuter plusieurs expériences simultanément, en tirant parti du parallélisme dans la pile. Utilise les sessions pour les charges de travail itératives ou les expériences nécessitant un accès dédié. Voir Run jobs in a session pour des exemples.

Pour une expérience QAOA, une session serait un bon choix si tu y as accès, puisque nous devons échantillonner notre circuit de nombreuses fois avec des valeurs de paramètres différentes pour trouver l'optimum.

Revenons au problème d'optimisation. Nous devons trouver de meilleures valeurs de gamma et beta que nos premières estimations approximatives. Nous allons le faire en injectant notre fonction de coût et ces estimations initiales dans un optimiseur scipy COBYLA.

Tu peux voir ici la valeur de la fonction de coût au fil des itérations. Elle commence de façon un peu erratique, monte et descend, puis se stabilise à une valeur basse. Nous allons utiliser les valeurs trouvées par scipy qui correspondent à l'évaluation la plus basse de la fonction de coût.

Maintenant que nous avons pu réduire notre fonction de coût en trouvant de meilleures valeurs de nos paramètres, nous allons exécuter notre circuit avec les nouvelles valeurs que nous avons trouvées pour gamma et beta. J'ai listé les valeurs spécifiques que j'utilise ici, mais souviens-toi que quand tu essaieras ou même si tu réexécutes simplement le même notebook de tutoriel, ces valeurs pourraient changer légèrement. Nous allons maintenant exécuter notre circuit optimisé avec ces valeurs et trouver notre solution candidate à notre problème Max-Cut.

Dans la phase de post-traitement, nous allons analyser les données et afficher ces résultats pour voir si notre algorithme quantique a trouvé les bonnes solutions.

Post-traitement

Traçons maintenant un histogramme des données pour examiner la solution finale :

Les chaînes de bits représentent la façon dont chacun des nœuds a été partitionné en deux groupes (étiquetés « 0 » et « 1 ») par la coupe. Il devrait y avoir quatre solutions qui donnent toutes la valeur maximale d'arêtes coupées. Ces quatre solutions sont affichées en violet. Tu peux voir immédiatement que 4 solutions sont bien plus probables que toutes les autres. La chaîne de bits la plus haute, et donc la plus probable, est 0,1,0,1,1. (Souviens-toi — l'ordre des qubits est inversé dans les chaînes de bits du graphe !)

À partir de ce graphe, nous pouvons prendre la chaîne de bits la plus probable et la représenter comme un graphe partitionné, avec la coupe passant par cinq arêtes :

C'est bien une solution Max-Cut. Mais ce n'est pas la seule ! En raison de la symétrie de ce graphe, il existe plusieurs solutions correctes. Au lieu d'avoir les nœuds 0 et 3 à l'intérieur de la coupe, on pourrait avoir les nœuds 2 et 4. Tu peux voir que tout ce que j'ai eu à faire, c'est de faire pivoter ma coupe pour inclure ces nouveaux points. Le nombre d'arêtes coupées reste cinq. Il s'avère qu'il y a quatre solutions Max-Cut, puisque chacune des deux solutions que nous avons notées possède également un partenaire « opposé », où les nœuds violets sont gris et les nœuds gris sont violets — la coupe reste la même, mais chaque nœud bascule effectivement vers le côté opposé de la partition.

Regardons encore une fois l'histogramme et les quatre solutions les plus probables un instant. Idéalement, elles correspondraient chacune aux quatre vraies solutions Max-Cut. Le problème est que l'algorithme n'a pas identifié la quatrième et dernière solution comme faisant partie des 4 réponses les plus probables. Elle était la cinquième plus probable. La quatrième solution identifiée par l'algorithme est incorrecte — si tu la dessinais, tu verrais que la solution n'a que quatre coupes.

Mais souviens-toi : c'est un algorithme approximatif. Il n'est pas infaillible et n'est pas correct 100 % du temps. Tu dois faire appel à ta propre connaissance et compréhension pour vérifier la cohérence des solutions.

Cette erreur peut provenir de plusieurs endroits :

1. Cela pourrait être la nature approximative de l'algorithme lui-même, et le petit nombre de couches que j'ai utilisées.
2. Cela pourrait être une erreur d'échantillonnage fini, qui pourrait être réduite en augmentant le nombre de shots dans mon expérience.
3. Cela pourrait aussi être une erreur de lecture, puisque la quatrième vraie solution ne diffère que d'un seul bit.

Ce type d'analyse des erreurs est ce qu'il faut pour devenir un praticien de l'informatique quantique. Tu dois comprendre les performances du matériel et comment celui-ci peut contribuer à certains types d'erreurs et comment les corriger.

Cependant, n'oublions pas qu'il y avait 32 chaînes de bits possibles, et que les quatre vraies solutions se trouvaient dans les cinq meilleurs candidats. Et nous n'avons utilisé que deux couches pour trouver ça. En général, si nous voulions augmenter nos chances de trouver le meilleur Max-Cut à chaque fois, nous pourrions augmenter la profondeur des couches. Il y a quelques subtilités à cela, mais c'est pour une leçon ultérieure.

À l'échelle utilitaire

Maintenant que tu as eu un aperçu du processus de résolution d'un petit problème Max-Cut sur un ordinateur quantique, je te mets au défi de le faire à grande échelle. Suis le tutoriel lié pour voir combien de coupes tu peux obtenir dans un graphe à 125 nœuds.