EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization

1. Problématique

Dans l'ère des ordinateurs quantiques à échelle intermédiaire bruyants (NISQ), l'algorithme d'optimisation quantique approximative (QAOA) fait face à un goulot d'étranglement majeur : le nombre limité de qubits disponibles.

• Limitation actuelle : Les implémentations classiques du QAOA nécessitent un nombre de qubits qui croît linéairement avec la taille du problème ($n$ variables $\rightarrow$ $n$ qubits). Pour les problèmes d'optimisation combinatoire à grande échelle, cela dépasse rapidement les capacités des dispositifs actuels (souvent limités à 10-20 qubits fiables) et des simulations classiques (limitées à ~30 qubits en raison de la croissance exponentielle de l'espace de Hilbert).
• Défaillance des solutions existantes : Les méthodes actuelles de réduction de qubits (encodage compact, partitionnement de problèmes, compression de circuits) entraînent souvent une perte d'information, une dégradation de la précision de l'optimisation, ou nécessitent des opérations supplémentaires introduisant du bruit. Elles ne garantissent pas une équivalence mathématique stricte avec le système original.

2. Méthodologie : Le cadre EQE-QAOA

Les auteurs proposent le QAOA Économe en Qubits à Préservation d'Équivalence (EQE-QAOA). Cette approche exploite les structures physiques intrinsèques de la dynamique quantique pour réduire le nombre de qubits sans aucune perte de performance.

Le processus se déroule en trois étapes principales :

A. Identification du Sous-espace Invariant

• Analyse de la dynamique : Les auteurs analysent l'algèbre de Lie dynamique ($\mathfrak{g}$) générée par les Hamiltoniens de coût ($H_C$) et de mélange ($H_M$) du QAOA.
• Symétries et Quantités Conservées : En calculant le commutant de cette algèbre ($\mathfrak{g}'$), ils identifient des opérateurs $Q$ qui commutent avec $H_C$ et $H_M$. Ces opérateurs représentent des quantités conservées (symétries du système).
• Décomposition : La présence de ces quantités conservées implique que la dynamique quantique est strictement confinée à un sous-espace invariant ($\mathcal{H}_{eff}$) de l'espace de Hilbert complet ($\mathcal{H}$). L'évolution ne peut pas quitter ce sous-espace une fois l'état initial placé à l'intérieur.

B. Preuve d'Équivalence

• Les auteurs démontrent théoriquement que l'évolution dans le sous-espace invariant est exactement équivalente à celle du système complet.
• Cela signifie que les états quantiques, les valeurs d'attente des observables et les statistiques de mesure sont identiques, garantissant que la solution optimale trouvée dans le sous-espace réduit est la même que celle du problème original.

C. Mapping Isométrique et Réduction de Qubits

• Pour réduire le nombre de qubits, ils construisent une application isométrique ($V$) qui encode le sous-espace invariant $\mathcal{H}_{eff}$ (de dimension $M$) dans un espace de Hilbert réduit $\tilde{\mathcal{H}}_{eff}$ utilisant un nombre minimal de qubits $m$.
• Le nombre de qubits requis est déterminé par $m = \lceil \log_2 M \rceil$.
• Les Hamiltoniens originaux sont transformés en Hamiltoniens induits ($\tilde{H}_C, \tilde{H}_M$) agissant sur cet espace réduit, permettant d'exécuter le circuit QAOA complet avec $m$ qubits au lieu de $n$.

3. Contributions Clés

1. Décomposition en sous-espaces invariants : Utilisation de l'algèbre de Lie dynamique pour prouver que la plupart des problèmes d'optimisation contraints ou symétriques évoluent dans un sous-espace de dimension bien inférieure à $2^n$.
2. Théorème d'équivalence : Preuve rigoureuse que la réduction de l'espace de recherche n'altère ni la trajectoire quantique, ni les statistiques de mesure, ni la qualité de la solution.
3. Cartographie Isométrique : Construction d'un schéma d'encodage qui réduit le nombre de qubits tout en préservant l'information (réduction sans perte).
4. Conditions d'applicabilité : Identification des conditions structurelles (présence de contraintes ou de symétries) sous lesquelles la réduction est possible. L'approche est inapplicable uniquement aux problèmes non contraints avec des variables totalement indépendantes.

4. Résultats Numériques

Les simulations basées sur des instances du problème Max-Cut valident l'approche :

• Réduction des qubits :
  • Pour des graphes complets ($K_n$) possédant une symétrie de permutation élevée, le nombre de qubits est réduit de $n$ à environ $\log_2(n+1)$. Par exemple, pour $n=12$, le nombre de qubits passe de 12 à 4 (réduction de ~70%).
  • Pour des graphes cycliques, une réduction modérée est observée.
  • Pour des graphes aléatoires (peu symétriques), la réduction est minimale, ce qui est cohérent avec la théorie (l'espace invariant est proche de l'espace complet).
• Préservation de la performance : Les métriques d'équivalence (fidélité de l'état, différence de valeur d'attente de l'énergie, distance de variation totale des probabilités) restent au niveau de la précision machine ($10^{-14}$ à $10^{-15}$), confirmant l'absence de dégradation.
• Efficacité mémoire : La mémoire nécessaire pour la simulation classique croît exponentiellement pour le QAOA original ($2^n$), mais beaucoup plus lentement pour EQE-QAOA ($2^m$), permettant de traiter des problèmes plus grands.
• Comparaison avec l'état de l'art : Contrairement aux méthodes d'encodage compact ou de partitionnement qui sacrifient la précision, EQE-QAOA maintient le taux d'approximation le plus élevé et l'écart d'erreur le plus faible par rapport à la solution optimale.

5. Signification et Impact

• Déverrouillage de l'échelle : EQE-QAOA permet d'aborder des problèmes d'optimisation combinatoire à grande échelle sur les dispositifs quantiques actuels (NISQ) et les simulateurs classiques, en contournant la limitation fondamentale du nombre de qubits.
• Optimisation sans perte : C'est l'une des rares méthodes à garantir une équivalence mathématique stricte avec l'algorithme original, éliminant le compromis habituel entre économie de ressources et précision.
• Applicabilité large : La méthode s'applique naturellement à la plupart des problèmes d'ingénierie réels qui comportent des contraintes (budget, capacité) ou des symétries structurelles, rendant l'optimisation quantique plus pratique et évolutive.

En résumé, EQE-QAOA représente une avancée théorique et pratique majeure en transformant la contrainte de ressources quantiques en une opportunité d'exploitation des symétries physiques, permettant une optimisation exacte avec des ressources réduites.