# Quantum Supremacy through the Quantum Approximate Optimization Algorithm

**Authors:** Edward Farhi, Aram W Harrow  
**arXiv:** [1602.07674](https://arxiv.org/abs/1602.07674)  
**Date:** 2016-02-24  
**Summary page:** https://www.summarizepaper.com/fr/arxiv-id/1602.07674v1/

## Key points

- L'Algorithme d'Optimisation Approximative Quantique (QAOA) a été développé par les auteurs Edward Farhi et Aram W Harrow.
- Conçu pour fonctionner sur un ordinateur quantique de modèle à portes avec une faible profondeur.
- Le QAOA prend en entrée un problème d'optimisation combinatoire et génère une chaîne satisfaisant une grande fraction du nombre maximal de clauses pouvant être satisfaites.
- La version de plus faible profondeur du QAOA offre des garanties de performance prouvées pour certains problèmes, bien que des algorithmes classiques offrent de meilleures garanties.
- Le QAOA pourrait démontrer une forme de Suprématie Quantique, car la distribution des résultats même de sa version à faible profondeur ne peut pas être simulée efficacement sur un dispositif classique selon des hypothèses théoriques complexes raisonnables.

## Summary

Les auteurs Edward Farhi et Aram W Harrow ont développé l'Algorithme d'Optimisation Approximative Quantique (QAOA), conçu pour fonctionner sur un ordinateur quantique de modèle à portes et ayant une faible profondeur. Ce programme prend en entrée un problème d'optimisation combinatoire et génère une chaîne qui satisfait une grande fraction du nombre maximal de clauses pouvant être satisfaites. Pour certains problèmes, la version de plus faible profondeur du QAOA offre des garanties de performance prouvées, bien que des algorithmes classiques offrent de meilleures garanties. Les chercheurs avancent que le QAOA peut démontrer une forme de Suprématie Quantique, car selon des hypothèses théoriques complexes raisonnables, la distribution des résultats même de la version de plus faible profondeur ne peut pas être simulée efficacement sur un dispositif classique. Cette affirmation est mise en contraste avec l'échantillonnage des résultats d'un ordinateur quantique exécutant l'Algorithme Adiabatique Quantique (QADI) avec la restriction que l'hamiltonien gouvernant l'évolution soit gapé et stoquastique. Il est démontré qu'il existe un oracle permettant d'échantillonner à partir du QADI, mais même avec cet oracle, si l'on pouvait échantillonner efficacement les résultats du QAOA de manière classique, la Hiérarchie Polynomiale s'effondrerait. Cela suggère que le QAOA est un excellent candidat pour être exécuté sur des ordinateurs quantiques à court terme non seulement pour son utilité en matière d'optimisation, mais aussi pour son potentiel en tant que voie vers l'établissement de la suprématie quantique.