Y a-t-il une classe QPP de classe complexité?

Question

La classe de complexité PP n'est pas considérée comme tractable, car la probabilité de succès peut devenir arbitrairement proche de 50% d'en haut, car les instances problématiques sont plus grandes, de sorte que (par exemple, si cette approche est exponentielle rapide) un nombre infaisable de répétitions peutêtre nécessaire avant que nous ayons une probabilité de distinguer en toute confiance les intrants satisfaisants de ceux non satisfaisants.Néanmoins, PP est une classe de complexité intéressante à étudier à part entière.

Y a-t-il une classe de complexité bien définie similaire "QPP" de problèmes qu'un ordinateur quantique a une chance supérieure à 50% de résolution correctement en temps polynomial?Je comprends que, dans l'affirmative, cette classe de problèmes ne serait pas réalisable sur un ordinateur quantique, mais des inclusions non sévères avec les classes de complexité les plus «traditionnelles» prouvées ou suspectées?Comment "Big" pensons-nous que la classe QPP est?

Answer 1

Yamakami a montré dans leur papier Analyse des fonctions quantiques que l'analogique quantiquede PP est la même chose que le PP classique.Ceci est mentionné dans le Article Wikipedia sur pp.