QAOA à l'échelle industrielle

Regardez la vidéo d'Olivia Lanes sur le QAOA à l'échelle des services publics, ou ouvrez la vidéo dans une fenêtre séparée sur YouTube.

Aperçu de la leçon :

Jusqu'à présent, dans ce cours, nous espérons vous avoir donné une base solide du cadre et des outils nécessaires pour résoudre des problèmes à grande échelle sur un ordinateur quantique. Aujourd'hui, nous allons enfin voir ces outils en action.

Dans cette leçon, nous allons nous plonger dans un exemple à grande échelle du problème du « max-cut », un problème célèbre de la théorie des graphes qui consiste à déterminer la meilleure façon de diviser un graphe en deux. Nous commencerons par un graphe simple à cinq nœuds afin de mieux comprendre comment un ordinateur quantique peut nous aider à résoudre le problème, puis nous appliquerons cette approche à une version à grande échelle du problème.

Cette leçon vous donnera un aperçu général de la méthode que nous utilisons pour résoudre ce problème. Il ne s'agira pas ici d'une analyse détaillée du code. Cette leçon s'accompagne toutefois d'un tutoriel contenant du code réel que vous pouvez exécuter pour résoudre le problème du « max-cut » sur un ordinateur quantique.

Le problème

Pour rappel, tous les problèmes de calcul ne se prêtent pas à 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 que nous envisageons avec le plus d'optimisme sont les suivants :

simuler la nature
le traitement de données à structure complexe
optimisation

Aujourd'hui, nous allons nous concentrer sur le troisième cas d'utilisation, l'optimisation. Dans un problème d'optimisation, nous recherchons généralement la plus grande ou la plus petite valeur possible pour une fonction donnée. La difficulté de trouver ces extrema avec les méthodes classiques peut augmenter 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 le « max-cut »; nous allons le résoudre à l'aide d'un algorithme appelé « Quantum Approximate Optimization Algorithm » (QAOA).

Qu'est-ce que le max-cut?

Nous commençons par un graphe, qui est constitué d'un ensemble de sommets (ou nœuds), dont certains sont reliés par des arêtes. Dans cet exercice, on nous demande de diviser les nœuds du graphe en deux sous-ensembles en « coupant » les arêtes qui les relient. Nous voulons trouver la partition qui maximise le nombre d'arêtes coupées de cette manière – d'où le nom de « max-cut »

Illustration d'un problème de coupe maximale

Par exemple, la figure ci-dessus représente un graphe à cinq nœuds, avec la solution du coup maximal indiquée à droite. Il traverse cinq arêtes, ce qui est le maximum possible avec ce graphe.

Comme un graphe à cinq nœuds est très petit, il n'est pas trop difficile de déterminer la coupe maximale de tête ou en essayant quelques coupes sur une feuille de papier. Mais comme vous pouvez 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 coupures possibles à prendre en compte croît de manière exponentielle avec le nombre de nœuds. Et à un certain stade, cela devient difficile, même pour les supercalculateurs, à réaliser avec les algorithmes classiques connus.

Nous aimerions trouver un moyen de résoudre le problème du coupure maximale pour ces graphes plus grands et plus complexes, car ce problème a de nombreuses applications pratiques, notamment la détection des fraudes dans le secteur financier, le regroupement de graphes, la conception de réseaux et l'analyse des réseaux sociaux. Le problème de Max-cut apparaît souvent comme un sous-problème dans le cadre d'une approche particulière d'un problème plus vaste. C'est donc bien plus courant qu'on pourrait le croire naïvement.

La solution

Nous allons maintenant vous présenter la méthode que nous utilisons pour résoudre le problème du coupure maximale sur un ordinateur quantique. Nous allons le faire à l'aide d'un graphe simple à cinq nœuds. Vous pouvez suivre ce tutoriel à l'aide du notebook Python. Après cet exemple simple, le tutoriel vous guidera à travers un exemple à grande échelle de ce 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. Vous pouvez le faire en important un paquetage appelé rustworkx, comme le montre le tutoriel. Le résultat sera un graphique qui ressemblera à celui-ci :

Résultat du graphique « max-cut » de Rustworkx

Nous utiliserons le framework Qiskit Patterns pour trouver les solutions de coupe maximale pour ce graphe sur notre ordinateur quantique.

Mappe

Nous devons transposer le problème sur notre ordinateur quantique. Pour ce faire, notons tout d'abord que la maximisation du nombre de coupes dans un graphique peut s'écrire mathématiquement comme suit :

\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$ sont soit 0, soit 1, selon le côté de la partition où se trouve chaque nœud (un groupe est étiqueté "0" et un autre "1"). Lorsque $x_i$ et $x_j$ se trouvent du même côté de la cloison, l'expression de la somme est égale à zéro. Lorsqu'ils sont sur des côtés opposés, et qu'il y a donc une coupure entre eux, l'expression est égale à un. Ainsi, en maximisant le nombre de coupes, on maximise la somme.

Nous pouvons également inverser la situation et rechercher le minimum en multipliant chacune des valeurs par un chiffre négatif.

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

Nous sommes maintenant prêts à cartographier. Il peut être assez décourageant de penser à la manière de passer d'un graphique comme celui que nous venons de dessiner à un circuit quantique. Mais nous allons procéder étape par étape.

N'oubliez pas que nous allons essayer de résoudre le problème du max-cut à l'aide de l'algorithme QAOA. Dans la méthodologie QAOA, notre objectif final est d'obtenir un opérateur (ou, en d'autres termes, un hamiltonien) qui servira à représenter 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 prélever un échantillon de 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, notamment la notation Quadratic Unconstrained Binary Optimization - ou QUBO en abrégé - qui est un moyen utile d'encoder les problèmes d'optimisation combinatoire. Dans QUBO, nous voulons trouver :

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

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

Pour appliquer le QAOA, nous devons formuler notre problème sous la forme d'un hamiltonien, qui est une fonction ou une 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 qui a la propriété que l'état fondamental correspond à la valeur minimale de la fonction. Pour résoudre notre problème d'optimisation, nous allons donc essayer de préparer l'état fondamental de $H$ sur un ordinateur quantique. L'échantillonnage de cet état permet alors d'obtenir la solution de $\min 𝑓(𝑥)$ avec une forte probabilité.

Mappage vers une fonction de coût hamiltonienne

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

Afin d'écrire le problème QUBO sous la forme du hamiltonien d'Ising, tout ce que nous avons à faire est de procéder à un simple changement de variables :

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

Nous ne détaillerons pas toutes les étapes ici, mais elles sont expliquées dans le carnet de notes ci-joint. Au final, 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 fonction de coût hamiltonienne, où le minimum de l'expression représente l'état fondamental, Z est l'opérateur Z de Pauli 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 ZZ de Pauli à deux localisations, que nous pouvons facilement convertir en portes à deux qubits dans notre circuit quantique. Nous obtiendrons six objets - ou chaînes de Pauli - dont 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 Z de Pauli 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, si l'hamiltonien évolue suffisamment lentement et si l'on dispose de suffisamment de temps, l'état final sera l'état fondamental de l'hamiltonien final. Le QAOA peut être considéré comme la version discrète et trotterisée de cet algorithme adiabatique quantique, où chaque étape trotterisée représente une couche de l'algorithme QAOA. Ainsi, au lieu d'évoluer d'un état à l'autre, dans chaque couche, nous alternerons entre notre hamiltonien de fonction de coût et un hamiltonien dit "mélangeur", que nous aborderons plus tard dans cette leçon.

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

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

Les trois parties principales du circuit de l'AQAO sont donc les suivantes :

l'état d'essai initial, en gris, qui est l'état de base du mélangeur, créé par l'application d'une porte de Hadamard à chaque qubit
l'évolution de la fonction de coût, dont nous avons parlé précédemment, en violet foncé
l'évolution sous l'hamiltonien mélangeur, que nous n'avons pas encore abordé, en violet clair.

Notre hamiltonien de départ est appelé Mixer car son état fondamental est la superposition de toutes les chaînes de bits possibles : il s'agit donc d'un mélange de toutes les solutions possibles au départ.

L'hamiltonien du mélangeur est la simple somme des opérations de Pauli-X sur chaque nœud du graphe. Qiskit vous permet d'utiliser un opérateur de mixage différent et personnalisé si vous le souhaitez, mais nous allons utiliser l'opérateur standard ici. Encore une fois, vous pouvez constater qu'avec Qiskit, une grande partie du travail est supprimée pour nous, ce qui rend trivial l'obtention de l'hamiltonien du mélangeur et de l'état de départ. Le seul travail à faire est de trouver la fonction de coût.

Chaque itération de ces opérateurs est appelée une couche. Ces couches peuvent être considérées comme une discrétisation de l'évolution temporelle du système, comme décrit précédemment. Le modèle alternatif provient de la décomposition de Trotter et approxime les fonctions exponentielles des matrices non commutatives. En général, plus nous incluons de couches ou d'étapes, plus nous nous rapprochons d'une évolution temporelle continue, comme dans l'AQR, et donc, en théorie, plus le résultat sera précis. Mais pour cet exemple, nous commencerons par échantillonner avec une seule couche. N'oubliez pas que l'hamiltonien de la fonction de coût et le mélangeur 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 semble assez simple et qu'il soit utile pour construire une compréhension intuitive, n'oubliez pas que la puce quantique ne comprend pas ce qu'est la porte QAOA. Nous devons transformer 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. Ces circuits sont censés être écrits dans l'architecture d'ensemble d'instructions (ISA) du backend.

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

Rappelons que le processus de transpilation comporte plusieurs étapes :

Mappage initial des qubits du circuit (c'est-à-dire des variables de décision) aux qubits physiques de l'appareil.
Déroulement des instructions dans le circuit quantique vers les instructions matérielles natives que le backend comprend.
Routage de tous les qubits du circuit qui interagissent vers des qubits physiques adjacents.

Et comme toujours, vous trouverez plus de détails à ce sujet dans la documentation.

Avant de transpiler, nous devons cependant choisir le backend sur lequel nous allons exécuter notre circuit, car le transpilateur optimise différemment selon les processeurs. C'est une autre raison pour laquelle il est important d'utiliser un transpileur automatisé - vous ne voudriez pas passer par le processus fastidieux d'optimisation de votre circuit à la main, pour vous rendre compte ensuite que vous voulez en fait faire fonctionner votre circuit sur un processeur différent, avec des propriétés différentes.

Passez le backend de votre choix à travers la fonction transpiler et spécifiez votre niveau d'optimisation. Dans le didacticiel, vous choisirez le niveau 3, qui est le niveau le plus élevé et le plus approfondi.

Et voilà, nous avons un circuit transpilé qui est prêt à être exécuté sur le matériel!

Exécuter

Jusqu'à présent, nous avons transposé le circuit en ne tenant pas compte des paramètres gamma et bêta - mais nous ne pouvons pas faire fonctionner le circuit sans spécifier ces paramètres. Dans le flux de travail de QAOA, les paramètres optimaux de QAOA sont trouvés dans une boucle d'optimisation itérative, où nous effectuons une série d'évaluations de circuits et utilisons ensuite un optimiseur classique pour trouver les paramètres 𝛽 et 𝛾 optimaux. Cependant, il faut bien commencer quelque part, et nous faisons donc une première estimation de $\gamma=\pi/2$ et de $\beta=\pi.$

modes d'exécution

Maintenant, nous sommes presque prêts à faire fonctionner le circuit - je vous le promets! Mais tout d'abord, il est important de noter que vous pouvez envoyer votre travail de différentes manières, appelées modes d'exécution.

Mode de travail : une seule requête est envoyée à la primitive Estimator ou Sampler, sans gestionnaire de contexte. Les circuits et les entrées sont regroupés sous forme de blocs primitifs unifiés (PUB) et soumis sous forme de tâche d'exécution sur l'ordinateur quantique.
Mode batch : Un gestionnaire de tâches multiples permettant d'exécuter efficacement une expérience composée d'un ensemble de tâches indépendantes. Utilisez le mode batch pour soumettre simultanément plusieurs travaux primitifs
Mode session : Une fenêtre dédiée à l'exécution d'une charge de travail à plusieurs tâches. Cela permet aux utilisateurs d'expérimenter les algorithmes variationnels d'une 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. Utilisez les sessions pour les charges de travail itératives ou les expériences qui nécessitent un accès dédié. Pour des exemples, voir Exécuter des tâches dans une session.

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

Revenons au problème d'optimisation. Nous devons trouver de meilleures valeurs de gamma et de bêta que nos premières estimations approximatives. Pour ce faire, nous introduirons notre fonction de coût et ces suppositions initiales dans un optimiseur scipy COBYLA.

Vous pouvez voir ici la valeur de la fonction de coût au fil des itérations. Elle commence par être un peu bizarre, monte et descend, puis se stabilise à une valeur basse. Nous utiliserons les valeurs trouvées par scipy qui correspondent à l'évaluation la plus basse de la fonction de coût.

Maintenant que nous avons réussi à réduire notre fonction de coût en trouvant de meilleures valeurs pour nos paramètres, nous allons faire fonctionner notre circuit en utilisant les nouvelles valeurs que nous avons trouvées pour gamma et bêta. J'ai indiqué ici les valeurs précises que j'utilise, mais n'oubliez pas que lorsque vous vous y essaierez vous-même ou même si vous vous contentez de relancer le même notebook de tutoriel, ces valeurs pourraient varier légèrement. Nous allons maintenant exécuter notre circuit optimisé avec ces valeurs et trouver une solution candidate à notre problème de coupe maximale.

Dans la phase de post-traitement, nous analyserons les données et afficherons 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 manière dont chacun des nœuds a été divisé en deux groupes (étiquetés "0" et "1") par la coupe. Il devrait y avoir quatre solutions qui donnent toutes la valeur maximale des arêtes coupées. Les quatre sont représentés en violet. On voit tout de suite que 4 solutions sont beaucoup plus probables que n'importe laquelle des autres. La solution la plus élevée, et donc la plus probable, est 0,1,0,1,1. (N'oubliez pas que l'ordre des qubits est inversé dans les chaînes de bits de l'intrigue!)

À partir de ce tracé, nous pouvons prendre la chaîne de bits la plus probable et la représenter sous la forme d'un graphe partitionné, dont la coupe passe par cinq arêtes :

Il s'agit donc bien d'une solution de coupe maximale. Mais ce n'est pas le seul! En raison de la symétrie de ce graphique, il existe plusieurs solutions valables. Au lieu d'inclure les nœuds 0 et 3 dans la coupure, on pourrait inclure les nœuds 2 et 4. Comme vous pouvez le voir, il m'a suffi de faire pivoter ma découpe pour y inclure ces nouveaux points. Le nombre d'arêtes coupées reste de cinq. Il s'avère qu'il existe quatre solutions de coupure maximale, car chacune des deux solutions que nous avons notées a également un « pendant » : les nœuds violets deviennent gris et les nœuds gris deviennent violets. La coupure reste donc la même, mais chaque nœud passe en fait de l'un des côtés de la partition à l'autre.

Revenons un instant sur l'histogramme et les quatre solutions les plus probables. Idéalement, il s'agirait des quatre solutions de coupe maximale réelles. Le problème, c'est que l'algorithme n'a en fait pas classé la quatrième et dernière solution parmi les quatre réponses les plus probables. C'était la cinquième option la plus probable. La quatrième solution identifiée par l'algorithme est incorrecte : si vous la dessiniez, vous verriez qu'elle ne comporte que quatre découpes.

Mais n'oubliez pas qu'il s'agit d'un algorithme approximatif. Elle n'est pas infaillible et n'est pas correcte dans 100 % des cas. Vous devez faire appel à vos propres connaissances et à votre propre compréhension pour vérifier le bien-fondé des solutions.

Cette erreur peut avoir plusieurs origines :

Cela pourrait être dû à la nature approximative de l'algorithme lui-même et au petit nombre de couches que j'ai utilisées.
Il pourrait s'agir d'une erreur d'échantillonnage finie, qui pourrait être réduite si j'augmentais le nombre de prises de vue dans mon expérience.
Il pourrait également s'agir d'une erreur de lecture, puisque la quatrième solution réelle n'est décalée que d'un bit.

C'est ce type d'analyse des erreurs qui est nécessaire pour devenir un praticien de l'informatique quantique. Vous devez comprendre les performances du matériel et la manière dont elles peuvent contribuer à certains types d'erreurs et comment les corriger.

Cependant, n'oublions pas qu'il y avait 32 combinaisons binaires possibles et que les quatre solutions réelles figuraient parmi les cinq meilleurs candidats. Et nous n'avons utilisé que deux couches pour arriver à ce résultat. En général, si nous voulions augmenter nos chances de trouver à chaque fois le meilleur max-cut, nous pourrions augmenter la profondeur de la couche. Il y a quelques subtilités à ce sujet, mais nous en parlerons dans une leçon ultérieure.

À l'échelle industrielle

Maintenant que vous avez eu un aperçu de la manière dont on résout un petit problème de coupe maximale sur un ordinateur quantique, je vous mets au défi de le faire à plus grande échelle. Suivez le tutoriel accessible via le lien pour découvrir combien de coupures vous pouvez obtenir dans un graphe à 125 nœuds.

Cette page a-t-elle été utile ?

Signaler un bogue, une coquille ou proposer du contenu sur GitHub.