Quantum circuit evolutionary framework applied on set partitioning problem

Cet article propose un cadre évolutif de circuits quantiques exploitant une topologie variable et un terme évolutif pseudo-contre-adiabatique pour résoudre efficacement des problèmes de partition d'ensemble en surmontant la stagnation de la convergence et en éliminant le besoin d'optimiseurs classiques.

L'essentiel

Imaginez que vous essayez de résoudre un puzzle massif et complexe. L'objectif est de diviser un groupe de personnes (comme des équipages de ligne aérienne) en équipes afin que chaque vol soit couvert exactement une fois, sans aucun chevauchement ni créneau manquant, tout en maintenant les coûts au plus bas. Dans le monde des mathématiques, cela s'appelle le problème de partition d'ensemble. C'est un défi notoirement difficile qui devient exponentiellement plus complexe à mesure que vous ajoutez plus de personnes et de vols.

Ce papier présente une nouvelle méthode permettant aux ordinateurs quantiques de relever ce défi. Au lieu d'utiliser la « recette » standard suivie par la plupart des algorithmes quantiques, les auteurs ont construit un cadre permettant à l'ordinateur d'évoluer sa propre recette au fur et à mesure de son travail.

Voici une décomposition de leur approche à l'aide d'analogies simples :

1. L'ancienne méthode : Le « plan fixe » (VQE)

La plupart des algorithmes quantiques actuels, comme l'estimateur variationnel d'état propre (VQE), fonctionnent comme un chef suivant un livre de recettes strict et immuable.

• La configuration : La structure du « circuit » (les étapes que l'ordinateur suit) est fixe. Vous ne pouvez ni ajouter ni retirer d'ingrédients ; vous ne pouvez qu'ajuster les quantités (les paramètres).
• Le problème : À mesure que le puzzle s'agrandit, le chef se retrouve souvent coincé dans une « vallée plate ». Imaginez marcher dans un champ brumeux où le sol est parfaitement plat. Peu importe la direction dans laquelle vous faites un pas, vous ne montez ni ne descendez. Vous ne pouvez pas dire si vous vous rapprochez de la solution ou non. En physique quantique, cela s'appelle un plateau aride. L'ordinateur cesse d'apprendre car il ne peut trouver de direction pour s'améliorer.

2. La nouvelle méthode : Le « sculpteur évolutif » (QCE)

Les auteurs proposent un cadre appelé évolution de circuit quantique (QCE). Au lieu d'une recette fixe, imaginez un sculpteur qui commence avec un petit bloc d'argile et qui a le droit d'ajouter, de retirer ou de remodeler l'argile à chaque étape.

• Fonctionnement : L'ordinateur commence avec un circuit très simple (peut-être une seule porte). Il crée ensuite une « famille » de versions légèrement différentes de lui-même en mutuant aléatoirement la structure (ajouter une nouvelle étape, supprimer une ancienne, ou modifier une connexion).
• La sélection : Il teste toutes ces versions. Celle qui résout le mieux le puzzle survit pour devenir le « parent » du prochain tour. Les autres sont éliminées.
• L'avantage : Parce que la structure elle-même change, l'ordinateur n'est pas coincé dans une vallée plate. Il peut remodeler toute son approche pour trouver un chemin hors du brouillard.

3. Les deux stratégies testées

Le papier a testé deux saveurs spécifiques de cette approche de « sculpteur évolutif » :

• Stratégie A : L'évolutionniste pur (sans ansatz)
  Cette version commence avec presque rien et laisse l'ordinateur déterminer la structure entièrement par essais et erreurs, un peu comme la sélection naturelle. Elle ne devine pas à quoi la solution devrait ressembler ; elle évolue simplement jusqu'à ce que cela fonctionne.

• Stratégie B : L'évolutionniste inspiré par la physique (pseudo-contre-diabatique)
  C'est la « star » du papier. Les auteurs ont donné à l'ordinateur un indice basé sur la physique du problème. Ils ont ajouté une « pousse » spéciale (appelée terme pseudo-contre-diabatique) au circuit.

  • L'analogie : Imaginez que vous essayez de pousser une lourde boîte en haut d'une colline. L'« évolutionniste pur » pousse simplement au hasard jusqu'à trouver un moyen de monter. La version « inspirée par la physique » connaît la forme de la colline et ajoute une force contre-spécifique pour maintenir la boîte en mouvement fluide, l'empêchant de rester coincée dans les zones plates.
  • Le résultat : Cette stratégie a donné les meilleurs résultats. Elle a évité la sensation de « blocage » (stagnation de la convergence) bien mieux que les autres méthodes, même lorsque le puzzle était très grand.

4. Les résultats

Les auteurs ont testé ces méthodes sur un simulateur (un programme informatique qui agit comme un ordinateur quantique) en utilisant 35 versions différentes du puzzle de planification des équipages aériens.

• Le gagnant : La méthode d'évolution inspirée par la physique (APCD-QCE) a constamment trouvé de meilleures solutions que la méthode standard du « plan fixe » (VQE).
• Le point de blocage : Bien que les nouvelles méthodes soient bien meilleures, elles ont toujours eu du mal lorsque le puzzle est devenu extrêmement grand (environ 20 qubits). Même le sculpteur évolutif a parfois manqué de temps ou de complexité pour trouver la solution parfaite.
• Bruit : Ils ont également testé ce qui se passe lorsque l'ordinateur fait des erreurs (simulant le « bruit » du monde réel). Les nouvelles méthodes ont tenu assez bien, bien que les performances aient diminué, ce qui est attendu.

La conclusion

Le papier affirme qu'en permettant à un circuit quantique de changer sa propre forme plutôt que de simplement ajuster ses paramètres, nous pouvons éviter les « impasses » qui piègent les algorithmes actuels. Plus précisément, l'ajout d'une « pousse » basée sur la physique à ce processus évolutif aide l'ordinateur à trouver de meilleures solutions plus rapidement.

Bien que cela ne résolve pas encore tous les problèmes (en particulier les plus grands), cela offre une nouvelle voie prometteuse pour utiliser les ordinateurs quantiques afin de résoudre des problèmes d'optimisation complexes comme la planification et la gestion des ressources, permettant potentiellement de contourner la nécessité pour les ordinateurs classiques de faire le gros du travail d'optimisation.

Résumé technique

Résumé technique : Cadre évolutionnaire de circuits quantiques appliqué au problème de partitionnement d'ensembles

Définition du problème
L'article traite du problème de partitionnement d'ensembles (SPP), un défi d'optimisation combinatoire NP-difficile bien connu. Le SPP consiste à diviser un ensemble d'éléments en sous-ensembles mutuellement exclusifs et exhaustifs afin de minimiser le poids total tout en garantissant que chaque élément appartient à exactement un sous-ensemble. Les applications pratiques incluent la planification des équipages aériens. Pour résoudre ce problème sur du matériel quantique, les auteurs formulent le SPP comme un problème d'optimisation binaire quadratique sans contrainte (QUBO), qui est ensuite mappé sur un hamiltonien d'Ising. L'étude cible spécifiquement les limitations des algorithmes quantiques variationnels (VQA) actuels, tels que le solveur d'états propres variationnel quantique (VQE), qui souffrent souvent de « plateaux stériles » — un phénomène où les gradients s'annulent de manière exponentielle à mesure que le nombre de qubits augmente, entraînant une stagnation de la convergence.

Méthodologie
Les auteurs proposent un cadre de circuit quantique évolutionnaire (QCE) qui s'écarte de l'approche VQE standard. Contrairement au VQE, qui utilise une topologie de circuit fixe (ansatz) avec des paramètres variables optimisés par un optimiseur classique, le cadre QCE fait évoluer la topologie du circuit elle-même. L'étude évalue deux stratégies distinctes au sein de ce cadre :

1. Évolution de circuit quantique sans ansatz (AF-QCE) :

   • Inspirée de la littérature précédente [13], cette approche commence par un circuit minimal (une seule porte aléatoire) et évolue de manière itérative sans ansatz prédéfini.
   • L'évolution repose sur des opérations de mutation : INSERTION (ajouter une porte), SUPPRESSION (retirer une porte), ÉCHANGE (remplacer une porte) et MODIFICATION (ajuster les paramètres de la porte).
   • Une population de circuits est générée, mesurée, et le circuit le plus performant est sélectionné comme parent pour la génération suivante, assurant une réduction monotone de la fonction de coût.

2. Ansatz avec terme évolutionnaire pseudo-contre-adiabatique (APCD-QCE) :

   • Cette approche intègre une structure inspirée de la physique dans l'ansatz pour améliorer la convergence. Elle utilise un hamiltonien $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$, où $H_{ad}$ représente un hamiltonien d'évolution temporelle adiabatique et $H_{pcd}$ est un terme évolutionnaire pseudo-contre-adiabatique.
   • L'opérateur unitaire est défini comme $U = U_{ad}U_{pcd}$. La composante $U_{ad}$ est fixe (une étape de Trotter), tandis que $U_{pcd}$ est évoluée en utilisant la même stratégie de mutation évolutionnaire que l'AF-QCE.
   • La préparation de l'état initial utilise $|+\rangle^{\otimes n}$, et des paramètres spécifiques ($\beta=0, \delta=0.5$) sont appliqués pour faciliter l'exploration de l'espace de Hilbert.

Configuration expérimentale
Les expériences ont été menées en utilisant la bibliothèque Qiskit sur un simulateur haute performance (KUATOMU) dans deux scénarios :

• Sans bruit : 35 instances du SPP (allant de 6 à 20 qubits) ont été testées.
• Avec bruit : Les simulations incluaient des canaux d'erreur de dépolarisation ($\epsilon = 0.01$) sur des qubits spécifiques pour imiter les limitations des dispositifs NISQ.
• Comparaison : Les stratégies QCE ont été évaluées par rapport au VQE standard (utilisant un ansatz d'intrication linéaire à deux corps et l'optimiseur COBYLA).
• Métrique : La performance a été mesurée à l'aide du rapport d'approximation ($R$), défini comme le rapport entre une valeur de référence classique (solveur Gurobi) et la valeur d'attente minimale trouvée par l'algorithme quantique.

Résultats clés

• Supériorité sur le VQE : Dans les scénarios sans bruit, l'AF-QCE et l'APCD-QCE ont tous deux nettement surpassé le VQE. La performance du VQE se dégradait rapidement à mesure que le nombre de qubits augmentait (échouant souvent à converger pour des instances $\ge 10$ qubits), tandis que les approches évolutionnaires maintenaient de meilleures performances.
• Performance de l'APCD-QCE : La stratégie APCD-QCE a démontré les résultats les plus robustes, atteignant un rapport d'approximation de 1,00 (optimal) dans 25 des 35 instances. Elle a efficacement évité la stagnation de la convergence dans la plupart des cas où le VQE et l'AF-QCE luttaient.
• Limites de l'évolutivité : Malgré les améliorations, des défis d'évolutivité ont persisté. Pour les instances de 20 qubits (spécifiquement 20.1, 20.6 et 20.7), toutes les méthodes, y compris l'APCD-QCE, ont montré des signes de stagnation de la convergence, avec une baisse significative des rapports d'approximation.
• Impact du bruit : Dans les simulations bruitées, la performance s'est dégradée pour tous les algorithmes, en particulier pour les petites instances. Cependant, les cadres QCE ont généralement maintenu une performance comparable ou supérieure par rapport au VQE.

Signification et affirmations
L'article affirme que le cadre QCE proposé offre une alternative prometteuse aux algorithmes variationnels à ansatz fixe pour les problèmes d'optimisation entière. Les contributions clés incluent :

• Atténuation de la stagnation : Le cadre, en particulier la variante APCD-QCE, démontre une capacité remarquable à éviter la stagnation de la convergence associée aux plateaux stériles dans les VQA standards.
• Élimination des optimiseurs classiques : En faisant évoluer directement la topologie du circuit, la procédure contourne le besoin d'optimiseurs classiques (comme COBYLA) pour ajuster les paramètres, résolvant ainsi un goulot d'étranglement dans les flux de travail VQA actuels.
• Voie vers l'évolutivité : Bien que ce ne soit pas une solution complète à la stagnation des 20 qubits, les résultats suggèrent que les circuits à topologie variable offrent une « voie intéressante » pour résoudre des problèmes d'optimisation à plus grande échelle. Les auteurs notent que la stratégie APCD-QCE est « presque immunisée » contre les effets de stagnation de la convergence étant donné un nombre suffisamment élevé de générations, bien que l'échappement des minima locaux dans le paysage de mutation reste un défi.

Les auteurs concluent que, bien que la méthode fasse face à des obstacles d'évolutivité avec l'augmentation du nombre de qubits, l'intégration de termes inspirés de la physique (pseudo-contre-adiabatiques) dans la recherche de circuits évolutionnaires produit des résultats encourageants pour la résolution de problèmes combinatoires sur des dispositifs NISQ.