Dequantization and Hardness of Spectral Sum Estimation

Sur la base du texte fourni, voici un résumé technique détaillé de l'article « Dequantization and Hardness of Spectral Sum Estimation ».

Énoncé du problème

L'article traite de la complexité computationnelle de l'estimation des sommes spectrales de matrices, définies par $\text{tr}[f(A)] = \sum_{i=1}^N f(\lambda_i)$, où $\lambda_i$ sont les valeurs propres d'une matrice hermitienne $A$. Les exemples clés incluent le log-déterminant ($\log \det(A)$), la fonction de partition ($\text{tr}[e^{-\beta A}]$), les traces de puissances ($\text{tr}[A^p]$) et la trace de l'inverse ($\text{tr}[A^{-1}]$).

Des algorithmes quantiques récents ont démontré que pour des matrices creuses et bien conditionnées, ces quantités peuvent être approximées avec une erreur relative $\epsilon$ en un temps polylogarithmique en dimension $N$ (spécifiquement $\text{poly}(\log N, s, \kappa, 1/\epsilon)$, où $s$ est la parcimonie et $\kappa$ le nombre de conditionnement). L'article examine deux questions fondamentales :

1. Déquantification : Dans quelle mesure ces paramètres de temps d'exécution quantique peuvent-ils être reproduits par des algorithmes classiques ?
2. Dureté (Hardness) : Lorsque la reproduction classique n'est pas possible, quels sont les obstacles de la théorie de la complexité ?

Méthodologie

Les auteurs développent deux cadres algorithmiques classiques distincts et les complètent par des bornes inférieures de complexité théorique.

1. Algorithmes classiques

Les deux algorithmes reposent sur l'observation que si un polynôme $p(x)$ approxime uniformément une fonction $f(x)$ sur le spectre de $A$, alors les sommes spectrales normalisées de $f$ et $p$ sont proches. La tâche centrale consiste à estimer la trace normalisée d'un polynôme de matrice, $\frac{1}{2^n}\text{tr}[p(A)]$, qui peut être exprimée comme l'espérance des entrées diagonales : $\mathbb{E}_{i}[p(A)_{ii}]$.

• Puissance creuse déterministe (pour les matrices creuses) :

  • Approche : Cet algorithme échantillonne un indice diagonal aléatoire $i$ et énumère explicitement tous les cycles fermés de longueur jusqu'à $d$ (le degré du polynôme d'approximation) partant de $i$ et s'y terminant.
  • Mécanisme : Pour une matrice $s$-creuse, le nombre de tels cycles est borné par $s^d$. L'algorithme calcule la somme pondérée de ces cycles pour évaluer $p(A)_{ii}$.
  • Temps d'exécution : $O^*(s^d \cdot f_{\max}^2 / \epsilon^2)$.
  • Application : En utilisant la troncature de Chebyshev pour approximer $\log(x)$, les auteurs dérivent un algorithme pour le log-déterminant d'une matrice $s$-creuse de nombre de conditionnement $\kappa$. Le temps d'exécution est $O^*(s^{c \cdot \sqrt{\kappa} \log(\kappa/\epsilon)})$. Cela représente une amélioration exponentielle par rapport aux méthodes classiques précédentes (par exemple, l'estimateur de Hutchinson) qui croissent de manière polynomiale avec le nombre total de non-zéros $\|A\|_0$.

• Estimateur de marche aléatoire (pour les Hamiltoniens locaux) :

  • Approche : Cet algorithme remplace l'énumération exhaustive par une marche aléatoire. Partant d'un indice $i$ aléatoire, la marche effectue des transitions vers des voisins avec une probabilité proportionnelle à la valeur absolue des entrées de la matrice.
  • Mécanisme : L'algorithme maintient un poids courant qui compense les probabilités de transition en utilisant les normes 1 des lignes et les signes complexes. Cela garantit que l'estimateur est sans biais.
  • Avantage : Pour les Hamiltoniens $k$-locaux avec une force d'interaction totale bornée, la norme 1 $\|H\|_1$ est bornée par $2^{k/2}$, indépendamment du nombre de termes locaux $m$.
  • Temps d'exécution : $O^*(2^{kd} \|p\|_1^2 / \epsilon^2)$. Cela supprime la dépendance au nombre de termes $m$ de la partie exponentielle du temps d'exécution, rendant l'algorithme efficace pour les Hamiltoniens log-locaux.

2. Dureté de la complexité théorique

Les auteurs établissent des bornes inférieures pour déterminer quand les algorithmes classiques ne peuvent pas atteindre la même efficacité que les algorithmes quantiques.

• Complétude DQC1 : L'article prouve que l'estimation des sommes spectrales normalisées (traces de puissances et d'inverses) pour les Hamiltoniens log-locaux avec une précision additive inverse-polynomiale est DQC1-complète. Cela résout un problème ouvert concernant l'estimation de la norme Schatten-$p$. La preuve utilise une construction circuit-vers-Hamiltonien (la construction de Kitaev adaptée par Brandão), montrant que la somme spectrale encode la probabilité de rejet d'un circuit DQC1.
• Complétude PP : Pour les sommes spectrales non normalisées, les auteurs prouvent la complétude PP sous des hypothèses légères (approximabilité polynomiale et non-dégénérescence). La réduction implique la construction d'une matrice diagonale où la trace correspond au nombre de satisfaisants d'une formule booléenne, réduisant le problème à MAJSAT.

Résultats clés

1. Déquantification du log-déterminant : Les auteurs fournissent un algorithme classique pour le log-déterminant de matrices creuses et bien conditionnées qui s'exécute en un temps $O^*(s^{c \cdot \sqrt{\kappa} \log(\kappa/\epsilon)})$. Bien qu'il ne soit pas entièrement polynomial dans tous les paramètres (spécifiquement $\kappa$ et $\epsilon^{-1}$), il offre une amélioration exponentielle en dimension $N$ par rapport aux méthodes classiques dépendant de $\|A\|_0$.
2. Paysage de la complexité : L'article cartographie la complexité de quatre sommes spectrales (log-déterminant, fonction de partition, trace de puissances, trace d'inverse) à travers différents régimes de paramètres :
   • Paramètres constants : Tous les problèmes sont dans BPP (résolubles par un temps polynomial aléatoire classique).
   • Paramètres polylogarithmiques (ex: $\kappa, \beta, p$) : Les problèmes admettent des algorithmes classiques en temps quasi-polynomial.
   • Paramètres polynomiaux : Pour les Hamiltoniens log-locaux, les problèmes sont DQC1-complets, impliquant qu'aucun algorithme classique de temps polynomial n'existe à moins que DQC1 $\subseteq$ BPP.
   • Précision inverse-exponentielle : Les problèmes deviennent PP-complets.
3. Résolution de problèmes ouverts : Ce travail résout la dureté DQC1 pour les traces de puissances polynomiales et les inverses, complétant ainsi le tableau de la complexité de ces sommes spectrales initié par Cade et Montanaro (2018).

Signification et revendications

L'article affirme s'inscrire dans le programme plus large de « déquantification » des algorithmes d'algèbre linéaire quantique. Sa signification réside dans :

• Déquantification partielle : Démontrer que la dépendance polylogarithmique en dimension $N$ obtenue par les algorithmes quantiques peut être préservée classiquement pour des régimes de paramètres spécifiques, notamment pour les matrices creuses et les Hamiltoniens locaux.
• Identification de l'avantage quantique : Les résultats suggèrent que l'avantage quantique apparent dans l'estimation des sommes spectrales ne provient pas de la capacité à obtenir une précision d'estimation plus élevée en soi, mais plutôt de la capacité à gérer des paramètres spectraux (comme le nombre de conditionnement $\kappa$ ou la température inverse $\beta$) qui croissent polynomialement avec $n$. Dans ces régimes, les problèmes sont DQC1-complets, et aucun algorithme classique efficace n'est connu.
• Complétude théorique : En établissant la complétude DQC1 pour les traces de puissances polynomiales et les inverses, ce travail comble une lacune dans la compréhension de la puissance de calcul du modèle DQC1 concernant les sommes spectrales.

Les auteurs notent que bien que leurs algorithmes classiques améliorent les limites précédentes, ils ne déquantifient pas entièrement les algorithmes quantiques dans tous les régimes de paramètres (spécifiquement lorsque $\kappa$ ou $\epsilon^{-1}$ sont grands). De plus, ils laissent ouverte la question de savoir si les sommes spectrales normalisées de matrices creuses générales (pas seulement les Hamiltoniens log-locaux) peuvent être estimées en DQC1, notant que les techniques standards de block-encoding pourraient ne pas être assez efficaces en termes d'ancilla pour le modèle DQC1.