Résumé technique : Sur l'estimation de la trace des puissances d'états quantiques

Énoncé du problème

Cet article étudie la complexité computationnelle de l'estimation de la trace des puissances d'états quantiques, $\text{tr}(\rho^q)$, pour un état mixte quantique de $n$ qubits $\rho$ donné par son circuit de préparation d'état de taille $\text{poly}(n)$. Cette quantité est intrinsèquement liée à l'entropie de Tsallis quantique $q$, définie par $S_q(\rho) = \frac{1 - \text{tr}(\rho^q)}{q - 1}$. Les auteurs se concentrent sur deux problèmes de décision primaires :

1. Problème de différence d'entropie de Tsallis quantique $q$ (TsallisQED$_q$) : Étant donnés deux circuits de taille polynomiale préparant les états $\rho_0$ et $\rho_1$, décider si $S_q(\rho_0) - S_q(\rho_1) \ge 0,001$ ou si $S_q(\rho_1) - S_q(\rho_0) \ge 0,001$.
2. Problème d'approximation de l'entropie de Tsallis quantique $q$ (TsallisQEA$_q$) : Étant donné un seul circuit préparant $\rho$ et un seuil $t(n)$, décider si $S_q(\rho) - t(n) \ge 0,001$ ou si $S_q(\rho) - t(n) \le -0,001$.

L'étude comble une lacune dans la littérature existante où des algorithmes quantiques efficaces n'étaient auparavant connus que pour les entiers $q \ge 2$ (par exemple, l'estimation de la pureté via le test SWAP) ou résultaient en une complexité de temps exponentielle $\exp(n)$ pour les $q$ non entiers $q > 1$ lorsque l'état est fourni via un circuit de préparation.

Méthodologie

Algorithmes quantiques efficaces (Bornes supérieures)

Pour le régime $q \ge 1 + \Omega(1)$, les auteurs proposent un algorithme quantique qui atteint une complexité de temps polynomiale, améliorant considérablement les résultats $\exp(n)$ précédents. La méthodologie repose sur trois composantes centrales :

1. Approximation polynomiale uniforme : Les auteurs introduisent des approximations polynomiales uniformes calculables efficacement pour les fonctions de puissance positives $x^q$ sur l'intervalle $[0, 1]$. Contrairement aux approches précédentes qui utilisaient des approximations par morceaux (entraînant des erreurs dépendantes du rang), cette méthode utilise des troncatures de Chebyshev et des sommes partielles de de La Vallée Poussin pour construire des polynômes $P(x)$ tels que $\max_{x \in [0,1]} |P(x) - \frac{1}{2}x^q| \le \epsilon$ avec un degré de $O(1/\epsilon^{1/q})$.
2. Transformation de la valeur singulière quantique (QSVT) : En utilisant le polynôme construit, l'algorithme implémente un bloc-encodage de l'opérateur $\rho^{q-1}$ via la QSVT.
3. Test de Hadamard et estimation d'amplitude : La trace $\text{tr}(\rho^q)$ est estimée en effectuant un test de Hadamard sur l'opérateur bloc-encodé et l'état $\rho$, suivi de l'estimation d'amplitude quantique pour atteindre l'erreur additive $\epsilon$ souhaitée.

Cette approche produit une complexité de requête de $O(1/\epsilon^{1 + \frac{1}{q-1}})$ et une complexité de temps de $\text{poly}(n, 1/\epsilon)$ pour $q \ge 1 + \Omega(1)$. Une variante plus efficace en termes d'échantillonnage est également dérivée en utilisant une technique de « samplizer », résultant en une complexité d'échantillonnage de $\tilde{O}(1/\epsilon^{3 + \frac{2}{q-1}})$.

Résultats de dureté (Bornes inférieures)

Pour établir la dureté computationnelle, les auteurs effectuent des réductions à partir de problèmes connus de test d'état quantique vers TsallisQED$_q$ et TsallisQEA$_q$.

1. Nouvelles inégalités : Les preuves reposent sur l'établissement de nouvelles inégalités entre la divergence de Jensen-Tsallis quantique $q$ ($QJT_q$) et la distance de trace $T(\rho_0, \rho_1)$ pour $1 \le q \le 2$. Plus précisément, ils prouvent des inégalités de traitement de données pour $QJT_q$ et des bornes reliant $QJT_q$ à la distance de trace, généralisant les résultats connus pour l'entropie de von Neumann ($q=1$).
2. Réductions :
   • Dureté BQP : Pour $1 \le q \le 2$, les auteurs réduisent le problème de distinction d'états purs (PureQSD), qui est BQP-dur, à la variante à rang constant de TsallisQED$_q$. Cela démontre que l'estimation de la différence d'entropie pour des états à rang constant capture toute la puissance de BQP.
   • Dureté QSZK/NIQSZK : Pour le régime $1 < q \le 1 + \frac{1}{n-1}$, des réductions sont faites à partir des problèmes généraux de distinction d'états quantiques (QSD) et de proximité d'un état quantique par rapport à l'état mixte maximal (QSCMM). Ces réductions utilisent des bornes sur l'entropie de Tsallis par rapport à la distance de trace, montrant que ces problèmes sont QSZK-durs et, pour certains $q$, NIQSZK-durs.

Contributions clés et résultats

1. Transition de phase nette dans la complexité

Le papier identifie une transition de phase nette dans la complexité computationnelle de l'estimation de $S_q(\rho)$ :

• Régime facile ($q \ge 1 + \Omega(1)$) : Les problèmes TsallisQED$_q$ et TsallisQEA$_q$ sont contenus dans BQP. Les auteurs fournissent un algorithme quantique avec une complexité de temps polynomiale, exponentiellement plus rapide que les approches $\exp(n)$ antérieures.
• Régime difficile ($1 < q \le 1 + \frac{1}{n-1}$) : Les problèmes deviennent QSZK-durs (et NIQSZK-durs pour certains $q$). Cela implique que, sauf si $\text{BQP} \subseteq \text{QSZK}$, aucun algorithme quantique efficace n'existe pour ces régimes.
• Cas limite ($q=1$) : Correspond à l'entropie de von Neumann, qui est connue pour être QSZK-complète (pour la différence) et NIQSZK-complète (pour l'approximation).

2. BQP-complétude de l'estimation de la pureté

Comme corollaire direct du résultat de dureté BQP pour $1 \le q \le 2$, l'article établit que l'estimation de la pureté (estimer $\text{tr}(\rho^2)$) est BQP-dure. Cela résout une question de longue date concernant la capacité de l'estimation de la trace des puissances d'états quantiques à capturer pleinement la puissance de calcul quantique.

3. Nouveaux outils mathématiques

• Approximations polynomiales uniformes efficaces : La construction d'approximations polynomiales uniformes calculables efficacement pour $x^q$ adaptées à la QSVT, évitant la dépendance au rang des méthodes précédentes.
• Inégalités $QJT_q$ : Nouvelles inégalités bornant la divergence de Jensen-Tsallis quantique en termes de distance de trace pour $1 \le q \le 2$, incluant des inégalités de traitement de données dérivées de la convexité jointe.
• Bornes de l'entropie binaire de Tsallis : Bornes plus serrées pour l'entropie binaire de Tsallis $H_q(x)$ pour $1 \le q \le 2$.

Signification et affirmations

L'article affirme résoudre le paysage de la complexité computationnelle de l'estimation de l'entropie de Tsallis quantique $q$ à travers différents régimes de $q$.

• Percée algorithmique : Il fournit le premier estimateur quantique efficace (en temps polynomial) pour les $q$ non entiers $q \ge 1 + \Omega(1)$, surmontant la barrière exponentielle des travaux antérieurs (ex. [AISW20, WGL+24, WZL24]).
• Classification de la complexité : Il délimite précisément la frontière entre les régimes tractables (BQP) et intractables (QSZK-dur), révélant que la difficulté d'estimer l'entropie augmente à mesure que $q$ s'approche de 1 par le haut, spécifiquement lorsque $q$ est à $O(1/n)$ de 1.
• Aperçu fondamental : En prouvant que l'estimation de la pureté est BQP-dure, ce travail confirme que des propriétés simples d'états quantiques (comme la pureté) sont aussi difficiles à estimer que les problèmes BQP généraux, à condition que l'état soit fourni via un circuit.

Les auteurs notent que leurs résultats reposent sur l'hypothèse que $q$ est une constante supérieure à 1 pour l'algorithme efficace, et que les résultats de dureté pour le "régime difficile" dépendent du fait que le rang des états approche la dimension $2^n$. Ils précisent explicitement que la borne supérieure efficace pour le régime difficile reste un problème ouvert, bien qu'ils fournissent des bornes inférieures correspondantes.