Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques

Cette série de notes de cours présente les algorithmes de réseaux de tenseurs, spécifiquement les états et opérateurs de type MPS (Matrix Product States/Operators), en tant qu'outils d'algèbre linéaire généraux pour traiter des systèmes exponentiellement grands, fournissant des preuves détaillées et des applications allant de la simulation quantique à la résolution d'équations aux dérivées partielles via la représentation « quantique ».

L'essentiel

L'idée générale : La bibliothèque « impossible »

Imaginez que vous avez une bibliothèque contenant $2^{50}$ livres (c'est plus que le nombre d'atomes dans votre corps). Un ordinateur quantique est une machine magique conçue pour feuilleter ces livres incroyablement vite. Cependant, il y a un piège : vous ne pouvez pas lire toute la bibliothèque à la fois. Vous ne pouvez jeter un coup d'œil qu'à un seul livre à la fois (un « échantillon »).

L'article pose une question provocatrice : Un ordinateur classique (un supercalculateur traditionnel) peut-il faire le même travail que cette machine quantique magique ?

Habituellement, la réponse est « Non », car la bibliothèque est trop grande pour tenir en mémoire. Mais les auteurs soutiennent que beaucoup de ces « bibliothèques » cachent un secret : elles ne sont pas un chaos aléatoire. Elles possèdent une structure simple et répétitive, comme une fractale ou un motif. Si vous connaissez le motif, vous n'avez pas besoin de stocker chaque livre ; vous avez seulement besoin de stocker les instructions pour les construire.

Cet article vous apprend comment trouver ces motifs en utilisant un outil appelé Réseaux de tenseurs (Tensor Networks).

---

L'outil principal : L'approche « Lego » (Réseaux de tenseurs)

Les auteurs introduisent une technique mathématique appelée Réseaux de tenseurs. Imaginez un objet 3D géant et complexe (comme une sculpture massive) qui représente un état quantique.

• Le Problème : Décrire l'objet entier à la fois nécessite un milliard de nombres.
• La Solution (Réseaux de tenseurs) : Au lieu de décrire l'ensemble, on le décompose en petites briques de Lego simples.
  • MPS (Matrix Product States) : Ce sont comme une longue chaîne de briques Lego. Chaque brique est connectée à la suivante. Si la sculpture n'est pas trop « tordue » (intriquée), vous pouvez reconstruire tout l'objet en utilisant seulement quelques petites briques.
  • MPO (Matrix Product Operators) : Ce sont comme des instructions ou des outils Lego qui vous disent comment modifier la sculpture (comme une porte dans un circuit quantique).

L'article montre que pour beaucoup de problèmes, vous n'avez pas besoin de la bibliothèque d'un milliard de nombres. Vous avez juste besoin de la chaîne de briques Lego. Cela permet à un ordinateur classique de simuler ce qu'un ordinateur quantique fait, mais beaucoup plus rapidement et avec moins de mémoire.

L'algorithme d'apprentissage « Magique » (TCI)

L'une des parties les plus fascinantes de l'article est un algorithme appelé Interpolation Croisée Tensorielle (TCI - Tensor Cross Interpolation).

• L'Analogie : Imaginez que vous essayez de deviner la forme d'une chaîne de montagnes cachée. Vous ne pouvez pas voir toute la chaîne, mais vous pouvez demander à un guide : « Quelle est la hauteur à cet endroit précis ? »
• Comment ça marche : Au lieu de demander pour chaque point (ce qui prendrait une éternité), le TCI est un détective intelligent. Il interroge quelques points stratégiques, comprend le motif, puis complète le reste de la carte.
• Le Résultat : Il peut apprendre la forme d'une fonction complexe (comme une onde ou une distribution de chaleur) en ne regardant qu'une infime fraction des données. Il transforme un problème de « boîte noire » en un ensemble d'instructions Lego (un MPS) qu'un ordinateur peut facilement gérer.

L'astuce « Quantics » : Zoomer et Dézoomer

L'article introduit un concept appelé Quantics pour résoudre des équations physiques (comme la propagation de la chaleur ou le mouvement des ondes).

• L'Analogie : Imaginez la carte d'un pays. Habituellement, vous regardez le pays entier à la fois. Mais et si vous pouviez zoomer sur une ville, puis sur une rue, puis sur une maison, tout cela en même même temps ?
• L'Astuce : Les auteurs représentent les nombres en binaire (0 et 1). Le premier bit vous indique si vous êtes du côté gauche ou droit du pays (grande échelle). Le bit suivant vous indique si vous êtes au nord ou au sud de ce côté (échelle moyenne). Le dernier bit vous indique si vous êtes à gauche ou à droite de votre propre maison (petite échelle).
• Pourquoi ça aide : En organisant les données de cette façon, l'ordinateur voit que les changements à « grande échelle » et les changements à « petite échelle » sont souvent indépendants. Cela rend la « chaîne de Lego » (MPS) très courte et facile à calculer.
• Le Résultat : Ils peuvent résoudre des équations sur une grille de billions de points sur un ordinateur portable ordinaire. Un ordinateur normal planterait en essayant de stocker autant de points en mémoire, mais l'astuce de compression Lego des « Quantics » réduit cela à quelque chose de gérable.

Le test de réalité de la « Suprématie Quantique »

L'article discute des célèbres expériences de « Suprématie Quantique » (où des entreprises prétendent que leurs ordinateurs quantiques ont fait quelque chose d'impossible pour les classiques).

• Le point de vue de l'article : Les auteurs sont sceptiques face au battage médiatique. Ils soutiennent que ces expériences ont été conçues pour créer du « bruit aléatoire » (un chaos sans motif). Bien sûr, un ordinateur classique a du mal à simuler du bruit aléatoire !
• Le Piège : Si l'ordinateur quantique fait quelque chose d'utile (comme simuler une réaction chimique ou un matériau spécifique), l'état possède généralement beaucoup de structure. L'article montre que les ordinateurs classiques, en utilisant ces techniques de Lego, peuvent très bien simuler ces états quantiques utiles.
• Le Verdict : Un ordinateur quantique n'est pas une baguette magique qui résout tout. C'est un outil spécifique. Si le problème possède une structure de « rang faible » (des motifs Lego simples), un ordinateur classique peut souvent battre le quantique.

Résumé de ce qu'ils ont fait

1. Enseigné les bases : Comment décomposer de grands problèmes mathématiques en petites pièces connectées (Réseaux de tenseurs).
2. Montré comment simuler les ordinateurs quantiques : Ils ont construit un ordinateur quantique « virtuel » sur un ordinateur portable ordinaire capable de gérer des centaines de qubits, à condition que le circuit ne soit pas trop chaotique.
3. Introduit un outil d'apprentissage (TCI) : Une façon d'apprendre à un ordinateur la forme d'un problème en jetant simplement un coup d'œil à quelques points de données.
4. Résolu la physique réelle : Ils ont utilisé ces outils pour résoudre des équations complexes (comme le flux de chaleur et les équations d'ondes) sur des grilles si vastes qu'elles seraient normalement impossibles à traiter, le tout sur une station de travail standard.

L'essentiel à retenir

L'article affirme que les ordinateurs classiques ne sont pas condamnés. Tant que le problème possède une certaine structure sous-jacente (ce qui est le cas de la plupart des problèmes scientifiques utiles), nous pouvons utiliser les « Réseaux de tenseurs » pour compresser les données et résoudre le problème. Nous n'avons pas toujours besoin d'un ordinateur quantique pour faire le gros du travail ; parfois, un algorithme classique astucieux peut rivaliser, et même gagner, face au quantique.

Résumé technique

Résumé technique : « Qui peut rivaliser avec les ordinateurs quantiques ? Notes de cours sur les techniques de calcul par réseaux de tenseurs d'inspiration quantique »

Énoncé du problème
Le document traite du défi fondamental que représente la simulation de systèmes quantiques et la résolution de problèmes d'algèbre linéaire de haute dimension qui croissent de manière exponentielle avec la taille du système ($2^N$ pour $N$ qubits). Bien que les ordinateurs quantiques soient théoriquement capables de manipuler ces espaces d'états exponentiellement grands, les supercalculateurs classiques ne peuvent pas stocker la fonction d'onde complète pour $N \gtrsim 50$. Cependant, les auteurs notent que de nombreux états physiquement pertinents possèdent des structures mathématiques internes qui permettent une représentation classique efficace. Le problème central consiste à identifier et à exploiter ces structures — spécifiquement les propriétés de bas rang — pour effectuer des multiplications matrice-vecteur, résoudre des problèmes de valeurs propres et simuler la dynamique sans stocker explicitement l'objet exponentiel complet. Les cours visent à détacher les algorithmes de réseaux de tenseurs de leur contexte traditionnel de la physique du corps condensé pour les présenter comme des outils généraux d'algèbre linéaire sur de grandes matrices et de grands vecteurs.

Méthodologie
Le document présente une suite complète d'algorithmes basés sur les États de Produits de Matrices (MPS) et les Opérateurs de Produits de Matrices (MPO). Ce sont des représentations de réseaux de tenseurs qui factorisent des vecteurs et des matrices exponentiellement grands en une chaîne de petits tenseurs locaux connectés par des indices virtuels (dimensions de liaison ou bond dimensions).

1. Émulation exacte : Les auteurs établissent d'abord que les circuits quantiques sont des réseaux de tenseurs. Ils décrivent des stratégies d'émulation exacte :

   • Simulateur d'état complet : Alloue un vecteur de taille $2^N$ et applique les portes séquentiellement. Cela croît exponentiellement en mémoire ($O(2^N)$) mais linéairement par rapport au nombre de portes.
   • Émulateur MPS exact : Représente l'état sous forme de MPS. Pour les circuits à faible intrication (par exemple, des portes de voisinage immédiat sur des états produits), cela croît linéairement en $N$ et polynomialement par rapport à la profondeur du circuit, à condition que la dimension de liaison $\chi$ reste faible.

2. Compression et approximation : Pour gérer des systèmes plus larges, les cours introduisent la compression à bas rang via la Décomposition en Valeurs Singulières (SVD).

   • Forme canonique : Un choix de jauge où les tenseurs sont des isométries, permettant de lire directement l'entropie d'intrication à partir des valeurs singulières d'un tenseur central.
   • TEBD (Time-Evolving Block Decimation) : Un algorithme pour les circuits quantiques où les portes sont appliquées, et l'état résultant est tronqué via SVD pour maintenir une dimension de liaison $\chi$ fixe. Cela introduit une erreur contrôlée, bornée par les valeurs singulières rejetées.
   • DMRG (Density Matrix Renormalization Group) : Adapté ici pour les circuits quantiques et la diagonalisation de Hamiltoniens. Il optimise un ou deux tenseurs à la fois pour minimiser l'énergie (pour les Hamiltoniens) ou maximiser la fidélité (pour les circuits), en parcourant le système jusqu'à convergence.

3. Apprentissage et construction (TCI) : Une partie importante de la méthodologie est dédiée à l'Interpolation Croisée de Tenseurs (TCI). Contrairement aux méthodes traditionnelles qui nécessitent l'accès au tenseur complet, la TCI est un algorithme d'apprentissage actif qui construit une représentation MPS/MPO en interrogeant une fonction $F(\sigma)$ à des indices spécifiques.

   • Elle utilise l'Interpolation Croisée (CI) et la décomposition LU à révélation de rang partielle (prrLU) pour sélectionner des « pivots » (lignes et colonnes) qui maximisent le déterminant (principe du maxvol), garantissant que les tranches sélectionnées capturent l'information essentielle de la matrice.
   • Cela permet la conversion de fonctions arbitraires (par exemple, des intégrandes, des potentiels) en formats MPS/MPO sans connaissance préalable de leur structure tensorielle.

4. La représentation « Quantics » : Les auteurs introduisent un schéma de discrétisation spécifique où une variable continue $x$ est mappée sur une chaîne binaire de bits. Cette représentation « quantics » permet de traiter les fonctions de variables continues comme des MPS.

   • Ils fournissent des constructions analytiques de MPO pour les opérateurs différentiels (différentiation, intégration, Laplacien), la convolution, et la Transformée de Fourier Quantique (QFT).
   • Crucialement, la QFT est montrée comme étant un MPO de bas rang (rang $\chi \approx 15$ pour la précision machine), permettant des transformées de Fourier « super-rapides » sur des grilles de $2^N$ points.

Contributions clés

• Généralisation des réseaux de tenseurs : Les cours recadrent les MPS et MPO non pas simplement comme des outils de la physique de la matière condensée, mais comme des solveurs d'algèbre linéaire généraux pour des vecteurs et des matrices exponentiellement grands.
• Boîte à outils algorithmique : Le texte fournit des dérivations détaillées, étape par étape, pour :
  • L'échantillonnage à partir d'un MPS (échantillonnage exact via la règle de chaîne bayésienne).
  • L'addition et la multiplication de MPS/MPO.
  • La résolution de systèmes linéaires ($Ax=b$) utilisant les MPS.
  • La construction analytique de MPO pour les opérateurs différentiels et la QFT.
• La TCI comme passerelle : Le document positionne la TCI comme le pont critique permettant de mapper des problèmes n'appartenant pas aux réseaux de tenseurs (comme les équations aux dérivées partielles) dans le cadre des réseaux de tenseurs.
• Quantics pour les EDP : Les auteurs démontrent comment la représentation quantics, combinée à la TCI et aux MPO de bas rang, permet de résoudre des EDP (Poisson, Schrödinger, équation de la chaleur) sur des grilles de $2^{30}$ à $2^{40}$ points en utilisant des stations de travail standards, une échelle inatteignable par les méthodes de force brute.

Résultats
Le document illustre ces méthodes à travers des applications concrètes :

• Simulation de circuits quantiques : Les comparaisons montrent que pour les circuits à faible intrication (ex: génération d'état GHZ), l'émulateur MPS exact évolue en $\sim N^2$, tandis que le simulateur d'état complet évolue en $\sim N 2^N$.
• Circuits aléatoires et fidélité : Les simulations de circuits quantiques aléatoires (similaires aux expériences de « suprématie quantique ») montrent que la fidélité décroît exponentiellement avec la profondeur du circuit, de manière contrôlée par la dimension de liaison. Cela suggère que même pour de grands $N$, si le taux d'erreur (ou la dimension de liaison effective) est suffisamment bas, les réseaux de tenseurs peuvent simuler le système.
• Solutions d'EDP :
  • Intégration : La TCI est utilisée pour calculer une intégrale oscillatoire à 10 dimensions, convergeant en $\sim 1/N_{eval}^4$, surpassant nettement les méthodes de Monte Carlo qui souffrent du problème de signe et évoluent en $1/\sqrt{N_{eval}}$.
  • Équation de la chaleur : En utilisant le MPO de la QFT à bas rang, l'équation de la chaleur est résolue sur une grille de $2^{30}$ points (un billion de points) en quelques secondes sur un ordinateur portable.
  • Équation de Gross-Pitaevskii : Des simulations de cette équation non linéaire sur un potentiel quasi-périodique sont réalisées avec $2^{20}$ points de grille par dimension, démontrant la capacité à gérer des échelles de longueurs très différentes.

Signification et revendications
Les auteurs affirment que ces techniques « d'inspiration quantique » rivalisent directement avec les capacités des ordinateurs quantiques en exploitant les mêmes structures mathématiques sous-jacentes (faible intrication/bas rang) qui rendent les états quantiques tractables.

• Recadrage de la suprématie quantique : Le document soutient que les expériences de « suprématie quantique » ciblent souvent des états aléatoires et chaotiques difficiles à simuler, mais qui manquent de pertinence physique. À l'inverse, de nombreux algorithmes quantiques et systèmes physiques possèdent une structure permettant aux réseaux de tenseurs classiques de les simuler efficacement.
• Goulot d'étranglement d'E/S : Les auteurs soulignent que les ordinateurs quantiques font face à un « goulot d'étranglement d'E/S » (produisant seulement $N$ bits d'information probabiliste), tandis que les réseaux de tenseurs peuvent fournir la fonction d'onde complète ou des intégrales de haute précision.
• Perspectives futures : Le document pose que les réseaux de tenseurs et la TCI joueront un rôle pivot dans l'avenir de l'informatique quantique, servant potentiellement d'interface pour mapper les entrées de problèmes vers des formats de réseaux de tenseurs qui pourront ensuite être compilés en circuits quantiques. Les auteurs insistent sur le fait que, bien que les réseaux de tenseurs soient puissants, ils ne sont pas une panacée ; ils dépendent de l'existence d'une structure de bas rang, ce qui n'est pas garanti pour tous les problèmes.

En résumé, ce document sert de guide pédagogique et technique démontrant que les algorithmes de réseaux de tenseurs classiques, particulièrement lorsqu'ils sont augmentés par la TCI et la représentation quantics, offrent une alternative robuste, scalable et souvent supérieure à la simulation par force brute pour une large classe de problèmes de haute dimension, défiant ainsi la nécessité de l'infrastructure matérielle quantique pour certaines tâches spécifiques.