Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

Cet article propose un cadre de combinaison linéaire d'unitaires (LCU) basé sur la transformée de Fourier et sans ancilla, qui décompose efficacement des circuits quantiques complexes pour des tâches d'optimisation en échangeant la complexité du circuit contre une surcharge d'échantillonnage polynomiale, permettant ainsi des implémentations compatibles avec le matériel d'algorithmes tels que QAOA sur des dispositifs quantiques à court terme tout en maintenant des garanties de performance rigoureuses.

L'essentiel

Imaginez que vous essayez de résoudre un puzzle massif et incroyablement complexe. Dans le monde de l'informatique quantique, ce puzzle est souvent un problème d'optimisation : trouver la meilleure disposition possible de choses (comme l'itinéraire de livraison le plus efficace ou le meilleur portefeuille d'investissement).

L'article de Carrera Vazquez, Egger et Woerner introduit une nouvelle méthode astucieuse pour relever ces défis en utilisant un ordinateur quantique, spécifiquement l'un qui en est encore aux premiers stades de développement, dits « bruyants ».

Voici la décomposition de leur idée à l'aide d'analogies simples :

Le Problème : Le Circuit « Tous les Bras sur le Pont »

Traditionnellement, pour résoudre ces puzzles sur un ordinateur quantique, vous devez construire une machine spécifique (un circuit quantique) où chaque pièce unique du puzzle communique avec toutes les autres simultanément.

• L'Analogie : Imaginez essayer d'organiser une fête où 100 invités doivent tous se serrer la main avec chaque autre invité exactement au même moment. Dans une vraie pièce, c'est impossible ; les gens se bousculeraient, la pièce serait trop bondée et l'événement échouerait.
• La Réalité Quantique : En termes quantiques, cela nécessite une « connectivité tous-à-tous » et des circuits très profonds et complexes. Les ordinateurs quantiques actuels sont comme de petites pièces ; ils ne peuvent pas gérer autant de poignées de main simultanées sans commettre d'erreurs (bruit).

La Solution : L'Approche « Livre de Recettes » (LCU)

Les auteurs proposent une nouvelle stratégie appelée Combinaison Linéaire d'Opérateurs Unitaires (LCU). Au lieu d'essayer de construire la machine « tous les bras » impossible, ils décomposent la tâche complexe en une liste de tâches beaucoup plus simples et plus petites.

• L'Analogie : Au lieu d'essayer de cuire un seul gâteau de mariage géant et complexe (qui pourrait s'effondrer), vous cuisez 100 petits cupcakes simples.
  • Certains cupcakes sont à la vanille, d'autres au chocolat, certains ont des perles de sucre.
  • Vous n'avez pas besoin d'un four géant ; vous pouvez les cuire un par un ou par petites fournées.
  • Ensuite, vous mélangez les résultats sur une assiette. Si vous les mélangez dans les bonnes proportions, la « saveur » de l'assiette a exactement le goût du gâteau de mariage géant que vous vouliez.

Dans l'article, ces « cupcakes » sont de simples circuits quantiques qui ne nécessitent que des portes à un seul qubit (une personne serrant la main d'une autre personne). Le « mélange » se fait classiquement (sur un ordinateur ordinaire) une fois la partie quantique terminée.

Le Secret : La Transformée de Fourier

Comment savent-ils quels cupcakes cuire et combien en mélanger ? Ils utilisent un outil mathématique appelé la Transformée de Fourier.

• L'Analogie : Imaginez une chanson complexe. Une transformée de Fourier décompose cette chanson en notes individuelles (fréquences). Les auteurs l'utilisent pour décomposer une « chanson » quantique complexe (le circuit) en une série de notes simples et répétitives (rotations à un seul qubit).
• Le Résultat : Ils peuvent exprimer une opération quantique très difficile et complexe comme une somme pondérée d'opérations très simples.

Le Compromis : Qualité contre Quantité

Il y a un piège. Puisque vous ne construisez pas directement la machine géante, vous devez répéter l'expérience « cupcake » beaucoup plus souvent pour obtenir une réponse fiable.

• L'Analogie : Si vous voulez connaître la taille moyenne d'une foule, vous pourriez mesurer tout le monde une fois (difficile à faire s'ils bougent tous). Ou alors, vous pourriez mesurer 10 personnes au hasard, puis 10 autres, puis 10 autres encore, et prendre la moyenne. Vous obtenez le même résultat, mais vous devez effectuer plus de mesures.
• L'Affirmation de l'Article : Les auteurs montrent que bien que vous deviez exécuter les circuits simples plus souvent (une « surcharge d'échantillonnage »), le nombre de runs supplémentaires est gérable (polynomial), et non impossible. Ce compromis leur permet d'exécuter des problèmes sur le matériel actuel qui seraient autrement impossibles.

Application Réelle : Le « Sous-graphe le Plus Dense »

Pour prouver que cela fonctionne, ils l'ont testé sur un problème spécifique appelé « Sous-graphe k le plus dense » (trouver le groupe d'amis le plus soudé dans un immense réseau social).

1. À Petite Échelle : Ils l'ont simulé sur un graphe de 12 nœuds (comme un petit quartier) pour montrer que les mathématiques fonctionnent parfaitement.
2. À Grande Échelle : Ils l'ont exécuté sur un véritable ordinateur quantique IBM avec 106 qubits (un grand quartier).
   • Ils ont trouvé avec succès des solutions de haute qualité.
   • Ils ont comparé deux méthodes : l'une utilisant une « pénalité » (comme une amende pour avoir enfreint les règles) et l'autre utilisant un « mélangeur » spécial (une danse respectueuse des règles).
   • La Découverte : L'approche « mélangeur », combinée à leur nouvelle méthode de Fourier, a fonctionné exceptionnellement bien, trouvant des solutions presque aussi bonnes que le meilleur théorique, même sur du matériel réel et bruyant.

L'Astuce « Sans Aide »

Habituellement, pour mélanger ces « cupcakes » ensemble, vous avez besoin d'un qubit supplémentaire (un « ancilla ») pour suivre les mathématiques.

• L'Innovation : Les auteurs ont développé une méthode pour le faire sans l'aide.
• L'Analogie : Au lieu d'avoir besoin d'un arbitre pour vous dire quelle équipe a marqué, vous laissez simplement les joueurs jouer au hasard, puis vous regardez le tableau d'affichage après coup pour déterminer le vainqueur. Cela élimine une énorme quantité de complexité du circuit quantique, le rendant beaucoup plus convivial pour les machines d'aujourd'hui.

Résumé

Cet article présente une nouvelle façon d'exécuter des algorithmes d'optimisation quantique complexes sur le matériel imparfait d'aujourd'hui. Au lieu d'essayer de construire une machine massive et fragile qui connecte tout à tout, ils décomposent le problème en de nombreuses petites pièces simples, exécutent ces pièces et combinent les résultats classiquement.

Ils ont prouvé que cela fonctionne en résolvant un problème de graphe difficile sur un ordinateur quantique de 106 qubits, montrant que nous pouvons résoudre des problèmes plus grands et plus complexes aujourd'hui en échangeant la « complexité du circuit » (la difficulté de construire la machine) contre une « surcharge d'échantillonnage » (le nombre de fois où nous devons exécuter le test).

Résumé technique

Résumé Technique : Combinaison Linéaire de Unitaires Basée sur la Transformée de Fourier et Applications en Optimisation Quantique

Énoncé du Problème
Les algorithmes d'optimisation quantique, en particulier l'Algorithme d'Optimisation Approximative Quantique (QAOA), font face à des obstacles d'implémentation majeurs sur le matériel à court terme. La structure mathématique des problèmes d'optimisation, en particulier ceux impliquant des contraintes (par exemple, des contraintes de cardinalité), nécessite souvent des circuits quantiques à haute connectivité (interactions toutes-à-toutes), à grande profondeur de circuit et comportant de nombreuses portes à deux qubits. Ces exigences dépassent fréquemment les capacités des processeurs quantiques supraconducteurs actuels. Bien que des stratégies telles que la découpe de circuits ou l'approximation de circuits existent, elles sacrifient souvent la qualité de la solution à la complexité ou nécessitent une surcharge d'échantillonnage substantielle sans garanties de performance rigoureuses.

Méthodologie
Les auteurs proposent un cadre de Combinaison Linéaire de Unitaires (LCU) basé sur la Transformée de Fourier conçu pour approximer des circuits quantiques complexes à l'aide d'ensembles de circuits plus simples et compatibles avec le matériel. La méthodologie centrale comprend :

1. LCU sans qubit auxiliaire pour l'échantillonnage : Contrairement aux implémentations LCU standard qui utilisent un qubit auxiliaire pour implémenter de manière cohérente une combinaison linéaire d'unitaires (nécessitant des opérations contrôlées), ce travail se concentre sur des applications basées sur l'échantillonnage. En supprimant les facteurs de signe associés à la décomposition de quasi-probabilité (QPD) et en remplaçant l'auxiliaire par une randomisation classique, la méthode élimine le besoin de qubits auxiliaires et de portes contrôlées. Cela transforme l'implémentation en un mélange probabiliste de circuits plus simples, où la surcharge d'échantillonnage est quantifiée par un facteur $\Gamma$.
2. Décomposition de Fourier pour les Unitaires Diagonaux : Pour les unitaires diagonaux (courants dans les fonctions de coût et les termes de pénalité), les auteurs utilisent la transformée de Fourier discrète. Une unitaire cible $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ est décomposée en une combinaison linéaire d'unitaires plus simples $V(\theta_j)$, qui sont souvent de simples couches de portes $R_Z$ à un qubit. Les coefficients sont dérivés de la transformée de Fourier de la fonction définissant l'unitaire. Cette approche remplace les interactions complexes à plusieurs qubits (par exemple, des pénalités quadratiques nécessitant $O(n^2)$ portes) par des couches à un qubit, au prix d'une surcharge d'échantillonnage $\Gamma \le m+1$.
3. Extension aux Unitaires Non-Diagonaux Invariants par Permutation : Le cadre est généralisé aux unitaires non-diagonaux, tels que le mélangeur XY entièrement connecté utilisé pour préserver les contraintes de poids de Hamming. En s'appuyant sur la dualité de Schur-Weyl et la théorie des représentations de $SU(2)$, les auteurs expriment les unitaires invariants par permutation comme des combinaisons linéaires continues de rotations collectives à un qubit $R(g)^{\otimes n}$. Cela permet l'implémentation de mélangeurs hautement non locaux en utilisant uniquement des portes à un qubit, avec une surcharge d'échantillonnage théorique bornée par $O(n^3)$.
4. Lien avec la Relâchement Lagrangien : L'article établit un lien formel entre les pénalités quantiques basées sur la Fourier et le relâchement lagrangien classique. L'optimisation d'une seule branche de la décomposition LCU s'avère équivalente à l'optimisation d'un paramètre lagrangien, offrant une perspective unifiée sur la gestion des contraintes.

Contributions Clés

• Développement du Cadre : Introduction d'un cadre LCU sans qubit auxiliaire et basé sur la Fourier, qui décompose de larges classes d'unitaires diagonaux et non-diagonaux en ensembles de couches de portes à un qubit.
• Efficacité Matérielle : Démonstration que des opérateurs complexes et connectés toutes-à-toutes (comme les pénalités de cardinalité et les mélangeurs XY) peuvent être remplacés par des circuits nettement plus simples, échangeant la profondeur et la connectivité du circuit contre une surcharge d'échantillonnage polynomiale.
• Garanties Théoriques : Fourniture de bornes de performance rigoureuses, montrant que la probabilité d'échantillonner des chaînes de bits de haute qualité dans l'approche LCU est minorée par la probabilité cohérente mise à l'échelle par $1/\Gamma$. L'article relie également l'optimisation de la Valeur à Risque Conditionnelle (CVaR) à ces bornes.
• Validation de l'Évolutivité : Application réussie du cadre au problème du sous-graphe le plus dense sur des instances allant jusqu'à 106 qubits sur du matériel IBM Quantum réel, une échelle précédemment inabordable pour les implémentations entièrement cohérentes de telles contraintes.

Résultats Expérimentaux
Les auteurs ont validé leur approche par des simulations exactes de vecteurs d'état sur une instance de 12 nœuds et des expériences à grande échelle sur un dispositif de 106 qubits :

• Simulation 12 Nœuds : Les comparaisons entre le QAOA entièrement cohérent et l'approche LCU basée sur la Fourier ont montré que, bien que les valeurs moyennes brutes des circuits LCU soient plus faibles (en raison de la surcharge d'échantillonnage), l'optimisation d'un seul circuit de base LCU (un ansatz variationnel dérivé du LCU) a produit la probabilité la plus élevée d'échantillonner des solutions optimales, surpassant la base cohérente sur des métriques spécifiques.
• Expérience Matérielle 106 Nœuds : Sur un graphe heavy-hex de 106 qubits (étendu via des couches SWAP), les approches LCU basées sur la pénalité et sur le mélangeur XY ont été exécutées. Les résultats ont démontré que la surcharge d'échantillonnage pratique était nettement inférieure aux bornes théoriques du pire cas ($\Gamma \approx 10^4$). L'ansatz LCU à branche unique a trouvé avec succès des solutions de haute qualité (jusqu'à 81 arêtes dans le sous-graphe le plus dense) avec des probabilités réalisables allant de 2,7 % à 4,8 %, indiquant la viabilité de la méthode pour des problèmes à grande échelle.
• Mélangeur XY vs Pénalité : L'approche LCU basée sur le mélangeur XY a généralement surpassé l'approche basée sur la pénalité, en particulier lors de l'utilisation d'un seul circuit de base optimisé, suggérant que les mélangeurs préservant les contraintes sont plus efficaces lorsqu'ils sont combinés avec cette décomposition.

Signification et Revendications
L'article revendique que le cadre LCU basé sur la Fourier offre une voie systématique pour étendre la portée pratique de l'optimisation quantique à court terme. En remplaçant les opérations cohérentes complexes par des combinaisons pondérées de circuits plus simples, la méthode élargit la gamme d'instances de problèmes (en particulier celles avec des contraintes globales) qui peuvent être exécutées sur le matériel actuel. Les auteurs soulignent que cette approche ne nécessite pas la reproduction exacte de la distribution cible mais se concentre plutôt sur l'échantillonnage de solutions de haute qualité, un objectif bien adapté aux tâches d'optimisation. Le travail suggère que le compromis entre la complexité du circuit et la surcharge d'échantillonnage est favorable, car les bornes théoriques sont souvent lâches en pratique, et la méthode permet l'étude d'algorithmes et d'instances de problèmes qui seraient autrement au-delà des capacités matérielles. L'article conclut que cela fournit un principe de conception flexible pour des algorithmes quantiques plus compatibles avec le matériel, en particulier pour la gestion des contraintes dans le QAOA.