⚛️ quantum physics

Evaluating QAOA expectation values can be as hard as counting optimal solutions

Cet article établit que l'évaluation des valeurs d'espérance exactes ou exponentiellement précises de l'algorithme QAOA pour le problème MaxCut à une profondeur $p \geq 2$ est #P-difficile, démontrant que la difficulté computationnelle passe de la tractabilité au dénombrement des solutions optimales plutôt qu'à la simple optimisation.

Auteurs originaux : Stuart Hadfield

Publié 2026-08-13

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Stuart Hadfield

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un monde où les ordinateurs ne se contentent pas de brasser des chiffres, mais dansent avec les probabilités. C'est le domaine de l'informatique quantique, un domaine qui promet de résoudre des problèmes si emmêlés et complexes que les superordinateurs d'aujourd'hui mettraient plus longtemps que l'âge de l'univers pour les résoudre. Au cœur de cette danse se trouve une routine populaire appelée l'Algorithme d'Optimisation Approchée Quantique, ou QAOA. Considérez le QAOA comme une chasse au trésor de haute technologie. Vous avez une carte (un problème) avec de nombreux chemins possibles, et vous voulez trouver le chemin qui mène au plus d'or (la meilleure solution). L'ordinateur quantique prépare un état spécial de « superposition » — un mélange magique de tous les chemins possibles à la fois — puis, à travers une série d'étapes appelées « couches » ou « profondeur », il tente d'incliner les probabilités pour que le meilleur chemin brille le plus intensément lorsque vous regardez enfin.

Pour savoir si la chasse au trésor se passe bien, les scientifiques doivent vérifier la « valeur d'espérance ». En langage clair, cela revient à jeter un coup d'œil rapide à la danse de l'ordinateur quantique pour voir à quel point il est proche de trouver l'or, sans pour autant arrêter la danse pour compter chaque pièce. Pendant longtemps, les chercheurs savaient que si la danse n'avait qu'une seule étape (profondeur $p=1$ ), vérifier ce score était facile, comme lire une recette simple. Mais que se passe-t-il lorsque la danse devient plus complexe, avec deux étapes ou plus ? Une étude récente de Wang et ses collègues a montré que vérifier le score pour ces danses plus profondes est incroyablement difficile — si difficile qu'il est aussi difficile de résoudre le problème de la chasse au trésor originale lui-même. Mais est-ce juste aussi difficile que de trouver un seul bon chemin, ou est-ce encore plus dur ?

Cet article, écrit par Stuart Hadfield, plonge au cœur de cette question. L'auteur prouve que pour le QAOA avec deux couches ou plus, vérifier le score n'est pas seulement aussi difficile que de trouver une seule meilleure solution ; c'est aussi difficile que de compter chaque solution parfaite qui existe. Dans le monde de l'informatique, trouver une solution est un défi de taille, mais les compter toutes est un monstre d'une tout autre dimension, souvent considéré comme encore plus impossible à gérer pour les ordinateurs classiques. Hadfield montre que ce « monstre du comptage » apparaît dès que l'on ajoute une seconde couche à l'algorithme. L'article ne fait pas que le suggérer ; il fournit une preuve mathématique rigoureuse, construisant un type spécifique de graphe de problème qui force tout ordinateur tentant de calculer le score du QAOA à résoudre essentiellement le problème impossible du comptage. Cela signifie que pour ces algorithmes quantiques plus profonds, l'acte même de vérifier s'ils réussissent est, dans le pire des cas, une tâche qui pourrait être fondamentalement hors de portée des ordinateques classiques, même si nous possédons une machine quantique parfaite pour exécuter la danse.

La chasse au trésor se complique

Décortiquons le tour de magie. L'algorithme QAOA est conçu pour résoudre le problème du « MaxCut ». Imaginez un groupe d'amis lors d'une fête, et vous voulez diviser ces amis en deux équipes (Équipe Rouge et Équipe Bleue) pour jouer à un jeu. Le but est d'organiser les équipes de manière à ce que le maximum d'amitiés soient rompues entre les deux côtés. C'est cela, le « MaxCut ». Certaines dispositions sont meilleures que d'autres, et trouver la disposition absolue est un casse-tête classique qui devient plus difficile à mesure que l'on ajoute des amis.

L'algorithme QAOA tente de trouver cette meilleure disposition en faisant tourner une pièce quantique. Il commence avec tout le monde en superposition (à la fois Rouge et Bleu) puis applique une série de « torsions » (les couches). Plus vous ajoutez de torsions, plus la danse devient sophistiquée. Pour voir si la danse fonctionne, les scientifiques calculent une « valeur d'espérance ». Voyez cela comme un « score » qui vous indique, en moyenne, combien d'amitiés sont rompues dans la danse quantique.

Pour une seule torsion ( $p=1$ ), calculer ce score est facile. Vous pouvez l'écrire sur un coin de table. Mais quand vous ajoutez une deuxième torsion ( $p=2$ ), les choses deviennent étranges. Des recherches antérieures ont montré que calculer ce score était « NP-difficile », ce qui signifie qu'il était aussi difficile que de trouver la meilleure disposition d'équipe. Mais l'article de Hadfield dit : « Attendez, c'est en fait pire que cela ».

Le monstre du comptage

La découverte principale de Hadfield est une mise à niveau radicale de notre compréhension de la difficulté. Il prouve que calculer le score pour $p \ge 2$ n'est pas seulement « NP-difficile » (trouver une solution) ; c'est #P-difficile.

Pour comprendre la différence, imaginez que vous êtes un détective.

NP-difficile, c'est comme si on vous demandait : « Pouvez-vous trouver un suspect qui a commis le crime ? » C'est difficile, mais si vous avez de la chance ou si vous essayez assez fort, vous pourriez en trouver un.
#P-difficile, c'est comme si on vous demandait : « Combien de suspects au total ont commis le crime ? » Vous devez trouver chacun d'entre eux et les compter.

Dans le monde de l'informatique, le comptage est généralement considéré comme beaucoup plus difficile que la simple recherche d'une solution. Hadfield montre que pour le QAOA avec deux couches ou plus, les mathématiques requises pour calculer le score vous obligent à compter le nombre de solutions parfaites.

Le gadget magique

Comment a-t-il prouvé cela ? Hadfield a construit un « gadget » ingénieux, qui est comme un piège conçu pour capturer l'ordinateur. Il a pris un problème MaxCut standard et a construit un graphe géant et complexe autour de lui. Ce graphe possède des points d'ancrage spéciaux et des blocs de variables.

Le truc réside dans la conception. Lorsque l'ordinateur quantique exécute sa danse sur ce graphe spécifique, le score final (la valeur d'espérance) devient une expression mathématique géante appelée « polynôme de Laurent ». Cette expression est comme une longue chaîne de termes, chacun avec une puissance différente d'une variable (comme $z^1, z^2, z^3...$ ).

Hadfield a montré que la plus haute puissance dans cette chaîne (le « coefficient extrême ») détient un secret. Si vous pouvez calculer le score parfaitement, vous pouvez extraire cette puissance la plus élevée. Et voici le plus important : la taille de ce nombre spécifique est directement proportionnelle au nombre total de solutions parfaites du problème original.

Ainsi, si vous pouviez facilement calculer le score QAOA pour ce graphe, vous connaîtriez instantanément la réponse au problème du « monstre du comptage ». Puisque le comptage est considéré comme impossible à réaliser efficacement pour les ordinateurs classiques, calculer le score du QAOA doit également être impossible pour eux.

La surprise de « l'arête unique »

L'article devient encore plus surprenant. Vous pourriez penser : « D'accord, calculer le score total est difficile, mais peut-être que calculer le score pour une seule amitié spécifique (une seule arête) est facile ? »

Hadfield dit que non. Il prouve que même si vous demandez seulement à l'ordinateur quantique de vous donner la corrélation entre deux personnes spécifiques (un « corrélateur à deux qubits » comme $\langle Z_r Z_s \rangle$ ), le problème reste #P-difficile. La difficulté n'est pas seulement dans la vue d'ensemble ; elle est ancrée dans les plus petits détails de l'algorithme.

Ce que cela signifie pour l'avenir

L'article trace une ligne claire dans le sable :

Profondeur $p=1$ : Facile. Nous pouvons calculer le score efficacement.
Profondeur $p \ge 2$ : Difficile. Calculer le score est aussi difficile que de compter toutes les solutions optimales.

Cela a d'énormes implications. De nombreux algorithmes modernes utilisent le QAOA pour entraîner la machine, en ajustant les « torsions » (paramètres) pour obtenir un meilleur score. Si calculer le score est aussi difficile, alors entraîner ces algorithmes sur un ordinateur classique (pour voir comment la machine quantique se comporte) pourrait être impossible pour des circuits profonds.

L'auteur note également que cela ne signifie pas que les ordinateurs quantiques sont inutiles. En fait, cela pourrait signifier qu'ils sont plus utiles. Si un ordinateur classique ne peut même pas vérifier le score, peut-être que l'ordinateur quantique est le seul capable de le faire. Cependant, l'article prévient aussi que cette « difficulté » est un scénario du pire des cas. Cela ne signifie pas que chaque graphe est impossible à résoudre ; cela signifie simplement qu'il existe des graphes spécifiques et complexes où les mathématiques s'effondrent pour les ordinateurs classiques.

L'essentiel

L'article de Stuart Hadfield est un signal d'alarme pour la communauté quantique. Il nous dit qu'en rendant le QAOA plus puissant en ajoutant plus de couches, nous ne faisons pas seulement en sorte que le problème soit plus difficile à résoudre ; nous faisons en sorte que le problème de vérifier notre travail devienne exponentiellement plus difficile. Nous sommes passés d'un monde où nous pouvions facilement vérifier la danse quantique à un monde où vérifier la danse nécessite de résoudre un puzzle de comptage qui pourrait être l'un des plus difficiles de l'informatique. C'est un rappel que dans le royaume quantique, plus on descend en profondeur, plus les mathématiques deviennent mystérieuses.

Résumé Technique : L'évaluation des valeurs d'espérance de l'algorithme QAOA est #P-difficile

Énoncé du Problème
Le document traite de la complexité computationnelle de l'évaluation des valeurs d'espérance pour l'algorithme d'optimisation approximative quantique (QAOA) appliqué au problème de la MaxCut (coupe maximale). Bien que l'évaluation de la valeur d'espérance du coût $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ soit connue pour être efficacement calculable pour une profondeur $p=1$ sur des graphes arbitraires, des travaux récents ont établi que l'évaluation exacte devient NP-difficile pour toute profondeur fixe $p \ge 2$ . La question centrale investiguée ici est de savoir si la difficulté pour $p \ge 2$ est limitée à l'optimisation (trouver une solution) ou si elle s'étend au comptage (déterminer le nombre de solutions optimales). Plus précisément, l'auteur cherche à savoir si le calcul de ces valeurs d'espérance est #P-difficile, une classe de complexité généralement considérée comme plus difficile que NP, correspondant à la difficulté de compter le nombre de solutions d'un problème de satisfaction de contraintes.

Méthodologie
L'auteur affine le mécanisme de preuve de dureté introduit par Wang et al. [5], qui utilisait des polynômes de Laurent pour récupérer la valeur de la coupe maximale à partir de l'exposant le plus grand. L'approche de l'auteur implique les étapes suivantes :

Construction de Graphe (Gadget de Comptage Équilibré) : Au lieu des gadgets asymétriques utilisés dans les travaux précédents, l'auteur construit un graphe spécifique $G(H)$ à partir d'un graphe d'entrée $H$ . Cette construction emploie :
- Gadgets de Variables : Pour chaque sommet de $H$ , un graphe biparti complet équilibré $K_{L,L}$ est créé, où $L = O(n)$ .
- Arêtes Synchrones : Des arêtes connectant les sommets correspondants des gadgets $K_{L,L}$ de sommets adjacents dans $H$ afin de préserver la structure originale du graphe.
- Sommets d'Ancrage : Deux sommets universels, $r$ et $s$ , connectés à tous les sommets des gadgets de variables et entre eux.
  Cette construction garantit que le graphe $G(H)$ possède un diamètre de 2 et que ses coupes maximales sont rigidement contraintes : les gadgets $K_{L,L}$ doivent être entièrement coupés, et les ancres doivent être sur des côtés opposés.
Analyse de Polynôme de Laurent : La valeur d'espérance du coût (ou un corrélateur spécifique de deux qubits $\langle Z_r Z_s \rangle$ ) est exprimée sous la forme d'un polynôme de Laurent en une variable de phase $z = e^{i\phi}$ . L'auteur analyse les coefficients de ce polynôme.
- Ils identifient un « coefficient extrême » correspondant à l'exposant de degré le plus élevé $D^*$ .
- À travers une analyse de « somme de chemins réduits », ils prouvent que le coefficient $a_{D^*}$ est non nul et directement proportionnel au nombre de coupes maximales du graphe original $H$ , noté $|\# \text{MC}(H)|$ .
- Plus précisément, $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ , où $\kappa$ est un facteur algébrique non nul connu dépendant des angles du mélangeur et de la taille du graphe.
Réduction par Interpolation : L'auteur démontre qu'en interrogeant l'oracle de la valeur d'espérance QAOA à un nombre polynomial de valeurs de phase distinctes (racines de l'unité), on peut utiliser la transformée de Fourier discrète inverse pour récupérer exactement les coefficients de Laurent. Puisque le coefficient extrême encode le compte des coupes maximales, un oracle capable d'évaluation exacte (ou d'une évaluation d'une précision exponentielle) permet de récupérer ce compte, établissant ainsi une réduction de Turing déterministe en temps polynomial du problème #P-difficile de comptage des coupes maximales vers le problème de l'évaluation des valeurs d'espérance QAOA.

Contributions Clés et Résultats

Dichotomie de Complexité : Le document établit une transition de complexité nette pour les valeurs d'espérance QAOA sur des graphes simples non pondérés :
- $p=1$ : Le problème appartient à FP (calculable en temps polynomial).
- $p \ge 2$ : Le problème est #P-difficile sous des réductions de Turing déterministes en temps polynomial.
Comptage vs Optimisation : Contrairement au résultat précédent sur la NP-difficulté qui récupérait la valeur de la coupe maximale, ce travail montre que l'évaluation de la valeur d'espérance permet de récupérer le nombre de coupes maximales. Cela élève la difficulté de l'optimisation au comptage.
Dureté Restreinte : La #P-difficulté se maintient même sous des restrictions significatives :
- Elle s'applique à l'évaluation d'un seul corrélateur de deux qubits désigné $\langle Z_r Z_s \rangle$ plutôt qu'à la fonction de coût globale.
- Elle est valable pour un ensemble très restreint de paramètres algorithmiques (angles de mélange fixes $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , et angles de coût liés $\gamma_1 = \gamma_2 = \phi$ ).
- Elle s'applique à des graphes de diamètre 2 (bien que ces graphes aient un degré élevé).
Dérivées et Hessiennes : L'auteur étend ces résultats pour montrer que le calcul exact des gradients et des Hessiennes de la fonction de coût QAOA par rapport aux paramètres est également #P-difficile.
Précision Exponentielle : La dureté s'étend au problème d'approximation de la valeur d'espérance avec une erreur additive exponentiellement petite ( $2^{-\alpha N}$ ), car cette précision est suffisante pour distinguer le coefficient extrême et récupérer le compte entier via l'arrondi.

Signification et Revendications
Le document affirme fournir une « classification exacte et propre de la complexité » pour les valeurs d'espérance de QAOA. La principale signification réside dans la démonstration que la transition de $p=1$ à $p=2$ n'est pas simplement un passage de la tractabilité à la difficulté d'optimisation (NP-difficile), mais un passage à la difficulté de comptage (#P-difficile).

L'auteur souligne que leurs résultats sont des énoncés de cas les plus défavorables concernant des familles spécifiques de graphes à haut degré et n'impliquent pas que l'évaluation de QAOA soit difficile pour tous les graphes ou pour des instances typiques. Ils notent que la dureté repose sur une évaluation exacte ou d'une précision exponentielle ; ils ne prétendent pas une dureté pour des erreurs additives constantes ou polynomialement petites, qui sont plus pertinentes pour les dispositifs quantiques actuels à échelle intermédiaire bruyante (NISQ).

De plus, le document distingue ses conclusions des résultats de suprématie quantique liés à l'échantillonnage. Alors que l'échantillonnage des sorties de QAOA à $p=1$ est déjà classiquement difficile sous certaines conditions, ce travail montre qu'évaluer la valeur d'espérance à $p=2$ est suffisant pour résoudre des problèmes de comptage #P-difficiles. L'auteur conclut que ses résultats impliquent que si l'on pouvait évaluer efficacement les valeurs d'espérance QAOA avec une précision exponentielle, la hiérarchie polynomiale s'effondrerait à son niveau le plus bas ($P=PH$). Cela a des implications pour les algorithmes hybrides qui reposent sur le traitement classique des valeurs d'espérance quantiques, suggérant que ces approches peuvent faire face à des barrières computationnelles fondamentales dans le pire des cas si une haute précision est requise.