Source vérifiéeNiveau 3

QAOA (algorithme quantique d'optimisation approchée)

QAOA est un algorithme hybride quantique-classique pour l'optimisation combinatoire : des couches de coût et de mélange alternent, un optimiseur classique règle les paramètres.

Ce que cela signifie

À partir de |+>^n, p couches alternent l'évolution sous le hamiltonien de coût exp(-i*gamma*C) et sous le mélangeur exp(-i*beta*B).Un optimiseur classique règle les 2p angles pour maximiser l'espérance de C.Quand p croît, la qualité d'approximation ne diminue pas ; à la limite p infini, QAOA rejoint l'algorithme adiabatique.

Analogie du quotidien

C'est comme pétrir une pâte en plusieurs tours : on presse vers la forme voulue (couche de coût), puis on plie et mélange (couche de mélange) -- après quelques tours, la pâte est bien plus proche de la forme demandée.
L'optimiseur classique est l'entraîneur, le circuit quantique l'athlète : l'entraîneur regarde le score et ajuste les réglages.

Idées reçues fréquentes

  • Aucune garantie de battre les algorithmes classiques -- pas d'accélération générale prouvée pour l'optimisation combinatoire.
  • À profondeur p finie, QAOA est approché -- pas d'optimum certifié.
  • Pas purement quantique : boucle hybride avec optimiseur classique.

À retenir

  • Alterne p couches de coût et de mélange depuis |+>^n.
  • L'optimiseur classique règle 2p angles.
  • Qualité non décroissante en p ; lien avec l'algorithme adiabatique.

Vérifiez votre compréhension

Quelles deux opérations alternent dans chaque couche QAOA ?

  1. A.Oracle et diffusion
  2. B.Évolution du hamiltonien de coût et du mélangeur
  3. C.QFT et QFT inverse
  4. D.Encodage et correction d'erreurs
Voir la réponse

Réponse: B. Évolution du hamiltonien de coût et du mélangeur

Pourquoi: Évolution sous C puis sous B, angles réglés classiquement.

S’appuie sur

QubitSuperpositionMesure quantiqueCalcul hybride quantique-classiqueSolveur variationnel quantique (VQE)

Source primaire: Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014)

Graded 2026-07-10 (human sign-off): established per Farhi, Goldstone, Gutmann arXiv:1411.4028 (2014).

Apprendre en pratiquant

Ce concept fait partie d’un cursus de 46 niveaux, avec un simulateur interactif et Lumen — un tuteur dont les réponses sont vérifiées avant affichage. Les niveaux 1–5 sont gratuits.

Commencer gratuitementVoir le cursus