Benchmark of Pauli Correlation Encoding for different optimisation problems

Cet article évalue un cadre d'optimisation quantique-classique utilisant l'encodage de corrélation de Pauli à travers quatre problèmes combinatoires, démontrant sa performance compétitive, sa résilience au bruit et son potentiel en tant que stratégie d'encodage efficace pour les dispositifs quantiques NISQ et tolérants aux fautes proches.

L'essentiel

Imaginez que vous essayez de résoudre un puzzle colossal, mais que vous n'avez qu'une toute petite boîte pour y ranger les pièces. Habituellement, si vous avez 1 000 pièces de puzzle, vous avez besoin d'une boîte assez grande pour contenir 1 000 emplacements. Mais et si vous pouviez magiquement compresser ces 1 000 pièces dans une boîte qui n'en contient que 10, sans perdre la capacité de résoudre le puzzle ?

C'est essentiellement ce dont traite ce document. Les chercheurs testent un nouveau « tour de magie » pour les ordinateurs quantiques appelé Codage de Corrélation de Pauli (PCE - Pauli Correlation Encoding).

Voici une décomposition de leur travail utilisant des analogies simples :

1. Le problème : La limitation de la « petite boîte »

Les ordinateurs quantiques sont comme de nouveaux moteurs puissants, mais pour l'instant, ils sont très petits et bruyants (comme un moteur de voiture qui bafouille un peu). Ils possèdent un nombre limité de « qubits » (les emplacements de notre boîte).

• L'ancienne méthode : Pour résoudre un problème avec 100 variables (comme décider de la place de chacun lors d'un dîner), les anciennes méthodes quantiques nécessitaient 100 qubits. Si vous aviez 1 000 variables, il vous faudrait 1 000 qubits. Comme les ordinateurs quantiques actuels n'ont qu'environ 50 à 100 qubits, ils ne peuvent pas résoudre de gros problèmes.
• Le nouveau tour (PCE) : La méthode PCE est comme un algorithme de compression pour un fichier ZIP. Elle permet à l'ordinateur de représenter 1 000 variables en utilisant seulement une poignée de qubits (peut-être 10 ou 20). Elle y parvient en observant comment les variables se « corrèlent » ou dansent ensemble, plutôt qu'en donnant à chacune son propre siège dédié.

2. Le test : Trois puzzles classiques

Pour voir si ce tour de compression fonctionne réellement, l'équipe l'a testé sur trois puzzles célèbres et difficiles issus d'une bibliothèque de tests standard (QOPTLib) :

• Le puzzle du « placement à table » (Problème de la Coupe Maximale / Maximum Cut) : Imaginez un graphe de personnes qui s'apprécient ou se détestent. L'objectif est de diviser ces personnes en deux groupes de sorte que le nombre maximal de « détestances » se produise entre les groupes, et non à l'intérieur de ceux-ci.
  • Résultat : La méthode PCE a très bien réussi. Elle a trouvé des solutions aussi bonnes que les meilleures réponses connues, prouvant qu'elle peut gérer ce type de problème efficacement.
• Le puzzle du « camion de déménagement » (Problème du Bin Packing) : Vous avez un tas de boîtes de différentes tailles et un nombre limité de camions. Vous voulez faire entrer toutes les boîtes dans le moins de camions possible sans les surcharger.
  • Résultat : C'était délicat. La méthode a trouvé des solutions, mais elle a eu du mal à tout faire entrer parfaitement dans les camions sans enfreindre les règles (comme la surcharge d'un camion). Cependant, lorsque les chercheurs ont ajouté une « équipe de nettoyage » (une étape de post-traitement classique) pour réorganiser les boîtes après que l'ordinateur quantique a terminé, les résultats se sont considérablement améliorés.
• Le puzzle du « voyageur de commerce » (TSP) : Un vendeur doit visiter une liste de villes exactement une fois et revenir chez lui, en empruntant le trajet le plus court possible.
  • Résultat : Similaire au puzzle du camion de déménagement, l'ordinateur quantique a trouvé un bon itinéraire, mais pas toujours le parfait. Là encore, l'« équipe de nettoyage » (le post-traitement) a aidé à affiner l'itinéraire pour le rendre beaucoup plus court.

3. Les « boutons de réglage » (Hyperparamètres)

Les chercheurs ont découvert que le tour de magie ne fonctionne pas automatiquement ; il faut le régler avec soin. Ils ont utilisé deux principaux « boutons » :

• Le bouton de « netteté » (Alpha) : Imaginez que vous essayez de décider si une lumière est « allumée » ou « éteinte ». Si le bouton est réglé trop bas, la lumière n'est qu'une lueur faible et floue (un mélange de allumé et éteint). Les chercheurs ont découvert qu'en tournant ce bouton vers le haut, la lumière bascule nettement sur « allumé » ou « éteint », menant à de meilleures solutions.
• Le bouton de « régularisation » (Beta) : C'est un assistant qui tente de maintenir les chiffres de manière stable. Curieusement, ils ont découvert que parfois, éteindre ce bouton ne nuisait pas aux résultats, ce qui signifie que le système est assez robuste.

4. Le test de réalité face au « bruit »

Les vrais ordinateurs quantiques ne sont pas parfaits ; ils sont comme une radio avec de la friture. Les chercheurs ont testé ce qui se passe lorsqu'ils exécutent le programme sur une machine simulée bruyante (imitant le matériel réel).

• La conclusion : Habituellement, le bruit gâche les calculs. Cependant, ils ont découvert quelque chose de surprenant : un peu de bruit a en fait aidé l'ordinateur à échapper aux « impasses » (minima locaux). C'est comme secouer légèrement un labyrinthe pour aider une bille à trouver la sortie lorsqu'elle est coincée dans un petit creux.
• La limite : Cependant, si le bruit devient trop fort, le signal se perd. Ils ont découvert que pour obtenir une réponse claire, il faut exécuter le calcul de nombreuses fois (shots) afin de moyenner la friture.

5. Le verdict

Le document conclut que ce « tour de compression » (PCE) est un moyen très prometteur de résoudre de grands problèmes d'optimisation sur les ordinateurs quantiques actuels, qui sont petits et bruyants.

• Points forts : Il réduit drastiquement le nombre de qubits nécessaires, nous permettant de s'attaquer à des problèmes qui étaient auparavant trop vastes pour les ordinateurs quantiques.
• Points faibles : Il nécessite un réglage minutieux des « boutons » (hyperparamètres) et nécessite souvent l'aide d'un ordinateur classique pour effectuer un « nettoyage » final de la réponse afin de la rendre parfaite.

En résumé, les chercheurs ont montré qu'en compressant le problème, nous pouvons faire entrer de gigantesques puzzles dans de minuscules boîtes quantiques et, avec un peu d'aide d'ordinateurs classiques pour ranger les résultats, nous pouvons obtenir de très bonnes réponses, même sur du matériel imparfait.

Résumé technique

Résumé Technique : Évaluation de l'encodage par corrélation de Pauli pour différents problèmes d'optimisation

Énoncé du problème
L'article traite des limitations de scalabilité des algorithmes d'optimisation quantique variationnelle (VQA) dans l'ère NISQ (Noisy Intermediate-Scale Quantum). Plus précisément, il cible la croissance linéaire des besoins en qubits dans les approches standards telles que l'algorithme d'optimisation approximative quantique (QAOA), où le nombre de qubits croît linéairement avec le nombre de variables binaires classiques. Cette contrainte entrave l'application de l'optimisation quantique à des problèmes combinatoires de grande échelle. L'étude examine l'encodage par corrélation de Pauli (PCE), un schéma capable de représenter $m$ variables binaires à l'aide d'un nombre polynomial de qubits $n$ (où $n \ll m$), afin de déterminer son efficacité à travers divers problèmes d'optimisation classiques.

Méthodologie
Les auteurs évaluent le cadre PCE à l'aide d'une approche hybride quantique-classique sur trois problèmes d'optimisation combinatoire classiques : le problème de la coupe maximale (MCP), le problème de mise en bacs (BPP) et le problème du voyageur de commerce (TSP). L'évaluation utilise des instances issues du benchmark QOPTLib.

• Schéma d'encodage : Le PCE encode les variables binaires $z_i \in \{-1, 1\}$ comme le signe des valeurs attendues de chaînes de Pauli traceless spécifiques $\Pi_i$. L'encodage repose sur un ordre de compression $k$, où le nombre de variables évolue selon $m \approx 3 \binom{n}{k}$.
• Ansatz variationnel : L'état quantique $|\Psi\rangle$ est préparé à l'aide d'un circuit quantique paramétré (PQC) de type "brick-wall" (mur de briques), efficace pour le matériel et indépendant du problème. La profondeur du circuit évolue selon $O(m^{1-1/k})$, équilibrant l'expressivité et le nombre de paramètres variationnels.
• Stratégie d'optimisation : L'optimisation classique des paramètres du circuit est réalisée à l'aide de l'évolution différentielle (DE), un algorithme évolutionnaire sans gradient choisi pour sa robustesse face aux plateaux stériles (barren plateaux) et aux minima locaux.
• Relaxation et régularisation : Pour faciliter l'optimisation, la fonction signe discrète est relaxée à l'aide d'une fonction tangente hyperbolique $z_i = \tanh(\alpha \langle \Pi_i \rangle)$, contrôlée par l'hyperparamètre $\alpha$. Un terme de régularisation pondéré par $\beta$ est inclus pour concentrer les valeurs attendues autour de zéro.
• Formulation de pénalité : Pour les problèmes contraints (BPP et TSP), les contraintes sont intégrées dans la fonction de coût via des termes de pénalité avec des poids $\lambda_1, \lambda_2, \lambda_3$. L'étude explore le problème "Big-M" du choix des poids de pénalité appropriés pour assurer la faisabilité sans déformer le paysage d'optimisation.
• Post-traitement : Une étape de post-traitement classique est appliquée à tous les résultats. Pour le MCP, des inversions de bits (bit-flip swaps) sont utilisées ; pour le BPP, des réassignations d'objages uniques dans les bacs ; et pour le TSP, une heuristique 2-opt est employée pour affiner les tours reconstitués.
• Analyse du bruit : L'étude inclut des exécutions basées sur le nombre de tirages (shots) utilisant l'émulateur CUNQA (imitant le matériel IBM Sherbrooke) pour analyser l'impact du bruit de tirage et des erreurs de porte sur l'estimation des valeurs attendues et la dynamique d'optimisation.

Contributions clés et résultats
L'article évalue le cadre PCE par rapport aux solutions de référence QOPTLib et aux solveurs hybrides D-WAVE.

1. Performance selon les problèmes :

   • Coupe Maximale (MCP) : Le cadre PCE obtient des performances compétitives, atteignant souvent le seuil de dureté théorique ($16/17$) et trouvant des solutions équivalentes ou meilleures que la référence. Des ordres de compression ($k$) plus élevés produisent généralement une meilleure qualité de solution en raison d'une profondeur de circuit et d'une expressivité accrues, malgré un coût computationnel plus élevé.
   • Mise en bacs (BPP) : La méthode démontre un fort potentiel, particulièrement pour les petites instances. Cependant, la faisabilité est très sensible à l'ordre de compression et aux hyperparamètres. Alors que $k=4$ a pu produire des solutions faisables pour toutes les instances testées, les ordres inférieurs ont échoué pour les grands $N$. Le post-traitement a considérablement amélioré le nombre de bacs utilisés, récupérant souvent des emballages proches de l'optimal.
   • Voyageur de Commerce (TSP) : Similairement au BPP, l'approche produit des solutions initiales compétitives. Pour $k \in \{3, 4\}$, l'algorithme égale ou surpasse fréquemment les solutions de référence. Le post-traitement avec 2-opt réduit systématiquement la longueur du tour. Les taux de faisabilité chutent pour les instances plus grandes avec un $k$ plus faible, soulignant le compromis entre compression et capacité à satisfaire des contraintes strictes.

2. Sensibilité aux hyperparamètres :

   • L'hyperparamètre $\alpha$ (contrôlant la netteté de la binarisation) est critique. Des valeurs plus élevées améliorent généralement la qualité de la solution en empêchant les variables de rester dans le régime linéaire de la fonction $\tanh$ (proche de 0,5), ce qui cause une ambiguïté lors de la reconstruction.
   • Le paramètre de régularisation $\beta$ a montré moins d'impact dans cette étude que dans la proposition originale ; fixer $\beta=0$ donnait souvent des résultats comparables à des valeurs non nulles, probablement en raison des poids de pénalité spécifiques utilisés.
   • Les poids de pénalité ($\lambda$) nécessitent un réglage minutieux. Des poids excessivement élevés n'ont pas garanti une meilleure binarisation et ont pu conduire à une satisfaction de contrainte "douce" où les variables prennent des valeurs fractionnaires.

3. Effets du bruit et des tirages (shots) :

   • Dans les simulations idéales, augmenter le nombre de tirages réduit l'erreur de convergence vers $\sim 10^{-3}$.
   • Dans les simulations bruitées (backend IBM Sherbrooke), le bruit matériel domine, plafonnant l'erreur absolue moyenne (MAE) à environ 0,02ce regardless du nombre de tirages.
   • Contre-intuitivement, la présence de bruit dans le processus d'optimisation itératif (avec 1000 tirages) a parfois aidé l'algorithme DE à échapper aux minima locaux, menant à de meilleurs ratios de solutions par rapport aux exécutions idéales sans bruit dans certains cas spécifiques.

Signification et affirmations
L'article affirme que l'encodage par corrélation de Pauli représente une stratégie prometteuse pour l'optimisation quantique dans l'ère NISQ et l'ère proche du tolérance aux fautes. Sa principale importance réside dans sa capacité à réduire drastiquement les besoins en qubits, permettant le traitement de problèmes combinatoires à grande échelle avec un nombre relativement restreint de qubits.

Les auteurs concluent que, bien que le cadre basé sur le PCE soit capable d'obtenir des solutions compétitives, et dans certains cas supérieures, par rapport aux références classiques et aux solveurs hybrides quantiques-classiques, son succès dépend fortement de :

1. La reformulation spécifique au problème : adapter correctement les fonctions de coût et les poids de pénalité.
2. Le calibrage des hyperparamètres : spécifiquement le réglage de $\alpha$ et de l'ordre de compression $k$.
3. Le post-traitement : la nécessité d'étapes de raffinement classique pour récupérer des solutions discrètes de haute qualité à partir de la sortie quantique relaxée.

Ce travail souligne que, bien que le PCE offre un encodage scalable, le problème "Big-M" de la sélection des pénalités et le compromis entre l'expressivité du circuit (profondeur) et l'entraînabilité restent des défis critiques. L'étude établit une référence pratique pour les temps d'exécution et les limites d'erreur, suggérant qu'avec des optimiseurs classiques appropriés et la parallélisation, l'approche est viable pour le futur matériel quantique, tout en servant également de puissant algorithme classique inspiré du quantique.