Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling

Cet article propose une méthode d'extrapolation pour optimiser les deux paramètres de l'algorithme QAOA à rampe linéaire, démontrant que cette approche atteint une mise à l'échelle du temps d'exécution supérieure par rapport aux algorithmes classiques pour les problèmes d'optimisation de portefeuille jusqu'à 28 qubits.

L'essentiel

Imaginez que vous essayez de résoudre un puzzle massif et incroyablement complexe. Vous avez un nouvel outil de haute technologie (un ordinateur quantique) qui pourrait être capable de résoudre ce puzzle plus rapidement que le meilleur cerveau humain ou le supercalculateur dont nous disposons aujourd'hui. Mais il y a un piège : pour faire fonctionner cet outil, vous devez régler ses boutons parfaitement. Si vous réglez mal les boutons, l'outil est inutile.

Ce document traite d'un raccourci astucieux pour régler ces boutons sans avoir à faire le travail difficile de tester chaque réglage à partir de zéro.

Voici le déroulement de leur parcours, expliqué simplement :

1. Le Problème : Régler la « Radio Quantique »

L'outil qu'ils utilisent s'appelle l'QAOA (Algorithme d'Optimisation Approximative Quantique). Considérez l'QAOA comme une radio qui essaie de trouver un signal spécifique et clair (la meilleure solution à un problème) au milieu de beaucoup de parasites.

• La méthode standard : Habituellement, pour obtenir un signal clair, vous devez tourner des dizaines de boutons (paramètres) et les tester encore et encore. À mesure que le puzzle devient plus grand, le nombre de boutons explose, et le processus de réglage prend une éternité. C'est comme essayer de régler une radio avec 100 boutons à la main ; vous ne finiriez jamais.
• La nouvelle idée (Linear-Ramp) : Les chercheurs ont trouvé un moyen de simplifier cela. Au lieu de 100 boutons, ils ont réalisé qu'ils n'ont réellement besoin que de deux réglages principaux (appelons-les « Vitesse » et « Direction ») et d'un réglage de « Profondeur » (combien de temps on écoute). C'est ce qu'on appelle la méthode Linear-Ramp. C'est comme si vous aviez une radio avec seulement un bouton de volume et un cadran de réglage, ce qui la rend beaucoup plus facile à utiliser.

2. La Solution : L'astuce du « Petit Puzzle » (Extrapolation)

Même avec seulement deux boutons, trouver le réglage parfait pour un énorme puzzle (disons de 28 pièces) reste difficile. On ne peut pas simplement deviner.

Les auteurs ont conçu un truc astucieux : l'Extrapolation.

• L'analogie : Imaginez que vous voulez savoir à quelle vitesse une voiture de course ira sur une piste de 100 miles. Au lieu de conduire la voiture sur les 100 miles complets (ce qui prend beaucoup de temps et consomme beaucoup de carburant), vous conduisez la voiture sur des sections de 4, 6 et 8 miles. Vous mesurez la vitesse sur ces sections.
• La prédiction : Vous tracez ensuite une ligne reliant ces vitesses et vous l'étendez pour prédire la vitesse à laquelle la voiture ira sur la piste complète de 100 miles.
• Dans l'article : Ils ont pris leurs problèmes complexes et volumineux (jusqu'à 28 « bits » ou pièces de puzzle) et les ont décomposés en versions minuscules et faciles (4, 6, 8 ou 10 pièces). Ils ont trouvé les réglages de boutons parfaits pour ces versions minuscules. Ensuite, ils ont utilisé les mathématiques pour « étirer » ces réglages afin de prédire les réglages parfaits pour les grands problèmes de 28 pièces.

3. Le Test : L'ordinateur quantique peut-il gagner ?

Ils ont testé cette méthode sur quatre types différents de puzzles du monde réel :

1. Optimisation de Portefeuille : Choisir le meilleur mélange d'actions pour maximiser les profits et minimiser les risques.
2. Sélection de Caractéristiques : Choisir les points de données les plus importants pour un modèle d'apprentissage automatique (machine learning).
3. Clustering (Regroupement) : Grouper des articles similaires ensemble (comme trier des billes rouges et bleues).
4. MaxCut : Diviser un réseau en deux groupes de manière à ce que les connexions entre les groupes soient les plus fortes possibles.

Ils ont exécuté ces puzzles sur un ordinateur quantique simulé (une version parfaite et sans bruit tournant sur un supercalculateur) et ont comparé le temps nécessaire pour trouver la réponse par rapport aux meilleures méthodes informatiques classiques (normales).

4. Les Résultats : Une victoire pour les actions, mais pas pour tout

Voici ce qu'ils ont découvert :

• Le puzzle du marché boursier (Optimisation de Portefeuille) : C'est là que la magie a opéré. La méthode quantique, utilisant leur truc de prédiction de « petit puzzle », est devenue plus rapide à mesure que le problème devenait plus grand par rapport à la méthode classique. Elle a montré un avantage potentiel. C'est comme si la voiture quantique commençait à dépasser le conducteur humain à mesure que la piste s'allongeait.
• Les autres puzzles : Pour les trois autres types de problèmes (choisir des données, regrouper des éléments, diviser des réseaux), la méthode quantique était en fait plus lente ou tout aussi lente que les méthodes classiques. Le « truc de prédiction » fonctionnait, mais l'outil quantique n'a pas battu les outils humains dans ces cas spécifiques.

5. Le raccourci « Universel »

Les chercheurs ont remarqué que les réglages de boutons « parfaits » pour le puzzle du marché boursier suivaient un schéma simple. Ils ont réalisé qu'ils n'avaient même pas besoin de calculer les réglages pour chaque nouveau puzzle. Ils pouvaient simplement utiliser une formule universelle (une règle unique qui fonctionne pour tout le monde).

• Lorsqu'ils ont appliqué cette règle universelle, les performances quantiques pour les trois autres puzzles se sont considérablement améliorées, devenant aussi bonnes que les méthodes classiques, bien que non meilleures.

L'essentiel à retenir

L'article affirme que :

1. Vous pouvez éviter le processus coûteux et lent de réglage d'un ordinateur quantique pour de grands problèmes en testant d'abord de petits problèmes et en devinant mathématiquement le reste.
2. Cette méthode fonctionne suffisamment bien pour montrer que, pour l'Optimisation de Portefeuille, un ordinateur quantique pourrait éventuellement résoudre ces problèmes plus rapidement qu'un ordinateur classique à mesure que les problèmes deviennent énormes.
3. Pour les autres problèmes testés, l'ordinateur quantique n'a pas encore gagné, mais la méthode l'a rendu compétitif.

Note importante : Les auteurs précisent avec prudence qu'il s'agit d'une simulation sur un ordinateur parfait. Ils n'ont pas prouvé que cela fonctionne sur du matériel quantique réel et bruyant, et ils n'ont pas résolu de problèmes de plus de 28 pièces. Mais le truc de prédiction « du petit au grand » semble être un moyen prometteur de rendre les ordinateurs quantiques utiles pour l'avenir.

Résumé technique

Résumé Technique : Méthode d'extrapolation pour optimiser les paramètres du LR-QAOA

Énoncé du problème
L'algorithme d'optimisation quantique approximative (QAOA) est un candidat de premier plan pour la résolution de problèmes d'optimisation combinatoire, pourtant sa forme variationnelle standard fait face à des défis de scalabilité significatifs. L'approche standard nécessite l'optimisation d'un grand nombre de paramètres de circuit ($2p$ paramètres pour une profondeur $p$) via des routines classiques, ce qui est coûteux en termes de calcul et sujet au piégeage dans des minima locaux. Ce goulot d'étranglement de l'optimisation entrave la démonstration d'un potentiel avantage de temps d'exécution quantique. Bien que des schémas fixes, tels que le LR-QAOA (Linear-Ramp QAOA), réduisent l'espace des paramètres à seulement deux paramètres libres ($\Delta\gamma, \Delta\beta$) plus la profondeur $p$, la recherche des valeurs optimales pour ces paramètres pour de grandes tailles de problèmes ($N$) reste une tâche non triviale.

Méthodologie
Les auteurs proposent une méthode pour déterminer des paramètres LR-QAOA appropriés pour de grandes tailles de problèmes par extrapolation à partir d'optimisations effectuées sur des sous-problèmes plus petits. La méthodologie se compose de trois composantes principales :

1. Formulation du problème : Quatre problèmes d'optimisation combinatoire sont formulés sous forme de problèmes d'optimisation binaire quadratique non contrainte (QUBO) : Optimisation de Portefeuille, Sélection de Caractéristiques, Clustering (utilisant les jeux de données Moons et Blobs), et MaxCut pondéré.
2. Référencement classique : La mise à l'échelle du temps d'exécution des solveurs classiques (CPLEX, Gurobi, Goemans-Williamson, et MQLib/Burer2002) est évaluée. Le heuristique MQLib/Burer2002 est sélectionné comme principal référent classique en raison de son temps d'exécution absolu faible et de son comportement de mise à l'échelle cohérent, évitant la surcharge des bornes d'optimalité trouvées dans les solveurs commerciaux.
3. LR-QAOA et schéma d'extrapolation :
   • Ansatz de rampe linéaire : Au lieu d'une optimisation variationnelle, les paramètres sont échantillonnés à partir d'un ansatz linéaire : $\gamma_j = \Delta\gamma x_j$ et $\beta_j = \Delta\beta(1-x_j)$, où $x_j$ est une variable de rampe linéaire.
   • Optimisation de sous-problèmes : Pour une taille de problème cible $N$ (jusqu'à 28 qubits), des sous-instances aléatoires de tailles plus petites ($\tilde{N} \in \{4, 6, 8, 10\}$) sont générées. Une recherche par grille est effectuée sur ces petites instances pour trouver les $\Delta\gamma$ et $\Delta\beta$ optimaux.
   • Ajustement et extrapolation : Les paramètres optimaux trouvés pour $\tilde{N}$ sont ajustés à l'aide d'une fonction de Gauss asymétrique multivariée pour localiser le centre de la région de haute probabilité. Ces centres sont ensuite extrapolés vers la taille cible $N$ en supposant une relation linéaire sur une échelle log-log ($\log(\text{paramètre})$ vs $\log(N)$).
   • Optimisation de la profondeur : La profondeur $p$ du QAOA est optimisée pour minimiser le temps d'exécution quantique total, défini comme le produit de la profondeur du circuit et du nombre médian de tirages nécessaires pour trouver la solution optimale ($D = d \cdot N_{shots}$).
   • Mise à l'échelle universelle : Pour améliorer la stabilité et réduire les valeurs aberrantes, les auteurs dérivent des lois de mise à l'échelle de paramètres « universelles » ($f(N) = a \cdot N^b$) basées sur les données extrapolées, appliquant ces lois fixes à toutes les instances d'une classe de problèmes donnée plutôt que d'optimiser par instance.

Résultats clés
L'étude évalue la mise à l'échelle du temps d'exécution quantique (exprimée en profondeur totale $D$) par rapport à la mise à l'échelle classique sur un émulateur quantique sans bruit pour des tailles de problèmes allant jusqu'à $N=28$.

• Optimisation de Portefeuille : Le LR-QAOA avec des paramètres extrapolés démontre un exposant de mise à l'échelle de $\alpha \approx 0,219$ (où $D \propto 2^{\alpha N}$), ce qui est nettement inférieur au référent classique (MQLib/Burer2002) de $\alpha_{cl} \approx 0,323$. Cela indique un potentiel avantage de mise à l'échelle quantique.
• Sélection de Caractéristiques, Clustering et MaxCut : Initialement, ces problèmes présentaient des exposants de mise à l'échelle quantique supérieurs à leurs homologues classiques. Cependant, en appliquant la mise à l'échelle de paramètres « universelle » dérivée des données d'extrapolation, la mise à l' échelle quantique s'est considérablement améliorée.
  • Pour la Sélection de Caractéristiques et le MaxCut, la mise à l'échelle quantique a atteint l'égalité avec les référents classiques ($\alpha \approx 0,202$ vs $0,197$ et $\alpha \approx 0,163$ vs $0,156$, respectivement).
  • Pour le Clustering (Moons), le référent classique ($\alpha_{cl} \approx 0,051$) est resté supérieur à l'approche quantique ($\alpha \approx 0,163$).
• Stabilité : L'utilisation de paramètres universels a considérablement réduit l'occurrence de valeurs aberrantes extrêmes (instances avec des profondeurs très grandes) observées lorsque les paramètres étaient déterminés individuellement pour chaque instance.
• Comportement de probabilité : Pour l'Optimisation de Portefeuille et le MaxCut, la probabilité de mesurer la solution optimale ($P_{opt}$) est restée constante ou a légèrement augmenté avec $N$, tandis que la profondeur du circuit suivait une mise à l'échelle algébrique. Cela suggère un potentiel pour une mise à l'échelle polynomiale du temps d'exécution médian pour ces classes de problèmes spécifiques.

Signification et Revendications
L'article affirme présenter une méthode scalable pour déterminer les paramètres du LR-QAOA sans nécessiter d'optimisation variationnelle coûteuse sur de grands circuits. En exploitant l'extrapolation à partir de petits sous-problèmes, les auteurs démontrent que :

1. Avantage de temps d'exécution : Un avantage de mise à l'échelle quantique est observé pour l'Optimisation de Portefeuille par rapport aux heuristiques classiques.
2. Scalabilité : La méthode d'extrapolation permet l'estimation efficace des paramètres pour des systèmes plus grands ($N=28$) basés sur des simulations de systèmes très petits ($N \le 10$).
3. Lois Universelles : L'identification de lois de mise à l'échelle algébrique pour les paramètres ($\Delta\gamma, \Delta\beta, p$) suggère que ces paramètres peuvent être déterminés indépendamment des instances spécifiques de problèmes, améliorant ainsi la robustesse de l'algorithme.

Les auteurs concluent modestement que, bien que leurs résultats suggèrent un potentiel pour des solutions en temps polynomial pour des instances spécifiques (indiqué par une $P_{opt}$ constante et une mise à l'échelle de profondeur algébrique), des travaux supplémentaires sont nécessaires pour vérifier ces conclusions sur des tailles de problèmes plus grandes ($N > 28$) et sur du matériel quantique tolérant aux fautes. Ils soulignent que leur travail traite du potentiel général du LR-QAOA en supposant que les paramètres puissent être trouvés efficacement, plutôt que de résoudre le coût de l'optimisation des paramètres en tant que composante du temps d'exécution.