Quantum Approximation Complexity of Classical Optimization Problems

Titre : Complexité d'approximation quantique des problèmes d'optimisation classiques
Auteur : Stuart Hadfield

Énoncé du problème

L'article traite de l'absence de garanties rigoureuses de performance dans le pire des cas pour les algorithmes d'optimisation quantique. Bien que de nombreuses méthodes quantiques (par exemple, QAOA, DQI) affichent des scores élevés sur des instances spécifiques ou fournissent des bornes sur les valeurs attendues (moyennes décodées), elles manquent souvent d'algorithmes uniformes qui garantissent un ratio d'approximation spécifique pour chaque entrée avec une erreur bornée. Le travail cherche à définir formellement des analogues quantiques aux classes de complexité d'approximation classiques (APX, PTAS, FPTAS) et à déterminer si le calcul quantique peut strictement s'améliorer par rapport aux algorithmes classiques randomisés en termes de qualité de solution garantie ou du temps requis pour atteindre une précision demandée.

Méthodologie

L'auteur étend le cadre des problèmes d'optimisation NP (NPO) pour inclure les algorithmes quantiques à erreur bornée.

1. Définition des classes quantiques : L'article définit BQ-APX, BQ-PTAS et BQ-FPTAS. L'appartenance à ces classes nécessite un algorithme quantique uniforme qui, pour chaque entrée, retourne une solution classique réalisable atteignant le ratio d'approximation revendiqué avec une probabilité d'au moins $2/3$. Crucialement, le temps d'exécution inclut toutes les étapes : sélection des paramètres, préparation de l'état, mesure, décodage et répétition. Le score de la solution doit être efficacement calculable classiquement.
2. Transfert de la moyenne décodée vers la sortie : Un outil technique clé est le Lemme 6 et le Corollaire 7, qui établissent une relation entre le score attendu d'une solution décodée et une garantie de sortie classique à erreur bornée. Cela permet de traduire les analyses basées sur l'espérance (courantes dans la littérature quantique) en garanties de sortie strictes requises pour l'appartenance à une classe.
3. Séparations conditionnelles : L'article construit des problèmes spécifiques pour démontrer des inclusions strictes entre les classes quantiques et classiques sous des hypothèses de complexité standard (par exemple, $NP \not\subseteq BQP$ et $Factor \notin FBPP$). Ces constructions reposent sur le « padding de recherche » (search padding) et la dureté cryptographique.

Contributions clés et résultats

1. Hiérarchie formelle des classes d'approximation quantiques
L'article établit une hiérarchie stricte pour les classes d'approximation quantiques sous l'hypothèse que $NP \not\subseteq BQP$ :
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
Cette hiérarchie est illustrée par des problèmes classiques :

• Max-E3SAT : Possède une approximation déterministe à ratio constant (dans APX) mais aucun PTAS quantique.
• Vertex Cover Planaire : Possède un PTAS déterministe mais aucun FPTAS quantique.
  Ces résultats montrent que les classes quantiques sont distinctes les unes des autres, bien qu'elles ne séparent pas encore les classes quantiques des classes classiques randomisées pour ces problèmes spécifiques.

2. Ordre Maximum Certifié (CMO) : Une forte séparation Quantique–Classique
L'article introduit le problème de l'Ordre Maximum Certifié (CMO), où l'objectif est de trouver l'ordre multiplicatif d'un élément modulo $N$ qui est certifié par une factorisation première de l'ordre.

• Résultat Quantique : Un algorithme quantique à erreur bornée peut trouver l'optimum exact (la fonction de Carmichael $\lambda(N)$) en temps polynomial en utilisant la factorisation et la recherche de période. Ainsi, $CMO \in BQ\text{-}FPTAS$.
• Barrière Classique : Tout algorithme polynomial en temps randomisé garantissant même un ratio d'approximation de facteur polynomial pour CMO impliquerait un algorithme de factorisation en temps polynomial randomisé.
• Conclusion : En supposant que $Factor \notin FBPP$, $CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$. Cela établit une séparation conditionnelle où les algorithmes quantiques fournissent des solutions exactes tandis que les algorithmes classiques randomisés ne peuvent même pas atteindre des approximations de facteur polynomial.

3. Ajustement de Logarithme Discret (DLog-Fit) : Une séparation de seuil
L'article définit DLog-Fit, un problème impliquant la prédiction de labels sur un échantillon basé sur des logarithmes discrets.

• Référence Classique : Un algorithme déterministe atteint une approximation de $1/2$ (prédiction de la majorité des labels).
• Avantage Quantique : Un algorithme quantique peut trouver un ajustement parfait (optimum exact).
• Barrière Classique : Toute amélioration fixe par rapport au ratio de $1/2$ par un algorithme classique randomisé résoudrait le problème du logarithme discret dans un sous-groupe de nombres premiers sûrs.
• Conclusion : Sous l'hypothèse que le logarithme discret de nombres premiers sûrs n'est pas dans $FBPP$, $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$. Cela démontre un écart au seuil d'approximation de $1/2$.

4. Padding de recherche général (Théorème 8)
L'article fournit une construction générique montrant que tout problème de recherche avec des témoins (witnesses) efficacement vérifiables peut être transformé en un problème NPO avec un seuil d'approximation de $1/2$. Si un solveur quantique existe pour la recherche mais qu'un solveur classique randomisé ne l'est pas, le problème d'optimisation résultant appartient à $BQ\text{-}FPTAS$ mais est en dehors de $R\text{-}PTAS$.

5. Analyse des méthodes quantiques existantes
L'article applique ces définitions à des algorithmes existants :

• QAOA : Pour un QAOA de profondeur fixe sur MaxCut 3-régulier, l'article utilise le transfert de la moyenne décodée pour montrer que la répétition peut produire une garantie de sortie à erreur bornée (par exemple, dépassant $2/3$ de l'optimum), plaçant cette famille de graphes spécifique dans $BQ\text{-}APX$.
• Interférométrie Quantique Décodée (DQI) : L'article note que bien que la DQI montre des scores d'espérance améliorés sur des familles spécifiques (comme l'OPI replié), établir une séparation dans le modèle de temps d'entrée explicite nécessite de prouver que les algorithmes classiques randomisés ne peuvent pas atteindre le même ratio, ce qui reste un défi ouvert pour les problèmes non restreints.

Signification et Revendications

L'article affirme fournir les premières définitions rigoureuses des classes d'approximation quantiques à erreur bornée et prouver que, sous des hypothèses de complexité explicites, le calcul quantique peut strictement améliorer les garanties d'approximation dans le pire des cas par rapport au calcul classique randomisé.

• Portée Modeste : L'auteur déclare explicitement que pour les problèmes courants et non restreints comme MaxCut ou MaxSAT, un écart quantique-classique dans les ratios d'output dans le pire des cas reste ouvert. Les séparations établies reposent sur des constructions de problèmes spécifiques, souvent cryptographiques (CMO, DLog-Fit), ou sur des familles de graphes restreintes.
• Cadre Théorique : Le travail comble le fossé entre la performance quantique heuristique (souvent mesurée par des valeurs d'espérance) et la théorie de la complexité rigoureuse (garanties de sortie à erreur bornée). Il clarifie que des scores de benchmark élevés ne suffisent pas à établir l'appartenance à une classe d'approximation sans uniformité et bornes de temps d'exécution.
• Direction Future : L'article identifie la recherche d'un algorithme quantique uniforme garantissant un ratio meilleur que le seuil de dureté classique pour les problèmes standards (comme MaxCut non restreint) comme le problème central ouvert du domaine.