Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

Résumé Technique : Réduction Algébrique pour l'Amélioration d'un Algorithme de Préparation d'État Quantique à Limite Optimale

Énoncé du Problème
La préparation d'état quantique (QSP - Quantum State Preparation) est un sous-routine fondamentale requise pour de nombreux algorithmes quantiques, incluant les solveurs de systèmes linéaires, la simulation de Hamiltoniens, la chimie quantique et l'apprentissage automatique. Le défi principal réside dans la minimisation de la complexité du circuit (profondeur, nombre de portes et nombre de CNOT) de l'opérateur unitaire $U$ qui transforme l'état initial $|0\rangle^{\otimes n}$ vers un état cible souhaité $|\psi\rangle = \sum c_i |i\rangle$. L'algorithme de Sun et al. (SUN) est connu pour être optimalement borné concernant le compromis espace-temps asymptotique (utilisant des qubits auxiliaires pour réduire la profondeur), mais sa mise en œuvre implique une décomposition utilisant trois opérateurs de type $\Lambda$ pour chaque porte uniformément contrôlée (UCG - Uniformly Controlled Gate). Ce document traite de l'opportunité de réduire la profondeur du circuit et le nombre de portes de l'algorithme SUN grâce à une décomposition algébrique plus efficace, particulièrement dans la plage paramétrique où le nombre de qubits auxiliaires $m$ satisfait $2^n \leq m \leq 2^n/n$.

Méthodologie
Les auteurs proposent un nouvel algorithme de QSP, nommé OSUN, qui introduit une décomposition algébrique plus simple de l'opérateur unitaire. Le changement méthodologique central consiste à séparer la préparation de l'état souhaité en deux blocs unitaires distincts :

1. Partie Réelle ($U_{mod}$) : Une unitaire responsable de la préparation des modules réels (amplitudes) des coefficients de l'état cible.
2. Partie Complexe ($D_{ph}$) : Une unitaire diagonale responsable de l'application des phases complexes nécessaires.

Dans le cadre traditionnel de SUN, chaque UCG de la structure en échelle est décomposée en trois opérateurs de type $\Lambda$ (gérant les déphasages diagonaux pour les composantes réelles et complexes séparément). L'algorithme OSUN proposé exploite le fait que $U_{mod}$ ne nécessite que la préparation d'amplitudes réelles. En restreignant les UCG de ce bloc à des matrices bloc-diagonales $R_y$ et en utilisant un changement spécifique de l'ensemble de portes ($R_y(\gamma) \equiv SH \cdot R_z(\gamma) \cdot HS^\dagger$), les auteurs démontrent que chaque UCG dans la préparation de la partie réelle peut être implémentée en utilisant un seul opérateur de type $\Lambda$ au lieu de trois. L'information de phase complexe est ensuite appliquée à la fin du circuit via un seul opérateur $\Lambda$ de dimension maximale.

Cette décomposition permet la parallélisation des opérations sur le registre auxiliaire en utilisant la même méthode de sommation dans l'espace de Fourier en 5 étapes établie dans les implémentations précédentes de SUN, mais avec un nombre réduit de constructeurs $\Lambda$ par niveau.

Contributions Clés
Le document expose six contributions spécifiques :

1. Optimisation de SUN : Un nouvel algorithme de QSP qui améliore l'algorithme SUN en termes de profondeur et de nombre de portes sur l'ensemble du premier intervalle du compromis espace-temps optimal défini par Sun et al. [40, Théorème 1].
2. Décomposition Algébrique : Une dérivation montrant que la séparation des parties réelles et complexes permet à chaque UCG d'être implémentée avec un seul constructeur de type $\Lambda$, réduisant le compte de trois à un par niveau de porte.
3. Limites Asymptotiques Plus Serrées : Une analyse formelle fournissant des limites optimales asymptotiques plus serrées pour le compromis espace-temps dans la plage paramétrique spécifiée.
4. Implémentation : La pleine implémentation de l'algorithme OSUN utilisant la bibliothèque PennyLane, disponible sur GitHub.
5. Vérification Étendue : Une batterie complète de tests exécutés sur le système HPC de l'Université de Parme, couvrant des états denses et creux, des coefficients aléatoires (réels positifs, réels négatifs, complexes) et des états physiquement pertinents (Bell, GHZ, W, Dicke) pour des nombres de qubits allant jusqu'à 10.
6. Analyse Comparative : Une comparaison directe des performances avec l'algorithme de Möttönen et al. (le standard pour la QSP sans auxiliaires) et l'implémentation originale de SUN, évaluant les métriques telles que la profondeur, le nombre total de portes, le nombre de CNOT et les types de portes.

Résultats
Les résultats de simulation indiquent que l'algorithme OSUN atteint une réduction systématique de la profondeur du circuit par rapport à l'implémentation originale de SUN.

• Analyse de Complexité : L'analyse théorique confirme que bien que la classe de complexité asymptotique reste $O(n^2 + 2^n/m)$, les préfacteurs des termes dominants sont significativement réduits. Spécifiquement, le terme logarithmique-linéaire ($n \log m$) montre une amélioration d'un facteur 3, et le terme exponentiel ($2^n/m$) montre un facteur 2 d'amélioration.
• Métriques de Simulation : Pour des états aléatoires avec des coefficients complexes, OSUN démontre une profondeur plus faible dès 6 qubits par rapport aux algorithmes SUN original et de Möttönen. La courbe de croissance de la profondeur est plus lisse que celle de la version originale.
• Nombre de Portes : Bien qu'OSUN réduise la profondeur, le nombre total de portes et de CNOT ne montre pas de réduction par rapport à l'algorithme de Möttönen. Cependant, les auteurs notent un changement dans la composition de l'ensemble de portes : l'approche de Möttönen utilise des CNOT et des rotations, tandis qu'OSUN utilise des CNOT et des déphasages (opérateurs diagonaux).
• Fidélité : L'algorithme maintient une fidélité élevée (proche de 1) et une faible distance de trace pour tous les types d'états et nombres de qubits testés (2 à 10).

Signification et Revendications
Le document affirme que la réduction algébrique proposée offre une amélioration pratique de l'état de l'art de l'algorithme SUN sans modifier sa classe de complexité asymptotique fondamentale. En réduisant les constantes de facteur dans la profondeur et le nombre de portes, OSUN fournit un circuit plus efficace pour la préparation d'état dans le régime où des qubits auxiliaires sont disponibles ($m \geq 2^n$). Les auteurs positionnent ce travail comme un raffinement du compromis espace-temps optimal, soulignant que la réduction du nombre d'opérateurs $\Lambda$ (de 3 à 1 par UCG) est le principal moteur du gain de performance.

Les auteurs déclarent explicitement que cette optimisation s'applique à l'ensemble du premier intervalle paramétrique de l'échange optimal. Ils suggèrent que les travaux futurs pourraient étendre ces avantages à d'autres points du domaine où les registres auxiliaires croissent exponentiellement. Le document conclut en notant que bien qu'OSUN améliore la profondeur, les investigations futures devraient aborder la connectivité des qubits sur le matériel réel et la traduction de ces circuits vers l'ensemble de portes Clifford+T pour évaluer pleinement leur complexité dans des contextes tolérants aux fautes. Le travail ne prétend pas résoudre le problème général de la QSP pour toutes les contraintes matérielles, mais offre une amélioration spécifique et vérifiée du cadre SUN en utilisant les stratégies auxiliaires existantes.