Methods for non-variational heuristic quantum optimisation

Cet article introduit et valide une nouvelle classe d'heuristiques d'optimisation quantique non variationnelles et résilientes au bruit — le Recuit Simulé amélioré par le Quantique (QeSA) et le Tempering Parallèle amélioré par le Quantique (QePT) — qui utilisent des techniques de Monte Carlo par chaînes de Markov pour atteindre une mise à l'échelle supérieure par rapport aux références classiques sur des instances difficiles de Sherrington-Kirkpatrick.

L'essentiel

Imaginez que vous essayez de trouver le point le plus bas d'une vaste chaîne de montagnes embrumée, remplie de vallées profondes et de fosses cachées. C'est ce que les informaticiens appellent un problème d'optimisation : trouver la meilleure solution absolue parmi des milliards de possibilités.

Pendant des décennies, la principale stratégie pour résoudre ces problèmes sur les ordinateurs quantiques a été les méthodes « variationnelles ». Considérez cela comme un étudiant qui essaie d'apprendre une chanson en demandant constamment l'avis d'un professeur, en ajustant sa hauteur de voix, puis en essayant à nouveau. Cela fonctionne, mais c'est lent et cela nécessite beaucoup d'allers-retours.

Ce document présente une approche différente. Au lieu de demander constamment un retour d'expérience, les auteurs proposent une méthode qui utilise les ordinateurs quantiques comme un « Super-Proposeur ». Ils appellent cela une approche « non variationnelle » car elle ne repose pas sur cette boucle lente professeur-élève. À la place, elle utilise un système hybride où un ordinateur classique mène la course principale, mais demande occasionnellement à l'ordinateur quantique de faire un « saut magique » vers un nouvel emplacement.

Voici une décomposition de leurs idées en utilisant des analogies simples :

1. Le Problème : Rester coincé dans des fosses locales

Imaginez que vous êtes un randonneur (l'algorithme) essayant de trouver la vallée la plus profonde (la meilleure solution).

• Recuit simulé classique (SA - Simulated Annealing) : Vous partez du haut d'une montagne et descendez lentement la pente. Si vous tombez dans une petite dépression (un minimum local), vous pourriez y rester coincé parce que vous n'avez pas l'énergie nécessaire pour en sortir et trouver le véritable fond.
• Température parallèle (PT - Parallel Tempering) : Pour corriger cela, vous envoyez toute une équipe de randonneurs. Certains marchent lors de journées chaudes et ensoleillées (température élevée) où ils peuvent facilement sauter par-dessus de petites collines. D'autres marchent lors de journées froides et glaciales (température basse) où ils sont très prudents. De temps en temps, les randonneurs échangent leurs places. Le randonneur « chaud », qui vient de sauter par-dessus une colline, échange sa place avec le randonneur « froid » qui est coincé, aidant ainsi toute l'équipe à échapper aux pièges.

2. L'Innovation : Le « Saut Magique » Quantique

Les auteurs ont réalisé que même si les randonneurs « chauds » sont bons pour sauter, ils sont toujours limités par la distance physique qu'ils peuvent franchir. Ils ont proposé de remplacer le « saut local » standard (basculer un interrupteur) par une Proposition Quantique.

Considérez l'ordinateur quantique comme un téléporteur. Au lieu de faire des petits pas prudents, l'ordinateur quantique regarde la carte et suggère une « téléportation » vers une partie complètement différente de la chaîne de montagne qui est susceptible d'être un bon endroit.

• Comment cela fonctionne : L'ordinateur classique dit : « D'accord, je suis à cet endroit. » L'ordinateur quantique effectue un calcul rapide (une « évolution en temps réel ») et dit : « Je pense que tu devrais te téléporter vers cet endroit spécifique là-bas. » L'ordinateur classique vérifie ensuite s'il s'agit d'un bon endroit et décide s'il accepte le saut ou non.

3. Les Deux Nouvelles Méthodes

Le document présente deux façons spécifiques d'utiliser ce téléporteur quantique :

• QeSA (Simulated Annealing augmenté par le Quantique) : C'est comme un randonneur solitaire, mais qui possède désormais un téléporteur. À mesure qu'il se refroidit (devient plus prudent), le téléporteur l'aide à échapper aux fosses profondes dans lesquelles un randonneur normal resterait coincé.
• QePT (Parallel Tempering augmenté par le Quantique) : C'est l'équipe de randonneurs. Les auteurs ont trouvé quelque chose de très intéressant : vous n'avez pas besoin de donner un téléporteur à chaque randonneur.
  • Si vous donnez le téléporteur uniquement aux randonneurs qui sont au fond (les plus froids, les plus prudents), toute l'équipe performe bien mieux.
  • C'est une avancée majeure car les ordinateurs quantiques sont coûteux et rares. Vous pouvez laisser les randonneurs « chauds » sur des ordinateurs classiques réguliers et n'utiliser le téléporteur quantique coûteux que pour les quelques randonneurs qui sont les plus susceptibles de rester coincés.

4. Ce qu'ils ont trouvé (Les Résultats)

Les auteurs ont fait tourner des simulations (modèles informatiques) pour tester ces idées sur des problèmes très difficiles, de type « vitreux » (montagnes avec des milliers de fosses confuses).

• La découverte : Les méthodes augmentées par le quantique ont trouvé les meilleures solutions beaucoup plus rapidement que les méthodes classiques.
• L'efficacité : Ils ont montré que l'on peut obtenir un gain de vitesse massif même si l'on n'utilise l'ordinateur quantique que pour une petite partie du travail (comme pour les derniers randonneurs de l'équipe).

5. Pourquoi cela importe pour l'avenir

Le document soutient que c'est un match parfait pour la technologie que nous avons actuellement (ou que nous aurons très bientôt).

• Résistance au bruit : Les ordinateurs quantiques d'aujourd'hui sont « bruyants » (ils font des erreurs). Les auteurs suggèrent que cette méthode est naturellement résistante au bruit. Même si le téléporteur quantique devient un peu flou, il suggère toujours un endroit aléatoire, ce qui est toujours mieux que rien.
• Puissance Hybride : Cela ne nécessite pas un ordinateur quantique parfait et sans erreur. Il a juste besoin d'un ordinateur quantique pour accomplir une tâche spécifique (suggérer des sauts) tandis qu'un puissant supercalculateur classique fait tout le reste du travail important.

Résumé

En bref, le document dit : « Arrêtez d'essayer de faire faire tout le travail à l'ordinateur quantique. Utilisez plutôt un ordinateur classique pour courir la course, et utilisez un ordinateur quantique juste pour donner aux coureurs un occasionnel et puissant « super-saut » pour les aider à échapper aux pièges. Nous avons prouvé que même quelques-uns de ces super-sauts permettent à toute l'équipe de gagner beaucoup plus vite. »

Note : Le document précise explicitement que ce sont des résultats de « preuve de concept » basés sur des simulations. Ils ne les ont pas encore testés sur du matériel quantique réel, et ne prétendent pas que ces méthodes résoudront immédiatement des problèmes industriels spécifiques du monde réel. Ils proposent une nouvelle façon de penser la manière d'utiliser les ordinateurs quantiques pour l'optimisation.

Résumé technique

Résumé Technique : Méthodes d'optimisation quantique heuristique non variationnelle

Énoncé du problème
L'optimisation est centrale dans les applications scientifiques et industrielles, pourtant les méthodes exactes classiques nécessitent souvent un temps exponentiel pour les problèmes combinatoires, ce qui rend nécessaire l'usage de solveurs heuristiques. Les algorithmes quantiques variationnels (VQA) et le recuit quantique (QA) dominent la recherche actuelle sur l'optimisation quantique résiliente au bruit, mais ils font face à des défis concernant la convergence, la profondeur de circuit et les exigences matérielles. De plus, de nombreuses approches quantiques existantes reposent sur des techniques tolérantes aux fautes ou des architectures matérielles spécifiques qui ne sont pas encore disponibles. Il existe un besoin pour des heuristiques quantiques alternatives, non variationnelles, capables d'exploiter les dispositifs quantiques de l'ère NISQ (Noisy Intermediate-Scale Quantum) via des cadres hybrides quantiques-classiques, en adressant spécifiquement la nature « vitreuse » des fonctions de coût (par exemple, les modèles de Sherrington-Kirkpatrick) où les méthodes classiques de Monte Carlo par chaînes de Markov (MCMC) souffrent d'une thermalisation lente en raison des barrières d'énergie.

Méthodologie
Les auteurs proposent une nouvelle classe d'heuristiques d'optimisation quantique qui remplacent les étapes de proposition locales des algorithmes basés sur le MCMC classique par une sous-routine quantique basée sur l'évolution en temps réel. Cette approche évite entièrement le cadre variationnel.

1. Mécanisme central (QeMCMC) : Le fondement est le Monte Carlo par chaînes de Markov amélioré par le quantique (QeMCMC). Au lieu d'une proposition locale classique (par exemple, inverser un seul spin), l'algorithme initialise un ordinateur quantique dans un état de base de calcul $|s\rangle$, applique une évolution unitaire $U = e^{-iHt}$, et mesure le résultat pour obtenir une nouvelle configuration $s'$.

   • Le Hamiltonien $H$ est construit comme une somme d'un terme de commande (lié au calcul quantique adiabatique, forçant la dispersion parmi les niveaux d'énergie) et du Hamiltonien d'Ising spécifique au problème.
   • Les hyperparamètres $\gamma$ (mélange) et $t$ (temps d'évolution) sont échantillonnés à partir de plages spécifiques.
   • Cette conception vise à générer des propositions avec de faibles différences d'énergie ($\Delta f$) et de grandes distances de Hamming ($\Delta H$), facilitant des mouvements non locaux qui échappent plus efficacement aux minima locaux que les propositions locales classiques.

2. Algorithmes proposés :

   • Recuit simulé amélioré par le quantique (QeSA) : Étend le recuit simulé (SA) classique en substituant la proposition locale classique par le mécanisme de proposition quantique, tout en suivant un calendrier de refroidissement logarithmique.
   • Température parallèle améliorée par le quantique (QePT) : Étend le parallélisme de température (PT), qui exécute plusieurs chaînes de Markov à différentes températures en parallèle avec des échanges périodiques de configurations. Dans le cas du QePT, les auteurs proposent une approche hybride où seules les chaînes de température basse (là où la thermalisation est la plus difficile) sont améliorées par le quantique, tandis que les chaînes à haute température restent classiques.

Contributions clés

• Proposition algorithmique : L'introduction du QeSA et du QePT en tant qu'heuristiques d'optimisation hybrides quantiques-classiques non variationnelles.
• Architecture hybride : Une démonstration que l'amélioration quantique complète n'est pas strictement nécessaire ; améliorer uniquement les chaînes de basse température qui constituent le « goulot d'étranglement » dans une configuration de parallélisme de température peut offrir des avantages significatifs, rendant cette approche plus réalisable pour l'intégration HPC-QC (Calcul Haute Performance - Calcul Quantique) à court terme.
• Numériques de preuve de concept : Les auteurs fournissent des résultats numériques simulés sur des instances de verre de spin de Sherrington-Kirkpatrick ($n \leq 10$) pour valider les propriétés de convergence de ces algorithmes par rapport aux références classiques.

Résultats

• Comportement de convergence : Dans les simulations, le SA classique se retrouve fréquemment piégé dans des minima locaux, présentant une variance élevée dans la probabilité de succès. En revanche, le QeSA démontre une capacité plus constante à atteindre le minimum global, la probabilité de succès augmentant régulièrement avec le nombre d'étapes.
• Effort de calcul : Les auteurs définissent l'« effort de calcul » ($N_p$) comme le produit de la longueur de la chaîne et du nombre de répétitions nécessaires pour trouver l'état fondamental avec une probabilité donnée.
  • Pour le QeSA, l'optimisation de la longueur de la chaîne révèle que l'approche quantique peut atteindre la probabilité de succès cible avec un effort total nettement inférieur à celui du SA classique pour les tailles de problèmes testées.
  • Pour le QePT, les résultats indiquent que le fait d'améliorer par le quantique uniquement les chaînes de basse température (par exemple, 2 répliques sur 4) fournit une amélioration tangible par rapport au PT entièrement classique, se rapprochant des performances des systèmes entièrement améliorés par le quantique. Cela suggère un compromis ressources-performance favorable.
• Mise à l'échelle (Scaling) : Les auteurs observent un potentiel avantage de mise à l'échelle (hypothétiquement jusqu'à l'ordre quartique) pour les instances de verre de spin en moyenne, bien qu'ils déclarent explicitement ne pas quantifier un avantage quantique définitif en raison des limitations de la simulation classique et de l'absence de tests sur matériel réel.

Signification et revendications
Le papier positionne ces méthodes comme une voie évolutive et potentiellement compétitive pour résoudre des problèmes d'optimisation à grande échelle à l'aide de dispositifs quantiques de l'ère NISQ.

• Robustesse : Les algorithmes sont revendiqués comme possédant une robustesse intrinsèque au bruit. Dans la limite d'un bruit de dépolarisation totale, les propositions quantiques reviennent à un échantillonnage uniforme, ce qui reste une étape MCMC valide, contrairement aux méthodes variationnelles qui peuvent échouer à converger.
• Parallélisme : L'approche supporte l'exécution parallèle sur des ressources quantiques et classiques, ne nécessitant que des communications classiques pour les échanges de répliques, ce qui s'aligne bien avec les architectures HPC actuelles.
• Modestie des revendications : Les auteurs sont explicites sur le fait qu'il s'agit de méthodes heuristiques sans garanties analytiques de vitesse pour les scénarios du pire cas. Ils reconnaissent que la performance de la proposition quantique est mal comprise analytiquement et que les avantages observés sont actuellement basés sur des numériques de preuve de concept sur du matériel simulé. Ils affirment que le véritable potentiel et la mise à l'échelle de ces méthodes ne pourront être vérifiés qu'une fois testés sur du matériel quantique réel avec une intégration quantique-classique plus étroite. Ce travail sert de motivation pour la recherche future et la validation expérimentale plutôt que de solution définitive à un avantage quantique.