Sparse quantum state preparation with improved Toffoli cost

Résumé Technique : Préparation d'États Quantiques Creux avec un Coût de Toffoli Amélioré

Énoncé du Problème
La préparation d'états quantiques est un primitif fondamental en informatique quantique, essentiel pour des applications allant des solveurs de systèmes linéaires et l'apprentissage automatique quantique à la simulation quantique. Alors que la préparation d'états génériques a été largement étudiée, les états quantiques creux (ou sparse) — des états sur $n$ qubits ne contenant que $s \ll 2^n$ états de base computationnelle non nuls — nécessitent des algorithmes spécialisés et efficaces.

Dans l'informatique quantique tolérante aux fautes, la métrique de ressource principale est souvent le nombre de portes Toffoli (et de portes T), car ces opérations non-Clifford sont nettement plus coûteuses à implémenter que les portes Clifford en raison de la surcharge de la distillation d'états magiques. Les approches existantes pour la préparation d'états creux tombent généralement dans deux catégories :

1. Construction itérative : Construire l'état en $s$ étapes, chacune préparant un seul état de base. Cela engendre généralement un coût de Toffoli supérieur à $s \lceil \log(s) \rceil$.
2. Approche en deux étapes (Préparation Dense + Isométrie) : Préparer d'abord un état dense sur un sous-registre de $\lceil \log(s) \rceil$ qubits, puis mapper cet état vers l'état creux cible via une isométrie. La préparation dense (via des algorithmes comme Grover-Rudolph) est déjà bien optimisée, mais l'étape d'isométrie a historiquement été le goulot d'étranglement. L'état de l'art, tel que la méthode de Malvetti et al., nécessite un coût de Toffoli dans le pire des cas de $s(\lceil \log(s) \rceil - 1)$ pour l'isométrie, ce qui domine le coût total de l'algorithme.

Méthodologie
Les auteurs proposent un cadre raffiné en deux étapes (illustré par la Figure 1) qui optimise l'étape d'isométrie et l'intègre à la préparation d'états denses :

1. Construction d'Isométrie par Lots (Batched Isometry) :
   L'innovation centrale est un nouvel algorithme classique pour construire le circuit d'isométrie. Au lieu d'appliquer des portes multi-contrôlées-X individuelles pour annuler les qubits hors-sous-espace pour chacun des $s$ états (comme le fait Malvetti et al.), les auteurs regroupent les états en lots (batches) de taille $m$, où $m$ est la plus grande puissance de deux s'insérant dans le registre non-sous-espace disponible ($m \le n - \lceil \log(s) \rceil$).

   • Pour chaque lot, l'algorithme transforme les états en une forme où le registre non-sous-espace contient un unique $|1\rangle$ à des positions distinctes (ex: $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$).
   • Un circuit d'Itération Unaire Partielle (PUI) est ensuite appliqué pour annuler simultanément les registres non-sous-espace pour l'ensemble du lot.

2. Circuits d'Itération Unaire Partielle (PUI) :
   Les auteurs introduisent deux variantes de circuits PUI, qui itèrent sur un intervalle spécifique $[l, r]$ d'un registre d'adresse plutôt que sur l'espace complet :

   • PUI Restreinte : Garantit que les unitaires ne sont appliqués qu'aux états à l'intérieur de l'intervalle cible $[l, r]$.
   • PUI Non-Restreinte : Permet au circuit d'appliquer des unitaires non triviaux à des états dont les valeurs d'adresse sont supérieures à $r$. Cette relaxation réduit considérablement le nombre de Toffoli. Les effets « indésirables » sur les valeurs d'adresse supérieures sont suivis classiquement et corrigés lors des étapes ou des lots suivants.

3. Optimisation Conjointe avec la Préparation d'États Denses :
   Les auteurs analysent l'arbitrage entre le coût de l'isométrie et le coût de la préparation d'états denses. Ils proposent d'« externaliser » certaines sous-tâches de la préparation dense vers le circuit d'isométrie :

   • Corrections de Signe : Au lieu de décalculer le registre d'angle après la préparation dense (ce qui nécessite des Toffolis supplémentaires pour la correction de signe), l'information de signe est encodée directement dans l'isométrie via des PUI restreintes.
   • États Réels : Pour les états cibles ayant des coefficients purement réels, l'étape de codage de phase de la préparation dense est entièrement supprimée et gérée au sein de l'isométrie, réduisant potentiellement le coût de Toffoli de la préparation dense d'un facteur allant jusqu'à trois.

Contributions Clés

• Algorithme d'Isométrie Amélioré : Un nouvel algorithme classique (Algorithme 1) qui construit des circuits d'isométrie avec un coût de Toffoli dans le pire des cas borné par :
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  où $\tilde{s} = 2^{\lceil \log(s) \rceil}$. Cela représente une amélioration d'environ $\log(s)/2$ par rapport à la méthode de pointe de Malvetti et al.
• Variantes de PUI : La définition et l'analyse de coût des circuits d'itération unaire partielle restreints et non-restreints. La version non-restreinte atteint des nombres de Toffoli plus faibles en permettant une « fuite » d'opérations vers des valeurs d'adresse supérieures, ce qui est gérable dans le contexte de la construction d'isométrie par lots.
• Analyse de Compromis de Ressources : Une analyse complète (Tableau 1) des coûts combinés de Toffoli et de qubits pour la préparation d'états creux, démontrant comment l'optimisation de l'isométrie permet une meilleure utilisation des qubits ancilla pour réduire le coût de la préparation dense, particulièrement pour les états à valeurs réelles.
• Implémentation : Les circuits sont implémentés dans le framework Qualtran, avec l'algorithme classique de recherche d'isométrie optimisé via du code Rust accéléré par SIMD.

Résultats

• Bornes Théoriques : Le coût de Toffoli dans le pire des cas pour l'isométrie est réduit de $O(s \log s)$ à environ $O(s)$ pour des valeurs de $n$ suffisamment grandes. Plus précisément, le coût approche $s$ dans les tests numériques sur des états aléatoires, comparé à l'environ $s \log s$ de la meilleure méthode précédente.
• Tests Numériques :
  • Pour des états $s$-creux aléatoires, le nombre de Toffolis par $s$ tend vers 1 à mesure que $n$ augmente (Figure 2, droite).
  • Pour les états purement réels, l'optimisation conjointe réduit significativement le compte total de Toffoli par rapport aux états complexes génériques (Figure 9).
  • L'algorithme classique s'exécute efficacement, trouvant des isométries pour $s=10^7$ états en environ 10 à 20 minutes sur du matériel CPU standard.
• Comparaison : La méthode proposée surpasse la littérature existante (ex: [4, 14, 20, 21]) en termes de nombre de Toffoli tout en maintenant un surcoût de qubits comparable ou inférieur.

Signification et Revendications
L'article affirme présenter les circuits de préparation d'états creux les plus efficaces de la littérature en termes de comptes de Toffoli et de qubits. La signification réside dans :

1. Suppression du Goulot d'Étranglement : En réduisant le coût de l'isométrie d'un facteur dominant à un niveau comparable à celui de la préparation dense, l'algorithme global devient plus efficace.
2. Scalabilité : L'approche passe favorablement avec le nombre de qubits $n$, la rendant adaptée aux algorithmes quantiques à grande échelle tolérants aux fautes où $s$ est grand mais $s \ll 2^n$.
3. Praticité : La méthode est compatible avec les cadres existants d'estimation de ressources pour le calcul tolérant aux fautes (se concentrant sur les comptes de Toffoli) et est implémentée dans un framework logiciel modulaire (Qualtran).

Les auteurs restent modestes quant aux implications futures, notant que si le compte de Toffoli est la métrique standard actuelle, les progrès de la génération d'états magiques (culture/distillation) pourraient déplacer l'attention vers les métriques de temps d'exécution à l'avenir. Ils laissent également ouverte la question de savoir si des coûts de Toffoli sous-linéaires en $s$ sont réalisables avec des ressources d'ancilla limitées.