Quantum Feature Selection with Higher-Order Binary Optimization on Trapped-Ion Hardware

Ce papier présente un cadre de sélection de caractéristiques quantique utilisant une formulation d'optimisation binaire non contrainte d'ordre supérieur (HUBO) avec des dépendances multivariées, qui a été mise en œuvre avec succès sur le matériel à ions piégés IonQ Forte pour démontrer des performances de classification compétitives et la faisabilité de l'optimisation quantique d'ordre supérieur pour le prétraitement en apprentissage automatique.

L'essentiel

Imaginez que vous essayez de résoudre un puzzle massif, mais que vous avez 32 pièces différentes (caractéristiques) parmi lesquelles choisir, et que vous n'en avez besoin que de quelques-unes pour voir l'image complète clairement. Le problème est que certaines pièces semblent importantes en elles-mêmes, d'autres semblent importantes uniquement lorsqu'elles sont associées à d'autres, et certaines sont tout simplement des duplicatas les unes des autres.

Ce papier décrit une nouvelle façon d'utiliser un ordinateur quantique pour trouver l'ensemble parfait de pièces de puzzle. Au lieu de simplement examiner les pièces une par une ou par paires (comme le font les méthodes traditionnelles), cette nouvelle méthode examine comment des groupes de trois pièces fonctionnent ensemble.

Voici la décomposition de leur approche en utilisant des analogies simples :

1. Le Problème : Trop de Choix

En science des données, la « Sélection de Caractéristiques » est le processus consistant à choisir les informations les plus utiles parmi une longue liste.

• L'Ancienne Façon (QUBO) : Imaginez essayer de choisir les meilleurs membres d'une équipe en demandant uniquement : « Quelle est la qualité de la Personne A ? » et « Comment la Personne A et la Personne B s'entendent-elles ? ». Cela fait passer à côté du fait que parfois, un groupe spécifique de trois personnes crée une chimie magique que vous ne pouvez pas voir en les regardant individuellement ou par paires.
• La Nouvelle Façon (HUBO) : Les auteurs ont créé une méthode qui demande : « Quelle est la qualité de ce trio spécifique de personnes travaillant ensemble ? ». Ils appellent cela l'Optimisation Binaire Non Contrainte d'Ordre Supérieur (HUBO). C'est comme avoir un manager sur-intelligent capable de comprendre instantanément les dynamiques de groupe complexes, et pas seulement les compétences individuelles.

2. La Recette : Le Modèle « Énergie »

Pour trouver la meilleure équipe, les chercheurs ont construit une « recette » mathématique appelée Hamiltonien (pensez-y comme à un tableau de scores).

• Pertinence (Un corps) : Si une information est très utile en elle-même, le tableau de scores lui accorde un « bonus » (abaisse l'énergie).
• Redondance (Deux corps) : Si deux informations disent exactement la même chose, le tableau de scores pénalise le fait de choisir les deux (augmente l'énergie).
• Groupes Complexes (Trois corps) : C'est le secret. Si trois informations créent une insight puissante uniquement lorsqu'elles sont combinées, le tableau de scores récompense ce trio spécifique.
• La Règle « Pas de Repas Gratuit » : Pour empêcher l'ordinateur de simplement choisir chaque pièce individuelle (ce qui est la solution paresseuse et facile), ils ont ajouté une pénalité. C'est comme un coach strict qui dit : « Vous ne pouvez pas choisir toute l'équipe ; vous devez choisir le meilleur petit groupe ».

3. La Machine : La Salle de Sport Quantique

Ils ont testé cette recette sur un véritable ordinateur quantique fabriqué par IonQ, qui utilise des ions piégés (atomes chargés) comme ses « bits ».

• L'Entraînement : Ils ont utilisé une technique appelée Optimisation Quantique Numérisée Contre-Adiabatique (DCQO). Imaginez essayer de trouver le point le plus bas dans une vallée brumeuse. Une marche normale pourrait vous coincer dans une petite dépression. Cette technique est comme une visite guidée qui aide l'ordinateur à « glisser » rapidement et fluidement vers le point le plus bas absolu (la meilleure solution) sans rester coincé dans le brouillard.
• Le Résultat : L'ordinateur a effectué cet « entraînement » et a émis une liste de probabilités pour chaque caractéristique, indiquant à quelle fréquence cette caractéristique apparaissait dans les meilleures solutions.

4. L'Essai Routier : Deux Scénarios Réels

Ils ont testé leur méthode sur deux ensembles de données différents pour voir si cela fonctionnait réellement :

• Scénario A : L'Ensemble de Données Gallstones (Médical)

  • La Tâche : Prédire si un patient a des calculs biliaires en se basant sur 32 métriques de santé (comme le cholestérol, l'âge, le poids).
  • Le Résultat : La méthode quantique a sélectionné 19 métriques clés. Elle a surpassé les méthodes informatiques standard (comme l'ACP ou le choix des 19 premiers par classement simple). Elle a trouvé une liste plus petite et plus épurée de symptômes qui prédisait la maladie aussi bien, voire mieux, que l'utilisation de toutes les données.
  • La Vérification : Ils ont comparé les résultats du véritable ordinateur quantique avec une simulation parfaite, sans bruit. Ils correspondaient très étroitement, prouvant que le matériel réel fonctionne comme prévu.

• Scénario B : L'Ensemble de Données Spambase (Courrier Électronique)

  • La Tâche : Déterminer si un e-mail est un spam ou non, basé sur 32 fréquences de mots/caractères.
  • Le Résultat : La méthode quantique a réduit la liste à 23 indicateurs clés. Encore une fois, elle a surpassé les méthodes standard. Elle a réussi à éliminer le « bruit » (mots redondants) tout en conservant le « signal » (mots qui indiquent réellement un spam).

5. La Conclusion

Le papier affirme que :

1. Ça marche : L'ordinateur quantique a trouvé avec succès des sous-ensembles de données de haute qualité.
2. C'est mieux que l'ancienne façon : En examinant les relations « à trois voies » (d'ordre supérieur), il a trouvé de meilleures combinaisons que les méthodes qui ne regardent que les individus ou les paires.
3. C'est efficace : Il a réduit la quantité de données nécessaire pour faire des prédictions précises sans perdre en précision.
4. Le matériel est prêt : Les résultats de la véritable machine IonQ étaient très similaires aux simulations parfaites, suggérant que les ordinateurs quantiques d'aujourd'hui sont déjà capables de gérer ces problèmes complexes de « dynamiques de groupe ».

En bref, les auteurs ont construit un « éclaireur » quantique qui est meilleur pour repérer les membres d'équipe les plus précieux dans un groupe, car il comprend comment les gens interagissent par trois, et pas seulement par paires. Ils ont prouvé que cela fonctionne sur du matériel réel avec de vraies données.

Résumé technique

1. Énoncé du problème

La sélection de caractéristiques (FS) est cruciale pour améliorer l'interprétabilité des modèles, réduire le surajustement et optimiser l'efficacité computationnelle dans les ensembles de données de haute dimension. Cependant, les méthodes classiques de FS présentent des limitations significatives :

• Les méthodes d'enveloppe (wrapper) sont coûteuses en calcul et s'étendent mal.
• Les méthodes de filtrage (filter) (par exemple, l'information mutuelle) ignorent souvent les interactions entre caractéristiques.
• Les méthodes intégrées (embedded) sont sensibles aux hyperparamètres et sont souvent biaisées vers des dépendances linéaires ou hiérarchiques.
• Limitations quantiques : Les approches quantiques existantes formulent généralement la FS comme un problème d'Optimisation Binaire Non Contrainte Quadratique (QUBO). Le QUBO étant limité aux interactions à un et deux corps, il force à négliger, approximer ou introduire via des surcoûts de quadratisation coûteux les dépendances d'ordre supérieur (relations multivariées).

Défi central : Comment capturer explicitement des dépendances statistiques complexes d'ordre supérieur entre les caractéristiques dans un cadre d'optimisation quantique sans réduire le problème à une forme quadratique, et comment exécuter cela sur le matériel quantique intermédiaire à échelle intermédiaire (NISQ) actuel.

2. Méthodologie

Les auteurs proposent un cadre novateur basé sur l'Optimisation Binaire Non Contrainte d'Ordre Supérieur (HUBO) exécuté sur du matériel à ions piégés IonQ Forte.

A. Formulation HUBO

Au lieu d'un hamiltonien quadratique, le problème est encodé dans un hamiltonien contenant des termes d'interaction à un, deux et trois corps :
$$H(Z) = \sum_i h_i Z_i + \sum_{i<j} J_{ij} Z_i Z_j + \sum_{i<j<k} K_{ijk} Z_i Z_j Z_k + C$$

• Variables : $Z_i \in \{-1, +1\}$ (convention d'Ising), où $-1$ indique la sélection de la caractéristique.
• Coefficients : Dérivés de l'Information Mutuelle (MI) :
  • $h_i$: Encode la pertinence individuelle de la caractéristique par rapport à la cible.
  • $J_{ij}$: Encode la redondance paire (pénalisant les caractéristiques corrélées).
  • $K_{ijk}$: Encode les dépendances d'ordre supérieur (capturant l'information présente uniquement dans des groupes de trois caractéristiques).
• Pénalités structurées : Pour éviter les solutions triviales (par exemple, sélectionner toutes les caractéristiques), un terme de pénalité linéaire $H_\lambda$ est ajouté, supprimant les caractéristiques dont la pertinence est négligeable en dessous d'un seuil $\tau$.

B. Algorithme d'optimisation : Optimisation Quantique Contre-Adiabatique Numérisée (DCQO)

Les auteurs utilisent la DCQO pour trouver l'état fondamental du hamiltonien HUBO :

• Mécanisme : Une approche basée sur les portes inspirée des « raccourcis vers l'adiabaticité ». Elle interpole entre un hamiltonien pilote et le hamiltonien HUBO cible tout en ajoutant des termes contre-adiabatiques approximatifs pour supprimer les transitions diabatiques lors d'une évolution de durée finie.
• Exécution : Implémentée sur IonQ Forte (ions Yb+) avec une connectivité tout-à-tout, ce qui supporte naturellement les interactions à longue portée requises par le HUBO sans encodage complexe.

C. Post-traitement et sélection

1. Échantillonnage : Le système est mesuré pour générer des échantillons de chaînes de bits.
2. Filtrage : Les échantillons sont classés par énergie ; seule la fraction la plus basse en énergie ($\rho$, par exemple les 25 % supérieurs) est conservée pour filtrer le bruit.
3. Notation : L'importance de la caractéristique ($I_i$) est calculée comme la fréquence empirique d'une caractéristique étant sélectionnée ($x_i=1$) au sein du sous-ensemble de basse énergie.
4. Seuillage : Les caractéristiques sont sélectionnées si $I_i \geq \delta$.

3. Contributions clés

1. HUBO pour la sélection de caractéristiques : La première formulation explicite de la sélection de caractéristiques comme un problème HUBO capturant directement les interactions à trois corps, évitant ainsi la perte d'information inhérente aux réductions QUBO.
2. Implémentation matérielle : Exécution réussie d'un problème d'optimisation d'ordre supérieur sur du matériel à ions piégés IonQ Forte, démontrant la faisabilité d'exécuter des circuits quantiques profonds pour le prétraitement d'apprentissage automatique.
3. Indépendance du modèle : La méthode repose uniquement sur les dépendances statistiques (Information Mutuelle) dérivées des données, ne nécessitant aucun entraînement de modèle pendant la phase de sélection.
4. Étalonnage : Comparaison complète contre des simulations quantiques sans bruit et des bases de référence classiques (SelectKBest et PCA) sur des ensembles de données réels.

4. Résultats expérimentaux

Le cadre a été testé sur deux ensembles de données : Gallstone (biomédical, 38 caractéristiques) et Spambase (textuel, 57 caractéristiques). Tous deux ont été pré-sélectionnés à 32 caractéristiques pour respecter les contraintes matérielles.

A. Ensemble de données Gallstone

• Matériel vs Simulation : Forte concordance qualitative entre IonQ Forte et la simulation sans bruit concernant les probabilités d'inclusion des caractéristiques.
• Performance : Le sous-ensemble sélectionné par le quantique (19 caractéristiques) a atteint un ROC-AUC de 0,88, surpassant :
  • Toutes les caractéristiques (0,86)
  • PCA (0,79)
  • SelectKBest (0,84)
• Insight : L'inclusion des termes d'ordre supérieur a permis au modèle d'identifier un sous-ensemble plus compact et informatif que les méthodes univariées.

B. Ensemble de données Spambase

• Performance : Le sous-ensemble sélectionné par le quantique (23 caractéristiques) a atteint un ROC-AUC de 0,9836, surpassant :
  • Toutes les caractéristiques (0,9817)
  • PCA (0,9615)
  • SelectKBest (0,9805)
• Efficacité : La méthode a réduit la dimensionalité d'environ 28 % tout en améliorant légèrement la précision de classification par rapport à l'utilisation de toutes les caractéristiques.

5. Signification et conclusion

• Au-delà du quadratique : L'étude prouve que la modélisation explicite des structures statistiques d'ordre supérieur (via des termes à 3 corps) produit de meilleurs sous-ensembles de caractéristiques que les approches quadratiques standard (QUBO), en particulier dans les ensembles de données avec des dépendances multivariées complexes.
• Adéquation matérielle : Les processeurs à ions piégés sont particulièrement adaptés aux problèmes HUBO grâce à leur connectivité tout-à-tout, ce qui élimine le besoin de surcoûts de mappage/encodage de qubits courants dans les architectures supraconductrices.
• Évolutivité : Les résultats suggèrent que, à mesure que le matériel quantique s'agrandit (plus de qubits, fidélité plus élevée), cette approche peut traiter des problèmes de sélection de caractéristiques de haute dimension qui sont computationnellement insolubles pour les méthodes combinatoires classiques.
• Travaux futurs : Les auteurs proposent d'intégrer la DCQO à champ de biais (BF-DCQO) pour mettre à jour itérativement les champs de biais, améliorant ainsi le paysage d'optimisation pour des ensembles de données plus volumineux.

En résumé, cet article démontre un flux de travail quantique pratique et agnostique au modèle qui exploite l'optimisation d'ordre supérieur sur du matériel à ions piégés pour surpasser les techniques classiques de réduction de dimensionalité tant en termes de compacité des caractéristiques que de performance prédictive.