Résumé technique : AQKA : Acquisition active de noyau quantique sous contrainte de tir

1. Énoncé du problème

Les méthodes de noyau quantique, qui transforment des entrées classiques en un espace de caractéristiques quantique pour calculer des fidélités $K(x_i, x_j) = |\langle \phi(x_j)|\phi(x_i)\rangle|^2$, figurent parmi les charges de travail les plus accessibles pour le matériel quantique à échelle intermédiaire bruyant (NISQ). Cependant, leur déploiement pratique est entravé par les coûts de mesure. L'estimation d'une matrice de noyau $N \times N$ nécessite $\Theta(N^2 S)$ exécutions de circuits (tirs), où $S$ est le nombre de tirs par entrée pour atteindre une précision souhaitée. Sur le matériel actuel, où les latences de circuit varient de quelques millisecondes à plusieurs secondes, cette mise à l'échelle limite la taille des problèmes déployables à quelques centaines.

Les stratégies existantes d'économie de budget (par exemple, Nyström-QKE, ShoFaR, alignement noyau-cible) y répondent en sous-échantillonnant quelles entrées mesurer (par exemple, en sélectionnant des colonnes repères ou des points d'entraînement). Cependant, ces méthodes allouent généralement le budget de tirs de manière uniforme au sein des sous-ensembles choisis. Elles ne tiennent pas compte de l'hétérogénéité de la contribution de chaque entrée de noyau spécifique à la performance du classifieur en aval. La question centrale sans réponse est la suivante : étant donné un budget de tirs fixe $B$, comment les tirs doivent-ils être alloués au niveau des paires pour minimiser la perte de la tâche en aval ?

2. Méthodologie : AQKA

Les auteurs formulent l'apprentissage de noyau quantique sous contrainte de budget de tirs comme un problème d'optimisation visant à minimiser la perte attendue $\mathbb{E}[L(\hat{K})]$ sous la contrainte d'un budget total de tirs $\sum s_{ij} \leq B$.

Déduction théorique

En utilisant une analyse du premier ordre (méthode Delta) combinée aux conditions Karush-Kuhn-Tucker (KKT), les auteurs dérivent une règle d'allocation optimale sous forme fermée. Pour une entrée de noyau $K_{ij}$ estimée avec $s_{ij}$ tirs, la variance est $K_{ij}(1-K_{ij})/s_{ij}$. L'allocation optimale $s^*_{ij}$ qui minimise la variance de l'estimateur de perte est proportionnelle à la sensibilité de la perte à cette entrée :
$$s^*_{ij} \propto |g_{ij}| \sqrt{K_{ij}(1-K_{ij})}$$
où $g_{ij} = \partial L / \partial K_{ij}$ est le gradient de la perte par rapport à l'entrée du noyau.

• Pour la régression Ridge à noyau (KRR) : Le gradient est dérivé explicitement comme $g_{ij} = -2\lambda^2(\beta_i \alpha_j + \beta_j \alpha_i)$, où $\alpha = (K+\lambda I)^{-1}y$ et $\beta = (K+\lambda I)^{-1}\alpha$.
• Pour les machines à vecteurs de support (SVM) : En utilisant le théorème de l'enveloppe (théorème de Danskin), le gradient est dérivé comme $g_{ij} = -y_i y_j \eta^*_i \eta^*_j$, où $\eta^*$ sont les variables duales optimales.

Implémentation algorithmique

Les auteurs proposent AQKA (Active Quantum Kernel Acquisition), un algorithme déployable fonctionnant par cycles :

1. Échauffement : Une petite fraction du budget ($\eta_w B$) est dépensée uniformément pour amorcer une estimation initiale du noyau $\hat{K}$.
2. Estimation de la sensibilité : L'algorithme résout le problème KRR (ou SVM) sur $\hat{K}$ pour calculer les scores de sensibilité basés sur le gradient $g_{ij}$.
3. Allocation de remplissage ciblé : Au lieu d'échantillonner des tirs à partir d'une distribution multinomiale (qui peut affamer les paires de faible sensibilité en raison de pics stochastiques), AQKA utilise une approche déterministe de « remplissage ciblé ». Il calcule le nombre de tirs cible $s^*_{ij}$ et ajoute la différence $\max(0, s^*_{ij} - s_{ij})$ à chaque paire.
4. Exploration : Une petite fraction d'exploration ($\eta_e B$) est ajoutée uniformément pour empêcher l'algorithme d'ignorer complètement les paires qui pourraient devenir importantes en raison d'effets d'ordre supérieur ou de bruit d'estimation.

3. Contributions clés

1. Décomposition complète du régime

L'article fournit une caractérisation fondée sur des principes de la période où différentes stratégies d'allocation sont optimales :

• AQKA domine dans le régime limité par le budget ($B \lesssim 16 n_{pairs}$) sur des tâches KRR à sensibilité clairsemée.
• Nyström-QKE (reconstruction de rang faible) l'emporte aux budgets saturants sur des données plantées clairsemées, où la structure de rang faible peut être entièrement récupérée.
• Les méthodes de type ShoFaR ne sont compétitives que dans les régimes de budget extrêmement faible.

2. Théorie d'acquisition au niveau des paires sous forme fermée

• Allocation optimale KKT : Dérivation du gradient $g_{ij}$ sous forme fermée pour KRR et SVM sous bruit de tir.
• Bornes corrigées conscientes de la parcimonie : Les auteurs dérivent une borne de Cauchy-Schwarz pour le rapport de réduction de variance réalisable $\rho$. Ils corrigent l'échelle naïve $\Theta(m^2/N^2)$ (en supposant que $g$ est supportée sur $S \times S$) vers une échelle plus précise $\Theta(m/N)$ ($\rho \leq 2m/N$ pour KRR). Cela reflète le fait structurel que même si le vecteur de solution $\alpha$ est clairsemé, le vecteur de sensibilité $\beta = (K+\lambda I)^{-1}\alpha$ est génériquement dense, ce qui signifie que toute paire touchant l'ensemble de support a une sensibilité non nulle.
• Bornes de regret : Une borne de regret de type plug-in à constante explicite est fournie, montrant que l'erreur converge vers l'optimum oracle à mesure que le budget d'échauffement augmente.

3. Algorithme de remplissage ciblé déployable

L'article démontre qu'un schéma déterministe de remplissage ciblé surpasse l'échantillonnage multinomial naturel, en particulier dans le régime limité par le budget. L'échantillonnage multinomial a tendance à se concentrer agressivement sur quelques paires à haut score, affamant les autres et amplifiant le bruit dans l'inversion de matrice ; le remplissage ciblé maintient un plancher de couverture minimale.

4. Première adaptation en ligne multi-graines sur matériel quantique

Les auteurs rapportent la première démonstration publiée d'allocation adaptative de tirs en ligne sur les dispositifs actuels de classe IBM Heron à 156 qubits.

• IBM Aachen (N=20) : +17,0 ± 4,8 points de pourcentage par rapport à l'allocation uniforme (significativité de 3,5$\sigma$).
• IBM Berlin (N=30) : +14,0 ± 8,5 points de pourcentage à des budgets plus élevés.

4. Résultats expérimentaux

Paramètres synthétiques et simulés

• KRR clairsemée plantée : Sur des données synthétiques avec des vecteurs de solution clairsemés, AQKA (remplissage ciblé avec sensibilité estimée) réalise +8 à +25 points de pourcentage par rapport à l'allocation uniforme lorsque $N$ passe de 225 à 1000.
• Noyaux quantiques sans bruit : Les gains se transfèrent aux simulations de cartes de caractéristiques ZZ à 4 qubits sans bruit, montrant +13 à +18 points par rapport à l'uniforme.
• Ablation par rééchantillonnage matériel : En utilisant un noyau mesuré sur IBM Pittsburgh (156 qubits) et en rééchantillonnant avec un bruit de tir, AQKA réalise +26,3 ± 6,1 points à $B = n_{pairs}$ et +31,9 ± 7,2 points à $B = 4n_{pairs}$ par rapport à l'uniforme.

Références sur données réelles

• Cancer du sein ($\alpha$ dense) : Sur un jeu de données réel où le vecteur de solution est dense (non clairsemé), AQKA ne domine pas uniformément. Il est compétitif mais montre une performance dépendante du régime, soulignant que l'avantage de la méthode repose sur une forte hétérogénéité de sensibilité au niveau des paires.
• SVM vs KRR : L'article note que, bien que le cadre théorique s'étende aux SVM, la version plug-in est plus fragile en raison de l'instabilité de l'ensemble de support sous des échauffements bruyants. Dans les régimes de petit N et d'échauffement bruyant, AQKA pour SVM peut sous-performer par rapport à l'allocation uniforme, tandis que la version KRR reste robuste.

5. Importance et revendications

L'article prétend combler l'écart entre l'optimisation théorique du budget de tirs et le déploiement pratique sur du matériel NISQ. Son importance principale réside dans :

1. Dépasser l'allocation uniforme : Démontrer que l'allocation de tirs non uniforme et consciente de la sensibilité est cruciale pour l'apprentissage de noyau quantique à court terme, en particulier lorsque les budgets sont serrés.
2. Validation matérielle : Fournir la première validation en ligne multi-graines d'une stratégie d'allocation adaptative de tirs sur du matériel quantique réel, prouvant que les gains théoriques survivent au bruit du dispositif et à la dérive de calibration.
3. Conscience du régime : Établir qu'aucune méthode unique n'est universellement supérieure ; AQKA est spécifiquement conçu pour le régime limité par le budget et à sensibilité clairsemée, qui est la zone opérationnellement pertinente pour le matériel actuel.

Les auteurs sont modestes dans leurs revendications, reconnaissant que pour des problèmes à sensibilité dense ou des budgets saturants, d'autres méthodes (comme Nyström) ou l'allocation uniforme peuvent être préférables. Ils identifient également le bruit du plug-in SVM comme une limitation actuelle nécessitant un travail futur (par exemple, acquisition stabilisée par la marge).