Quantum Approximate Optimization Algorithm

Le Quantum Approximate Optimization Algorithm (QAOA) est un algorithme hybride quantique-classique conçu pour trouver des solutions approximatives aux problèmes d'optimisation combinatoire. Il est particulièrement adapté aux problèmes qui peuvent être formulés comme la recherche du minimum d'une fonction de coût sur un ensemble discret de variables, tels que le problème Max-Cut ou le problème du voyageur de commerce. Le QAOA fonctionne par couches, alternant entre l'application d'un 'problem Hamiltonian' (qui encode la fonction de coût) et d'un 'mixer Hamiltonian' (qui permet l'exploration de l'espace des solutions). Les paramètres contrôlant la durée ou la force de ces applications Hamiltoniennes sont des variables classiques qui sont optimisées itérativement. Un ordinateur classique est utilisé pour préparer l'état quantique, exécuter le circuit quantique pour un ensemble donné de paramètres, mesurer l'état résultant pour estimer la valeur de la fonction de coût, puis mettre à jour les paramètres à l'aide d'une routine d'optimisation classique (par exemple, gradient descent). Ce processus se répète jusqu'à ce que les paramètres convergent, fournissant une solution approximative. Le QAOA est considéré comme un algorithme quantique à court terme (near-term), ce qui signifie qu'il est conçu pour fonctionner sur des appareils quantiques actuels ou futurs à échelle intermédiaire bruyants (NISQ). Son efficacité dépend de la profondeur du circuit (nombre de couches) et de la qualité de l'optimiseur classique.