BQP

Les relations supposées entre BQP et les autres classes de complexité^[1].

En théorie de la complexité des algorithmes BQP (Bounded error Quantum Polynomial time) est la classe des problème de décision qui peuvent être résolus par un calculateur quantique en un temps polynômial, 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, dites en "bounded error", 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.

Calcul quantique

La classe de complexité BQP est l'objet d'études intensives car certains problèmes présentant un intérêt pratique sont démontrés dans BQP, mais sont supposés en dehors de P (classe des problèmes qui peuvent être résolus par l'informatique classique en un temps polynômial).

Parmi les exemples les plus significatifs :

• La décomposition en produit de facteurs premiers (voir Algorithme de Shor) ^[2]
• les logarithmes discrets^[2]
• La simulation de systèmes quantiques
• Calcul des polynômes de Jones pour certaines racines de l'unité.

Références

1. ↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
2. ↑ ^{a et b} arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor