⚛️ quantum physics

A competitive NISQ and qubit-efficient solver for the LABS problem

Cet article démontre que le cadre de l'encodage de corrélation de Pauli (PCE), une approche variationnelle efficace en termes de qubits, résout efficacement le problème des séquences binaires à faible autocorrélation (LABS) avec une mise à l'échelle et une résilience au bruit améliorées, surpassant les heuristiques classiques de pointe tout en nécessitant nettement moins de ressources quantiques.

Auteurs originaux : Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Publié 2026-01-27

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'organiser une longue file de personnes, où chaque personne tient soit un drapeau rouge (+1), soit un drapeau bleu (-1). Votre objectif est d'organiser les drapeaux de sorte que, si vous regardez la file sous différents angles, les motifs de drapeaux rouges et bleus ne s'alignent pas accidentellement de manière confuse. Dans le monde scientifique, cela s'appelle le problème des Séquences Binaires à Faible Autocorrélation (LABS). C'est un casse-tête notoirement difficile utilisé pour tester l'efficacité des ordinateurs à résoudre des problèmes d'optimisation complexes.

Ce document présente une nouvelle méthode ingénieuse pour que les ordinateurs quantiques (plus précisément les modèles actuels, dits "bruyants", connus sous le nom de NISQ) puissent résoudre ce casse-tête plus efficacement que de nombreuses méthodes traditionnelles. Voici la décomposition de leur approche :

1. Le Problème : Un « terrain de golf » d'erreurs

Imaginez que la recherche de l'arrangement parfait des drapeaux revienne à chercher le point le plus bas dans un vaste paysage brumeux.

Le Paysage : La plupart du temps, vous marchez sur une plaine plate parsemée de petites dépressions (minima locaux). Ces creux ressemblent au fond d'une vallée, mais ce ne sont pas les vrais fonds.
L'Objecte : La véritable solution est un seul trou, minuscule et profond, au milieu de la plaine (le minimum global).
La Difficulté : Comme il existe de nombreux "faux fonds", les programmes informatiques standards se retrouvent souvent bloqués dans l'un d'eux et abandonnent, pensant avoir trouvé la meilleure réponse alors qu'ils ne l'ont pas trouvée.

2. La Solution : Une carte « compressée » (Codage de Corrélation de Pauli)

Habituellement, pour résoudre un problème de $N$ variables (comme 45 drapeaux), un ordinateur quantique a besoin de 45 bits quantiques (qubits). Mais les ordinateurs quantiques actuels sont petits et fragiles ; ils ne peuvent pas encore gérer autant de bits.

Les auteurs utilisent une astuce appelée Codage de Corrélation de Pauli (PCE).

L'Analogie : Imaginez que vous avez une immense bibliothèque de livres (ces 45 drapeaux), mais que vous n'avez qu'un petit carnet de notes (4 qubits). Au lieu de noter chaque livre individuellement, vous utilisez un code spécial. Vous notez les relations entre les livres.
Comment ça marche : Ils projettent les 45 drapeaux sur seulement 4 qubits. C'est comme compresser un film en haute définition en un tout petit fichier sans perdre l'intrigue. Cela leur permet de s'attaquer à des problèmes énormes (jusqu'à 45 drapeaux dans leur simulation, et même 120 lors d'une expérience réelle) en utilisant très peu de ressources quantiques.

3. La Stratégie : Choisir les bonnes « questions »

Pour tirer le maximum d'informations de ces 4 qubits, l'équipe a dû décider comment poser des questions à l'ordinateur quantique.

L'ensemble commutatif : Poser des questions qui n'interfèrent pas les unes avec les autres (comme demander la météo et l'heure de la journée).
L'ensemble non-commutatif : Poser des questions qui interfèrent les unes avec les autres (comme essayer de mesurer simultanément la position et la vitesse d'une pièce de monnaie en rotation).
Le Résultat : Ils ont découvert que les questions « interférant » (non-commutatives) étaient bien meilleures. C'est comme secouer un bocal de billes pour voir l'image globale plutôt que de simplement regarder un seul côté. Cette méthode a donné les meilleurs résultats.

4. La Performance : Plus rapide et plus intelligente

Ils ont testé leur nouvelle méthode contre les meilleurs programmes informatiques classiques (réguliers) et d'autres méthodes quantiques.

La Course : Ils ont mesuré le « Temps de résolution » (Time-to-Solution, le temps nécessaire pour trouver la réponse parfaite).
Le Résultat : Leur méthode quantique était plus rapide que les meilleurs programmes informatiques « heuristiques » classiques (un algorithme de supposition intelligente appelé recherche Tabu) pour les tailles de problèmes testées.
L'Échelle : Alors que d'autres méthodes quantiques nécessitent des ordinateurs massifs et parfaits qui n'existent pas encore, cette méthode fonctionne sur des appareils de petite taille et actuels. Elle passe mieux à l'échelle, ce qui signifie qu'à mesure que le problème s'agrandit, leur méthode reste compétitive plus longtemps que les autres.

5. Le Test en conditions réelles : Le terrain de jeu « bruyant »

Les auteurs n'ont pas seulement réalisé des simulations ; ils ont réellement exécuté leur algorithme sur un véritable ordinateur quantique fabriqué par IonQ (le processeur Forte).

Le Défi : Les vrais ordinateurs quantiques sont « bruyants ». C'est comme essayer d'entendre un murmure dans un ouragan. Le matériel commet des erreurs.
Le Résultat : Ils ont réussi à résoudre un problème de 120 drapeaux (le plus grand jamais montré sur du matériel quantique pour ce problème spécifique).
Résilience : Même avec l'« ouragan » de bruit, la réponse finale était toujours bonne. Ils ont constaté qu'ils n'avaient pas besoin de millions d'essais (shots) pour obtenir une réponse décente ; quelques milliers suffisaient. Cependant, le bruit a rendu la réponse finale légèrement moins parfaite qu'une simulation parfaite le serait.

Résumé

L'article affirme qu'en utilisant une technique de « compression » ingénieuse (PCE) et en posant les bons types de questions (opérateurs non-commutatifs), ils peuvent résoudre un casse-tête mathématique très difficile (LABS) sur de petits ordinateurs quantiques imparfaits. Leur méthode est plus rapide que les meilleures méthodes de supposition classiques actuelles pour les tailles testées, et elle est assez robuste pour fonctionner sur du matériel réel et bruyant dès aujourd'hui. Ils suggèrent que cela pourrait être un outil puissant pour résoudre des problèmes difficiles dès maintenant, avant même que nous ne disposions d'ordinateurs quantiques parfaits et sans erreur.

Résumé Technique : Un Solveur Compétitif pour le Problème LABS, Adapté au NISQ et Économe en Qubits

Définition du Problème
Le problème des séquences binaires à faible autocorrélation (LABS - Low Autocorrelation Binary Sequences) est un défi d'optimisation combinatoire bien connu, de classe NP-difficile, avec des applications en ingénierie, en communications et en physique statistique. Étant donné un entier $N$ , l'objectif est de trouver une séquence binaire $x \in \{-1, +1\}^N$ qui minimise l'énergie des lobes secondaires $E(x)$ , définie comme la somme des carrés des autocorrelations $C_\ell(x)$ pour $\ell > 0$ . Équivalemment, le but est de maximiser le facteur de mérite $F(x) = N^2 / 2E(x)$ . Le problème est caractérisé par un paysage d'optimisation de type « terrain de golf » (golf course) présentant de nombreux minima locaux et des minima globaux isolés. Bien que des solutions exactes soient connues pour $N \le 66$ , trouver des solutions optimales ou de haute qualité pour des $N$ plus grands devient insoluble pour les méthodes classiques par force brute, et même les heuristiques de pointe comme le Memetic Tabu Search font face à des défis de mise à l'échelle importants.

Méthodologie : Encodage par Corrélation de Pauli (PCE)
Les auteurs proposent un solveur quantique variationnel économe en qubits basé sur le cadre d'encodage par corrélation de Pauli (PCE). Contrairement aux encodages standards qui nécessitent un qubit par variable binaire, le PCE compresse $N$ variables binaires en $n$ qubits où $N = \text{poly}(n)$ , spécifiquement $n \ll N$ .

Encodage : Les variables binaires $x_i$ sont encodées comme les signes des valeurs d'espérance d'un ensemble de chaînes de Pauli à $n$ qubits $\Pi = \{\Pi_i\}_{i \in [N]}$ :
$x_i := \text{sgn}(\langle \Pi_i \rangle)$
où $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$ .
Optimisation : L'état quantique $|\Psi\rangle$ est généré par un circuit de type "brickwork" paramétré. Les paramètres sont optimisés classiquement pour minimiser une fonction de perte non linéaire $L$ . Pour faciliter l'optimisation basée sur le gradient, les variables binaires sont relaxées à l'aide d'une fonction tangente hyperbolique : $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$ . La fonction de perte inclut un terme de régularisation pour empêcher la disparition des corrélateurs.
Sélection de l'ensemble de Pauli : L'étude évalue deux ensembles distincts pour $\Pi$ $Π$ :
1. $\Pi(C)$ : Un ensemble de opérateurs de Pauli choisis aléatoirement et mutuellement commutants.
2. $\Pi(NC)$ : Un ensemble conçu pour maximiser le nombre d'opérateurs de Pauli mutuellement non commutants. Les auteurs émettent l'hypothèse que la non-commutativité conduit à des mesures mutuellement biaisées, augmentant ainsi l'expressivité et l'indépendance des variables encodées.

Contributions Clés et Résultats

Simulations Numériques ( $N \le 45$ ) :
- Les auteurs ont simulé le solveur PCE utilisant $n=4$ qubits et un circuit de profondeur 15 (30 portes à deux qubits, 150 paramètres).
- La variante $\Pi(NC)$ a systématiquement surpassé la variante commutante.
- Analyse de Mise à l'Échelle (Scaling) : Le Temps pour la Solution (TTS - Time-to-Solution), défini comme le nombre d'évaluations de la fonction de coût nécessaires pour trouver la solution exacte, a été comparé à l'algorithme QAOA et au Memetic Tabu Search.
  - Mise à l'échelle PCE : $O(1.330^N)$ pour les instances paires et $O(1.326^N)$ pour les instances impaires.
  - Comparaison : Cette mise à l'échelle améliore celle du QAOA qui est de $O(1.46^N)$ et est légèrement meilleure que la mise à l'échelle de l'état de l'art du Tabu Search, soit $O(1.34^N)$ (pour les instances paires) et $O(1.409^N)$ (pour les instances impaires).
- Les résultats indiquent un avantage de type loi de puissance de PCE sur les bases de référence classiques dans la plage testée.
Démonstration Expérimentale (IonQ Forte) :
- Les auteurs ont réalisé une démonstration de preuve de concept sur le processeur quantique IonQ Forte pour une taille d'instance $N=120$ , la plus grande démontrée à ce jour sur du matériel quantique.
- Pour l'expérience, un ensemble spécifique de corrélateurs à $k$ -corps ( $k=2$ ) compatible avec le matériel a été utilisé, nécessitant seulement trois configurations de mesure.
- Résilience au Bruit : L'étude a révélé que si le bruit de tir (shot noise) avait un impact mineur (nécessitant seulement quelques milliers de tirs), le bruit matériel dégradait significativement la qualité de la solution finale. Cependant, le processus d'entraînement lui-même est resté robuste, suggérant que l'atténuation des erreurs ou des taux de compression plus élevés sont critiques pour un déploiement à court terme.

Signification et Revendications
L'article affirme que les solveurs basés sur le PCE représentent une voie prometteuse pour deux approches distinctes :

Heuristiques Classiques d'Inspiration Quantique : Même lorsqu'ils sont simulés classiquement, le cadre PCE offre une mise à l'échelle compétitive ou supérieure par rapport aux principales heuristiques classiques pour des problèmes difficiles comme LABS, agissant comme un puissant algorithme d'inspiration quantique.
Réduction des Ressources NISQ : En encodant $N$ variables dans un nombre de qubits polynomialement plus petit ( $n$ ), le PCE réduit considérablement les exigences en qubits pour les dispositifs de l'ère NISQ. Les auteurs notent que $n=8$ qubits pourrait théoriquement traiter des instances allant jusqu'à $N=66$ (où les solutions exactes sont connues), et $n \le 20$ pourrait défier les plus grandes instances solubles par les heuristiques classiques.

Les auteurs maintiennent une position modeste concernant l'« avantage quantique ». Ils reconnaissent que la surcharge liée à la simulation de vecteurs d'états quantiques complets sur des benchmarks classiques retarde le point de croisement où un véritable avantage de temps d'exécution quantique devient évident. De plus, ils notent que bien que la méthode montre de solides performances, elle manque actuellement de garanties de performance. Néanmoins, la capacité de résoudre des instances $N=120$ sur le matériel actuel avec des budgets de tir modestes et l'observation d'une résilience au bruit soulignent le potentiel du PCE comme outil de réduction des besoins en ressources pour les algorithmes quantiques réels.