BQP
From Wikipedia, the free encyclopedia
En théorie de la complexité des algorithmes, BQP (bounded error quantum polynomial time) est la classe des problèmes de décision qui peuvent être résolus par un calculateur quantique en un temps polynomial, avec une probabilité d'erreur d'au plus 1/3 dans tous les cas. Elle est le pendant quantique de la classe classique de complexité BPP.
De même que pour les autres classes de complexité probabilistes à erreur bornée, le choix de la probabilité 1/3 d'erreur est arbitraire. On peut exécuter l'algorithme un nombre constant de fois, et prendre la majorité des votes pour obtenir n'importe quelle probabilité de réussite désirée, en utilisant les inégalités de Chernoff. Une analyse détaillée montre que la classe de complexité reste inchangée en autorisant un risque d'erreur inférieur à 1/2 − n−c d'une part, et supérieur à 2−nc d'autre part, c étant une constante positive quelconque et n la longueur des données en entrée de l'algorithme.
