Optimal fermion-qubit mappings via quadratic assignment

Cet article présente deux approches computationnelles pour optimiser les mappages fermion-qubit en résolvant un problème d'affectation quadratique afin de minimiser les poids de Pauli, permettant ainsi de réduire la complexité des portes tout en limitant le nombre de qubits nécessaires pour la simulation de systèmes fermioniques.

L'essentiel

Imaginez que vous essayez de simuler le comportement de la matière à l'échelle atomique (comme des électrons qui sautent d'un atome à l'autre) sur un ordinateur quantique. C'est un peu comme essayer de traduire un livre écrit dans une langue très complexe (la physique des fermions) vers une langue que votre ordinateur comprend (les qubits).

Le problème, c'est que cette traduction est souvent très maladroite. Elle crée des phrases (des opérations mathématiques) si longues et compliquées qu'elles font planter l'ordinateur quantique actuel, qui est encore fragile et a peu de mémoire.

Voici comment les auteurs de cet article ont résolu ce casse-tête, expliqué simplement :

1. Le Problème : La "Longue Chaîne"

Prenons l'ancienne méthode de traduction, appelée Jordan-Wigner. Imaginez que vous voulez dire "l'électron A saute vers l'électron B".
Dans cette vieille méthode, pour que l'ordinateur comprenne, il doit vérifier l'état de tous les électrons situés entre A et B, comme une longue chaîne de dominos. Si vous avez 100 électrons, la phrase peut devenir longue comme un roman. Plus la phrase est longue, plus l'ordinateur fait d'erreurs.

Les chercheurs avaient deux choix jusqu'à présent :

• Option A (Économie de place) : Utiliser le moins de qubits possible (comme un petit appartement), mais accepter des phrases très longues et complexes.
• Option B (Simplicité) : Utiliser des phrases très courtes et simples, mais au prix d'avoir besoin d'une énorme quantité de qubits supplémentaires (comme un gratte-ciel).

2. La Première Solution : Le "Réarrangement Intelligent"

Les auteurs disent : "Et si on ne changeait pas la méthode, mais simplement l'ordre dans lequel on place les électrons ?"

Imaginez que vous devez organiser une grande fête. Si vous placez les gens qui doivent se parler côte à côte, les conversations sont courtes. Si vous les placez aux extrémités opposées de la salle, ils doivent crier à travers toute la pièce.

Les chercheurs ont utilisé un algorithme mathématique (appelé "Quadratic Assignment", un peu comme un super-organisateur de mariage) pour trouver l'ordre parfait des électrons.

• Le résultat : En réorganisant simplement la liste des électrons avant de commencer la traduction, ils ont réussi à raccourcir considérablement les "phrases" complexes, même sans ajouter de matériel supplémentaire. C'est comme si, en changeant juste la disposition des meubles, la maison semblait beaucoup plus grande et facile à vivre.

3. La Deuxième Solution : Les "Assistantes Magiques" (Qubits Ancilla)

Mais parfois, même avec le meilleur ordre, les phrases restent trop longues. Alors, les chercheurs ont eu une idée brillante : ajoutons quelques assistants.

Imaginez que vous avez une chaîne de dominos très longue. Au lieu de faire tomber toute la chaîne, vous ajoutez un petit assistant (un qubit supplémentaire) qui peut "tenir" l'information au milieu.

• Le truc : Ils ajoutent un petit nombre d'assistants (jusqu'à 10) qui agissent comme des "ponts" ou des "raccourcis". Ces assistants permettent d'annuler les parties inutiles de la longue phrase.
• Le résultat : Au lieu d'avoir besoin d'un gratte-ciel entier (des centaines d'assistants), ils n'ont besoin que de quelques-uns pour réduire la longueur des phrases de 67 %.

C'est comme si, au lieu de construire un pont géant sur un fleuve, vous ajoutiez juste quelques piliers stratégiques pour que le pont soit beaucoup plus court et stable.

En Résumé

Ce papier nous dit deux choses importantes pour le futur de l'informatique quantique :

1. On peut faire mieux sans dépenser plus : En réorganisant intelligemment les données (comme un bon déménageur), on réduit la complexité.
2. On peut faire mieux avec très peu de ressources : En ajoutant quelques "assistants" magiques (qubits supplémentaires), on peut rendre les calculs beaucoup plus simples, surpassant même les meilleures méthodes connues jusqu'alors.

C'est une victoire pour les ordinateurs quantiques de demain : cela signifie qu'on pourra simuler des molécules complexes et découvrir de nouveaux médicaments ou matériaux, même avec des machines qui ne sont pas encore parfaites et qui ont peu de mémoire.

Résumé technique

1. Problématique

La simulation de systèmes fermioniques (chimie quantique, physique de la matière condensée, physique des hautes énergies) sur des ordinateurs quantiques nécessite de mapper les opérateurs fermioniques sur des qubits. Ce processus, appelé mapping fermion-qubit, est crucial car la complexité de la simulation (en termes de nombre de portes et de profondeur de circuit) dépend directement de la qualité de ce mapping.

Le défi principal réside dans le compromis entre deux approches existantes :

• Mappings sans qubits auxiliaires (ancilla-free) : Comme la transformation de Jordan-Wigner (JW), Bravyi-Kitaev (BK) ou l'arbre ternaire (Ternary Tree). Ils minimisent le nombre de qubits requis (égal au nombre de modes fermioniques), mais génèrent souvent des opérateurs de Pauli non locaux (poids de Pauli élevé), ce qui augmente la complexité des portes.
• Encodages locaux (local encodings) : Comme l'encodage Bravyi-Kitaev super-rapide. Ils utilisent des qubits auxiliaires pour garantir que les termes du Hamiltonien agissent sur un nombre constant de qubits (poids de Pauli constant), mais au prix d'un nombre de qubits qui croît linéairement avec la taille du système, une ressource rare sur les dispositifs actuels (NISQ).

L'objectif de cet article est de trouver un équilibre optimal : réduire le poids de Pauli (complexité des portes) sans nécessiter une échelle linéaire de qubits auxiliaires, en exploitant l'optimisation de l'ordre des modes fermioniques et l'ajout stratégique d'un petit nombre de qubits auxiliaires.

2. Méthodologie

Les auteurs proposent deux approches computationnelles distinctes pour optimiser ces mappings :

A. Optimisation de l'ordre des modes fermioniques (Approche sans ancilla)

Cette méthode vise à minimiser le poids total et le poids maximum des opérateurs de Pauli pour un encodage linéaire donné (JW, BK, Arbre Ternaire, Parité).

• Formulation : Le problème d'ordonnancement des modes fermioniques est formulé comme un Problème d'Affectation Quadratique (QAP).
• Fonction de coût : Pour une transformation linéaire donnée définie par une matrice binaire $U$, les auteurs définissent une matrice de coût $D$ où chaque élément $D_{ij}$ représente le poids de Pauli des termes de saut (hopping) et d'interaction entre les modes $i$ et $j$.
• Optimisation : L'objectif est de trouver une permutation $\sigma$ des modes qui minimise la somme (ou le maximum) des poids de Pauli sur les arêtes du graphe du Hamiltonien.
• Algorithme : Ils utilisent des heuristiques de type "Minimum Linear Arrangement" (MLA) et des solveurs QAP pour trouver des ordonnancements optimaux ou quasi-optimaux, étendant ainsi la méthode précédente (limitée à JW) à d'autres transformations comme Bravyi-Kitaev et l'Arbre Ternaire.

B. Ajout incrémental de qubits auxiliaires (Approche hybride)

Cette méthode généralise une stratégie précédente consistant à ajouter un nombre constant de qubits auxiliaires à la transformation de Jordan-Wigner pour réduire drastiquement le poids de Pauli.

• Principe : Au lieu d'utiliser une transformation locale complexe (qui nécessite $O(n)$ ancillas), ils ajoutent itérativement un petit nombre de qubits auxiliaires (par exemple 10) à un mapping JW optimisé.
• Mécanisme : Pour chaque terme de saut, ils introduisent un opérateur de Pauli modificateur $\kappa_{ij}$ impliquant le qubit auxiliaire. L'utilisateur choisit un sous-ensemble de qubits $I$ pour appliquer une chaîne de $Z$ ($Z_I$) sur les qubits principaux.
• Optimisation QAP : Le choix du sous-ensemble de qubits $I$ pour chaque qubit auxiliaire est également formulé comme un problème d'affectation quadratique. L'objectif est de minimiser l'augmentation du poids de Pauli tout en annulant les chaînes de $Z$ non locales présentes dans le mapping JW original.
• Théorie : La validité de cette modification repose sur le théorème assurant que le nouveau Hamiltonien sur $n+k$ qubits est unitairement équivalent au Hamiltonien fermionique original, à condition de préserver les relations de commutation et d'anti-commutation (via l'utilisation de qubits stabilisés).

3. Contributions Clés

1. Extension de l'optimisation d'ordre : Les auteurs ont généralisé l'optimisation de l'ordre des modes fermioniques (via QAP) au-delà de la transformation de Jordan-Wigner, l'appliquant avec succès aux transformations Bravyi-Kitaev, Arbre Ternaire et Base de Parité.
2. Stratégie d'ajout incrémental d'ancillas : Ils ont développé un protocole général pour ajouter un nombre arbitraire de qubits auxiliaires à la transformation de Jordan-Wigner, transformant ce problème en un QAP pour trouver les configurations optimales de chaînes de $Z$.
3. Établissement d'un nouveau standard : Ils démontrent qu'avec un nombre très faible de qubits auxiliaires (constant, par exemple 10), on peut surpasser les meilleures transformations sans ancilla (comme l'Arbre Ternaire) en termes de poids de Pauli total.

4. Résultats Expérimentaux

Les expériences ont été menées sur des systèmes allant jusqu'à 225 modes fermioniques (grilles carrées) et divers graphes de 64 modes (réseaux hexagonaux, triangulaires, cycles, graphes aléatoires).

• Comparaison des encodages sans ancilla :

  • Pour les petites grilles, Jordan-Wigner optimisé est compétitif.
  • Pour les grandes grilles, la transformation Arbre Ternaire (Ternary Tree) optimisée devient supérieure à Jordan-Wigner et Bravyi-Kitaev en termes de poids total et maximum de Pauli.
  • L'optimisation de l'ordre a permis de retrouver les ordonnancements optimaux connus (ex: Mitchison-Durbin) pour les grilles carrées.

• Impact de l'ajout de qubits auxiliaires (JW + Ancillas) :

  • Sur une grille $8 \times 8$, l'ajout de 10 qubits auxiliaires à la transformation Jordan-Wigner a réduit le poids total de Pauli des termes de saut de 39,3 % par rapport à la version sans ancilla.
  • Sur divers graphes de 64 modes, l'ajout de 10 ancillas a permis de réduire le poids de Pauli de jusqu'à 67 %.
  • Performance : Avec 10 ancillas, le mapping Jordan-Wigner modifié a surpassé la transformation Arbre Ternaire (qui est sans ancilla et considérée comme l'état de l'art pour les mappings sans ressources supplémentaires) sur la plupart des graphes testés. Par exemple, sur un réseau hexagonal périodique, le poids est passé de 7800 (JW standard) à 3487 (JW + 10 ancillas), contre 3429 pour l'Arbre Ternaire.

5. Signification et Conclusion

Cet article démontre qu'il existe une marge de manœuvre significative pour améliorer la simulation fermionique sur les ordinateurs quantiques à court et moyen terme (NISQ).

• Économie de ressources : La méthode proposée permet d'obtenir des Hamiltoniens de qubits à faible poids de Pauli (donc moins coûteux en portes) en n'utilisant qu'un nombre constant et faible de qubits auxiliaires, évitant ainsi le coût prohibitif des encodages locaux complets qui nécessitent $O(n)$ ancillas.
• Flexibilité : En traitant le problème comme un QAP, la méthode s'applique à n'importe quel modèle d'interaction (pas seulement les grilles carrées) et à divers types de transformations.
• Impact pratique : Pour les algorithmes comme VQE (Variational Quantum Eigensolver) ou la simulation de Trotter, la réduction du poids de Pauli se traduit directement par une réduction du nombre de mesures nécessaires et de la profondeur des circuits, augmentant ainsi la fidélité des résultats sur le matériel actuel.

En résumé, les auteurs proposent une voie pragmatique pour contourner les limitations des qubits actuels : optimiser l'ordre des modes et ajouter judicieusement quelques qubits auxiliaires pour obtenir des mappings quasi-optimaux, surpassant les solutions purement sans ancilla.