Algorithmes d'approximation quantique

Il est généralement considéré comme peu probable que les ordinateurs quantiques soient capables de résoudre efficacement des problèmes NP-complets. Dans le cas classique, une approche pour résoudre ces problèmes consiste à utiliser des algorithmes d'approximation. Y a-t-il eu des recherches sur les algorithmes d'approximation utilisant l'informatique quantique où la quanticité donne une accélération significative par rapport aux méthodes d'approximation classiques?

Par «significatif», je veux dire pas nécessairement exponentiel, mais supérieur à celui des algorithmes exacts correspondants. En d'autres termes, je suis intéressé si l'assouplissement de l'exigence que notre algorithme donne la solution exacte donne un avantage significatif aux algorithmes quantiques.

Un commentaire mis à niveau vers une réponse partielle:

Il y a beaucoup de travail de nos jours sur une version quantique conjecturée (ou non) du théorème du PCP: voir par exemple ce billet de blog de Scott Aaronson http://www.scottaaronson.com/blog/?p=139 ou cette réponse de Peter Shor sur MathOverflow /mathpro/45106/quantum-pcp-theorem/45167#45167

Concernant les algorithmes d'approximation quantique, vous pouvez consulter cette référence "Algorithmes d'approximation pour les problèmes QMA-complets" http://arxiv.org/abs/1101.3884

Personnellement, je ne connais aucun travail dans le sens d' algorithmes d'approximation quantique dans le sens d'approximations relatives (vs approximations additives) (bien que cela ne signifie pas nécessairement qu'elles n'existent pas).

Notez que si votre intention est de concevoir des algorithmes approximatifs quantiques poly-temps pour, disons, des problèmes NP-difficiles, de nombreux problèmes comme MAX-CUT ont déjà des algorithmes approximatifs classiques serrés (en supposant la conjecture des jeux uniques ou par PCP). Il est donc probablement logique de commencer par étudier un problème présentant un écart entre le rapport d'approximation connu et les résultats de dureté.

L'autre direction est la dureté de l'approximation - voir par exemple http://arxiv.org/abs/0811.3412 et http://arxiv.org/abs/1012.3319 pour les progrès positifs et négatifs partiels concernant un éventuel théorème PCP quantique.

Une sorte de réponse triviale, mais il y a estimation de la probabilité d'acceptation d'un circuit quantique, ou de l'un des problèmes équivalents, tels que l'approximation du polynôme de Jones, ou la solution d'un système linéaire d'équations, ou la trace d'une puissance d'un grande matrice clairsemée.

De plus, le comptage approximatif accélère de nombreux algorithmes d'approximation basés sur l'échantillonnage.

$i$