Locally Acting Grover Mixers for Constraint-Preserving QAOA

Cet article propose des mélangeurs de Grover agissant localement qui remplacent les coûteuses portes de déphasage multi-contrôlées globales du GM-QAOA par des opérations locales efficaces sur des sous-systèmes de qubits disjoints, atteignant une convergence comparable à la méthode originale tout en réduisant considérablement la profondeur du circuit et le nombre de portes pour des problèmes tels que la couverture exacte et le problème du voyageur de commerce.

L'essentiel

Imaginez que vous essayez de résoudre un puzzle massif et complexe, comme trouver l'itinéraire parfait pour un vendeur de passage devant visiter chaque ville exactement une fois. Vous avez un ordinateur super intelligent (un ordinateur quantique) qui peut essayer des millions de possibilités à la fois. Cependant, cet ordinateur est actuellement un peu « bruyant » et fragile, comme une sculpture de verre délicate. Si vous lui demandez de faire quelque chose de trop compliqué, il se brise ou fait des erreurs.

Ce document présente une nouvelle façon de guider cet ordinateur fragile afin qu'il puisse résoudre ces puzzles plus efficacement sans se briser.

Le Problème : Le livre de règles « Global »

Les chercheurs travaillent avec une méthode appelée QAOA (Quantum Approximate Optimization Algorithm). Considérez le QAOA comme un randonneur essayant de trouver le point le plus bas dans une vallée embrumée (la meilleure solution). Pour ce faire, le randonneur a besoin de deux outils :

1. Une Carte (Séparation de Phase) : Montre au randonneur où se trouvent les « mauvais » endroits.
2. Une Boussole (Le Mélangeur) : Aide le randonneur à se déplacer pour explorer de nouveaux endroits.

Dans la version standard de cette méthode (appelée GM-QAOA), la « Boussole » est une Porte Multi-Contrôlée Globale.

• L'Analogie : Imaginez essayer d'organiser une fête de danse pour 100 personnes. La Boussole standard est comme une règle géante qui dit : « Si tout le monde dans la pièce est dans une formation spécifique, alors tout le monde doit bouger ensemble. »
• Le Problème : Pour appliquer cette règle sur un ordinateur quantique fragile, vous avez besoin d'une machine massive et complexe pour vérifier les 100 personnes à la fois. Cette machine est énorme, prend beaucoup de place et est très susceptible de se briser (faire des erreurs) sur les ordinateurs bruyants d'aujourd'hui.

La Solution : La Surveillance de Quartier « Locale »

Les auteurs, Minjin Choi, Dongkeun Lee et Junghee Ryu, proposent une façon plus intelligente de construire cette Boussole. Ils l'appellent les Mélangeurs de Grover à Action Locale (Locally Acting Grover Mixers).

• L'Analogie : Au lieu d'une seule règle géante pour toute la pièce, ils divisent les 100 personnes en petits groupes indépendants (comme 10 tables de 10 personnes). Ainsi, au lieu d'une seule machine géante vérifiant tout le monde, vous avez 10 petites machines simples. Chaque machine ne vérifie que sa propre table.
  • La machine de la Table 1 dit : « Si tout le monde à la Table 1 est en formation, bougez. »
  • La machine de la Table 2 dit : « Si tout le monde à la Table 2 est en formation, bougez. »
• Le Résultat : Ces petites machines sont beaucoup plus faciles à construire, prennent moins de place et sont beaucoup moins susceptibles de se briser. Crucialement, parce que les groupes sont indépendants, le résultat global est tout aussi bon que celui de la machine géante.

Comment ils ont procédé

Les chercheurs ont réalisé que pour beaucoup de puzzles, vous n'avez pas besoin de forcer chaque règle dans la configuration de départ.

1. Encodage Partiel : Au lieu de forcer l'ordinateur à commencer avec une solution parfaite qui respecte toutes les règles, ils le laissent commencer avec une solution qui n'en respecte que certaines. Cela crée une « structure produit » (les groupes indépendants mentionnés ci-dessus).
2. Mélange Local : Ils utilisent ensuite leur nouvelle « Boussole Locale » pour mélanger les choses au sein de ces petits groupes.

La Preuve : Couverture Exacte et Vendeur de Passage

Ils ont testé cette idée sur deux puzzles célèbres :

1. Le Problème de la Couverture Exacte (Exact Cover) : Un puzzle logique sur la couverture d'éléments exactement une fois.
2. Le Problème du Vendeur de Passage (Traveling Salesman Problem - TSP) : Trouver l'itinéraire le plus court visitant plusieurs villes.

Les Résultats :

• Même Qualité : La nouvelle méthode « Locale » a trouvé des solutions tout aussi bonnes que l'ancienne méthode « Globale ».
• Beaucoup Plus Simple : La nouvelle méthode a utilisé 87 % de portes d'« intrication » en moins (les parties du circuit qui sont les plus susceptibles de se briser).
• Le Compromis : La nouvelle méthode nécessite que l'ordinateur exécute le circuit un peu plus de fois pour ajuster ses paramètres (car il y a plus de boutons à tourner). Cependant, puisque le circuit lui-même est beaucoup plus simple et moins sujet aux erreurs, ce compromis est une victoire majeure pour les ordinateurs bruyants d'aujourd'hui.

L'Idée Principale

L'article soutient que pour les ordinateurs quantiques que nous possédons en ce moment même (qui sont petits et bruyants), il est préférable d'utiliser une stratégie « Locale ».

• Ancienne Voie : Construire une machine massive et complexe qui essaie de tout faire parfaitement mais qui se brise facilement.
• Nouvelle Voie : Construire de nombreuses petites machines simples qui travaillent ensemble. Elles peuvent nécessiter quelques essais supplémentaires pour régler les paramètres, mais elles sont beaucoup plus fiables et adaptées au matériel actuel.

En bref, les auteurs ont trouvé un moyen de rendre les algorithmes quantiques pour les problèmes contraints plus légers, plus simples et plus robustes, sans sacrifier la qualité des réponses qu'ils trouvent.

Résumé technique

Résumé Technique : Mélangeurs de Grover à action locale pour le QAOA respectant les contraintes

Énoncé du problème
L'algorithme d'optimisation quantique approximative (QAOA) et sa généralisation, l'algorithme d'opérateur alterné quantique (QAOA), sont des algorithmes variationnels de premier plan pour l'optimisation combinatoire. Un défi critique lors de l'application de ces algorithmes à des problèmes contraints consiste à garantir que l'évolution quantique reste confinée dans le sous-espace réalisable défini par les contraintes du problème. Le mélangeur Grover QAOA (GM-QAOA) répond à cela en employant un opérateur de mélange généré par le projecteur sur l'état initial, ce qui garantit mathématiquement la préservation du sous-espace réalisable.

Cependant, le mélangeur GM-QAOA standard nécessite une porte de déphasage multi-contrôlée globale agissant sur tous les $n$ qubits. Sur les dispositifs quantiques à échelle intermédiaire bruyants (NISQ) actuels, qui ne supportent nativement que des opérations à un et deux qubits, la décomposition d'une telle porte globale en portes élémentaires entraîne un surcoût substantiel en termes de circuit. La profondeur et le nombre de portes de ces décompositions augmentent rapidement avec le nombre de qubits, posant une barrière significative à une mise en œuvre pratique et augmentant la susceptibilité au bruit matériel.

Méthodologie
Les auteurs proposent une variante « à action locale » du mélangeur de Grover, adaptée aux états initiaux qui admettent une structure de produit sur des sous-systèmes de qubits disjoints. Cette approche tire parti de l'observation selon laquelle, dans de nombreux problèmes combinatoires, les contraintes peuvent être partiellement encodées dans la préparation de l'état initial, laissant les contraintes restantes à être gérées via des termes de pénalité dans l'Hamiltonien de coût.

1. États initiaux à structure de produit : La méthode suppose que l'état initial $|\psi_0\rangle$ peut être factorisé sous la forme $|\psi_0\rangle = |\psi^{(1)}_0\rangle \otimes |\psi^{(2)}_0\rangle \otimes \dots \otimes |\psi^{(\ell)}_0\rangle$, où chaque $|\psi^{(j)}_0\rangle$ réside sur un sous-ensemble disjoint de qubits. Cette structure est obtenue en encodant seulement un sous-ensemble des contraintes du problème lors de la préparation de l'état.
2. Unitaire de mélange local : Au lieu d'un seul mélangeur global $e^{-i\beta |\psi_0\rangle\langle\psi_0|}$, la méthode proposée construit l'unitaire de mélange comme un produit tensoriel d'unitaires locaux :
   $$U_M(\beta^{(1)}, \dots, \beta^{(\ell)}) = \bigotimes_{j=1}^{\ell} e^{-i\beta^{(j)} |\psi^{(j)}_0\rangle\langle\psi^{(j)}_0|}$$
   Chaque unitaire local agit indépendamment sur son sous-système respectif en utilisant une porte de déphasage multi-contrôlée confinée à ce sous-système.
3. Paramétrage : L'ansatz introduit des paramètres variationnels indépendants $\beta^{(j)}$ pour chaque sous-système. Pour un circuit de $p$ couches avec $\ell$ sous-systèmes, le nombre total de paramètres de mélange est $p\ell$, contre $p$ dans le GM-QAOA original. Bien que cela augmente la dimension de l'espace de paysage d'optimisation classique, cela remplace une seule porte globale massive par $\ell$ portes locales plus petites.

Contributions clés

• Efficacité du circuit : La principale contribution est le remplacement de la porte de déphasage multi-contrôlée globale par $\ell$ opérations locales. Cela réduit considérablement le nombre de portes d'intrication (spécifiquement les CNOT) et la profondeur du circuit requis pour l'étape de mélange.
• Stratégie d'encodage des contraintes : Le document examine le compromis entre l'encodage de toutes les contraintes dans l'état initial et l'encodage d'un sous-ensemble de celles-ci. Il démontre que l'encodage partiel des contraintes, qui permet la structure de produit requise pour le mélangeur local, peut produire des circuits globaux plus compacts, même si cela réduit la taille de l'espace de recherche.
• Préservation de la faisabilité : La méthode conserve l'avantage central du GM-QAOA : l'opérateur de mélange préserve l'espace de recherche défini par l'état initial, garantissant que l'algorithme ne dérive pas vers des régions infaisables.

Résultats
Les auteurs ont évalué la méthode proposée sur le problème de Couverture Exacte (Exact-Cover) et le problème du Voyageur de Commerce (TSP) à l'aide de simulations numériques.

• Problème de Couverture Exacte : Pour une instance à sept qubits, la méthode proposée a atteint un comportement de convergence comparable au GM-QAOA original. De manière cruciale, la décomposition de l'unitaire de mélange dans l'ensemble de portes $\{RX, RY, RZ, CNOT\}$ a réduit le nombre de CNOT de 218 (original) à 28 (proposé), soit une réduction d'environ 87 %.
• Problème du Voyageur de Commerce (TSP) : Les simulations sur des instances TSP à quatre villes (neuf qubits) ont montré que la méthode proposée maintient des probabilités de solution comparables au GM-QAOA à travers différentes profondeurs de couches $p$.
  • Résilience au bruit : Sous un modèle de bruit de dépolarisation, la méthode proposée a présenté une erreur relative nettement plus faible de la valeur attendue de l'Hamiltonien de coût par rapport au GM-QAOA original, grâce à la réduction de la profondeur du circuit et du nombre de portes.
  • Compromis de ressources : Bien que la méthode proposée nécessite plus d'exécutions de circuits lors de l'optimisation classique en raison du nombre accru de paramètres variationnels, la réduction de la complexité du circuit quantique (le nombre de CNOT passant de 572 à 54 par opérateur de mélange) la rend plus viable pour le matériel bruyant.
  • Encodage partiel vs complet : Pour le TSP, l'encodage uniquement de la contrainte de l'étape temporelle ($P_1$) dans l'état initial (encodage partiel) combiné au mélangeur local a entraîné une profondeur de circuit de 450 à performance optimale ($p=7$). En revanche, l'encodage des contraintes de l'étape temporelle et de la visite des villes ($P_1$ et $P_2$) dans l'état initial (encodage complet) a nécessité un mélangeur global et a abouti à une profondeur de circuit de 4142 à $p=1$, malgré l'obtention d'une probabilité de solution élevée plus rapidement. Les auteurs concluent que l'encodage partiel offre une complexité de circuit globale plus favorable.

Signification et affirmations
L'article affirme que les mélangeurs de Grover à action locale offrent une voie pratique pour l'implémentation du QAOA respectant les contraintes sur les dispositifs quantiques de l'ère NISQ. En exploitant la structure de produit des sous-espaces réalisables, la méthode réduit considérablement le coût de mise en œuvre (nombre de portes et profondeur) tout en préservant la capacité de l'algorithme à converger vers des solutions de haute qualité.

Les auteurs notent avec modestie que, bien que l'augmentation du nombre de paramètres introduise un surcoût d'optimisation classique plus important et potentiellement un paysage d'optimisation plus complexe, la réduction de la complexité du circuit quantique est le facteur dominant pour les dispositifs NISQ, où la fidélité des portes est la principale limitation. Le travail suggère que le compromis entre le nombre de paramètres et la profondeur du circuit favorise l'approche proposée pour le matériel actuel. L'article ne prétend pas résoudre la question théorique de savoir pourquoi la structure de mélange relaxée atteint une convergence comparable, identifiant cela comme une direction ouverte pour des recherches futures.