Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

Résumé technique : Coût de tolérance aux fautes du QAOA de faible profondeur sur les problèmes d'optimisation quasi-symétriques

Énoncé du problème
Montanaro et Zhou [1] ont démontré que les circuits QAOA de profondeur un peuvent trouver la solution plantée de certains problèmes de satisfaction de contraintes (CSP) quasi-symétriques avec une probabilité constante $\Omega(1)$. En revanche, les réalisations explicites de ces problèmes présentent une apparente complexité temporelle exponentielle pour les solveurs classiques puissants. Bien que cela suggère un avantage exponentiel empirique, les ressources nécessaires pour implémenter ces circuits sur les premiers ordinateurs quantiques tolérants aux fautes restent incertaines. Les Hamiltoniens de coût pour ces problèmes contiennent $\Theta(n^\ell)$ clauses (où $\ell \ge 5$), ce qui implique un nombre de portes non-Clifford de l'ordre de $\tilde{O}(n^\ell)$ lors de la compilation par synthèse Clifford+T standard. Cette mise à l'échelle place les tailles de problèmes pertinentes hors de portée du matériel tolérant aux fautes de première génération.

Méthodologie
Les auteurs analysent le coût des ressources de tolérance aux fautes des circuits QAOA de profondeur un appliqués à ces instances quasi-symétriques, en se concentrant spécifiquement sur la synthèse de la couche de séparation de phase. L'analyse procède en trois étapes principales :

1. Adaptation de phase et mise à l'échelle de l'angle : Les auteurs réexaminent la condition d'adaptation de phase requise pour une probabilité de succès constante. Pour les fonctions de coût symétriques sous les permutations de variables par rapport à une solution plantée, l'angle de séparation de phase $\gamma$ doit évoluer comme $\gamma = \Theta(n^{1-\ell})$ pour assurer l'interférence constructive des coquilles de Hamming dominantes.
2. Synthèse de petits angles : En tirant parti du fait que $\gamma$ diminue avec la taille du système, les auteurs appliquent des techniques de synthèse Clifford+T pour petits angles (spécifiquement celles de Bothe et al. [9]). Ils utilisent des formulations de probabilité quasi-réelle et de mélange de probabilités où les rotations de petits angles sont approximées par l'identité avec une haute probabilité, et seule une petite fraction des rotations nécessite une synthèse non-Clifford.
3. Compilation explicite des clauses et analyse de fuite : Les auteurs passent du modèle d'oracle de valeur (où seules les valeurs du coût $C(x)$ sont interrogées) à un modèle de liste de clauses explicite requis pour la compilation de circuits. Ils analysent les coefficients de Fourier de la fonction de coût dérivée de la liste de clauses explicite pour déterminer si le processus de compilation révèle par inadvertance la solution.
4. Construction d'instances trompeuses : Pour tester la robustesse de l'accélération face aux attaques classiques exploitant la structure explicite, les auteurs construisent des instances quasi-symétriques « non-plantées ». Ces instances présentent une coquille de Hamming optimale exponentiellement grande contenant un sous-problème NP-difficile, avec un paysage de coût conçu pour piéger les algorithmes de recherche locale.

Contributions clés et résultats

• Mise à l'échelle non-Clifford quadratique : Le résultat principal est que le coût non-Clifford par circuit pour le QAOA de profondeur un sur ces instances se réduit à $\tilde{O}(n^2)$, indépendamment de la localité des clauses $\ell$ et du taux de sparsification. Cette réduction se produit car la masse de phase totale ($m\gamma$, où $m$ est le nombre de clauses) évolue linéairement avec $n$, et les coûts de synthèse des petits angles dépendent du carré de cette masse de phase. Par conséquent, les tailles de problèmes auparavant jugées irréalisables en raison d'une mise à l'échelle $\tilde{O}(n^\ell)$ deviennent viables sur les dispositifs tolérants aux fautes précoces (voir Fig. 2).
• Fuite classique dans les familles plantées : Pour les familles plantées étudiées dans la réf. [1], les auteurs montrent que la liste explicite des clauses requise pour la compilation expose la solution plantée. La condition d'adaptation de phase ($F'(1/2) \neq 0$) fixe les signes des coefficients de Fourier de degré un (champs locaux) de la fonction de coût. Ces signes révèlent directement la solution plantée $s$ via un balayage linéaire du temps de la liste de clauses. Ainsi, bien que le QAOA réussisse avec une probabilité constante, l'implémentation explicite rend le problème classiquement trivial.
• Existence d'instances non-plantées difficiles : Les auteurs démontrent que le régime des petits angles et la mise à l'échelle du coût en $\tilde{O}(n^2)$ ne sont pas contingents à l'existence d'une solution plantée. Ils construisent des instances quasi-symétriques sans solution plantée où :
  • L'optimum global se situe dans une coquille de Hamming exponentiellement grande.
  • Trouver l'optimum exact dans cette coquille est NP-difficile.
  • Le paysage de coût est « trompeur », piégeant les algorithmes de recherche locale et les solveurs MaxSAT généralistes dans des secteurs sous-optimaux séparés par des barrières énergétiques élevées.
  • Le QAOA de profondeur un au petit angle concentre son résultat sur la coquille optimale avec le même coût non-Clifford de $\tilde{O}(n^2)$.
  • Dans ces cas non-plantés, les coefficients de degré un sont uniformes et ne révèlent pas la solution, préservant la difficulté pour les algorithmes classiques qui n'exploitent pas la structure de symétrie spécifique.

Signification
Cet article établit que l'accélération empirique du QAOA de faible profondeur sur les problèmes quasi-symétriques peut être réalisée avec des ressources de tolérance aux fautes nettement inférieures à ce qui était précédemment supposé, spécifiquement $\tilde{O}(n^2)$ portes non-Clifford plutôt que $\tilde{O}(n^\ell)$. Cela fait de ces circuits de faible profondeur et de petits angles une cible réaliste pour le matériel tolérant aux fautes précoce.

Cependant, les auteurs notent modestement un compromis critique : le mécanisme qui permet la synthèse de petits angles (champs locaux cohérents) expose simultanément la solution aux attaques classiques dans les scénarios plantés. La signification de ce travail réside dans l'identification d'un régime où le QAOA de faible profondeur offre une voie efficace en ressources pour l'optimisation, tout en soulignant que les propriétés structurelles spécifiques permettant cette efficacité peuvent être une arme à double tranchant. Les auteurs concluent que la question centrale est de savoir si ce régime de « petits angles peu coûteux » peut être étendu à des circuits plus profonds ou à des structures de problèmes différentes où la solution reste cachée des attaques classiques de bas degré, réalisant ainsi un véritable avantage quantique qui soit à la fois peu coûteux en termes de tolérance aux fautes et résistant aux algorithmes classiques.