A Quantum Algorithm with Polylogarithmic Depth per Trotter Step for the Extended Hubbard Model

Résumé Technique : Q2FMM pour le modèle de Hubbard étendu

Énoncé du Problème
La simulation du modèle de Fermi-Hubbard étendu sur un réseau bidimensionnel est un défi central en informatique quantique, particulièrement pour la physique de la matière condensée et les structures électroniques fortement corrélées. Bien que les termes locaux (sauts et interactions sur site) puissent être simulés efficacement avec des circuits à profondeur constante ou faible, l'inclusion d'interactions de Coulomb à longue portée présente un goulot d'étranglement significatif. Ces interactions génèrent des termes en $O(N^2)$ (où $N$ est le nombre de sites du réseau), entraînant des circuits quantiques profonds. Les approches standards, telles que les réseaux de SWAP fermioniques, résultent en une profondeur de circuit par étape de Trotter évoluant en $O(N)$. Les stratégies de troncature sont souvent inefficaces pour les potentiels de Coulomb en raison de leur décroissance lente en $1/r$, ce qui nécessite des rayons de coupure importants pour maintenir la précision.

Méthodologie : L'algorithme Q2FMM
Les auteurs proposent Q2FMM, un algorithme quantique inspiré de la méthode classique Fast Multipole Method (FMM) pour simuler l'évolution temporelle du modèle de Hubbard étendu au sein de la formule de produit de Trotter. La méthodologie centrale consiste à remplacer les interactions directes site à site par des interactions entre des « boîtes » hiérarchiques et de grain grossier à travers plusieurs échelles de longueur.

1. Structure Hiérarchique : L'algorithme organise le réseau 2D en une structure de quadtree. Il distingue les interactions de « champ proche » (traitées directement au niveau le plus fin) et les interactions de « champ lointain » (approximées via des expansions multipolaires).
2. Expansions Multipolaires :
   • Q2FMM d'ordre 0 : Utilise une approximation simplifiée où les boîtes distantes interagissent en fonction de leurs nombres d'occupation totaux ($N_A N_B$).
   • Q2FMM d'ordre supérieur : Affine la précision en conservant les coefficients multipolaires ($M_{\ell m}$) plutôt que de simples nombres d'occupation totaux. Cela permet un compromis systématique entre précision et coût computationnel via un ordre de troncature $p$.
3. Conception du Circuit Quantique :
   • Phase de Calcul : L'algorithme procède du niveau le plus fin (sites individuels) vers le niveau le plus grossier. À chaque niveau, il agrège les informations des boîtes enfants vers les boîtes parentes en utilisant des additionneurs quantiques. Pour les versions d'ordre supérieur, cela implique la translation et la sommation des coefficients multipolaires.
   • Application de la Phase : L'énergie d'interaction pour les paires de boîtes est calculée à l'aide de multiplicateurs quantiques pour calculer les produits de nombres d'occupation ou de termes multipolaires. La phase résultante est appliquée via des portes de phase à un qubit.
   • Phase de Décalcul (Uncompute) : Pour éviter l'accumulation d'états résiduels (« garbage states ») et l'intrication indésirable, l'algorithme emploie une phase de « décalcul » réversible. Il inverse les étapes d'agrégation (décomposant l'information parente de nouveau en information enfant) après que la phase a été imprimée, garantissant que le système revienne à un état propre tout en préservant la phase dynamique.
4. Optimisations : Le papier discute d'optimisations optionnelles utilisant des opérations COPY (CNOT transversaux) pour paralléliser les calculs de phase et des portes de fan-out non bornées pour réduire la profondeur des circuits arithmétiques à $O(\log^* n)$, bien que l'analyse de complexité principale repose sur des circuits réversibles standards.

Résultats Clés et Complexité
Le circuit quantique résultant atteint les propriétés de mise à l'échelle suivantes par étape de Trotter et pour un temps de simulation total $t$ avec une erreur cible $\epsilon$ :

• Profondeur du Circuit : La profondeur par étape de Trotter évolue de manière polylogarithmique avec la taille du système $N$. Plus précisément, elle évolue en $O(\log N \cdot \log Q)$, où $Q$ est le nombre d'électrons.
• Complexité de Porte : La complexité de porte par étape de Trotter évolue de manière quasi-linéaire avec la taille du système, notée $\tilde{O}(N)$.
• Complexité Totale : En tenant compte du nombre d'étapes de Trotter nécessaires pour simuler le temps $t$ avec une erreur $\epsilon$, la profondeur totale du circuit évolue en $\tilde{O}(N^{1/2} t^{3/2} / \epsilon^{1/2})$, et la complexité totale des portes évolue en $\tilde{O}(N^{3/2} t^{3/2} / \epsilon^{1/2})$.
• Qubits Ancilla : L'algorithme nécessite un nombre de qubits ancilla qui évolue de manière quasi-linéaire avec la taille du système, $\tilde{O}(N)$.

Signification et Revendications
Le papier affirme que Q2FMM offre un avantage significatif par rapport aux méthodes existantes pour simuler les interactions à longue portée dans de grands systèmes.

• Comparaison avec l'Image d'Interaction : Les auteurs comparent Q2FMM à la méthode de l'image d'interaction (Low et Wiebe, Réf. [82]), qui possède une complexité de porte de $\tilde{O}(N^2 t)$. Q2FMM devient avantageux dans le régime des grands systèmes (grand $N$), tandis que la méthode de l'image d'interaction est plus favorable pour les simulations de longue durée et de haute précision (grand $t$, petit $\epsilon$). Le point de croisement est estimé à $N \sim \tilde{O}(t/\epsilon)$.
• Adaptabilité au Matériel : Les auteurs suggèrent que Q2FMM est particulièrement adapté aux ordinateurs quantiques à atomes neutres en deux dimensions, qui supportent nativement le déplacement d'atomes (shuttling) et les portes d'intrication à longue portée. Il est également compatible avec les architectures de code de surface où les opérations à longue portée peuvent être réalisées en profondeur constante.
• Généralité : Bien que démontré sur le modèle de Hubbard étendu, le cadre est présenté comme applicable à d'autres noyaux (ex: Yukawa, Helmholtz) et potentiellement à des hamiltoniens moléculaires ab initio discrétisés sur des grilles d'espace réel.

Distinction par rapport aux Travaux Connexes
Les auteurs distinguent Q2FMM des approches récentes basées sur la FMM pour les hamiltoniens moléculaires (ex: Berry et al., Réf. [80]). Dans ces travaux, l'état quantique est en première quantification, nécessitant un tri complexe des électrons dans des boîtes spatiales basées sur des données de position quantiques. En revanche, Q2FMM opère sur un réseau où les qubits sont pré-disposés par position spatiale (seconde quantification), éliminant ainsi le besoin de mouvement de données quantiques basé sur la position. Par conséquent, Q2FMM se concentre sur la réutilisation hiérarchique efficace des résultats intermédiaires et la gestion des états résiduels par le décalcul.