2.3 Complexité d'un algorithme quantique:
On parle «d'accélérer des algorithmes
classiques», mais encore faut-il se donner un moyen de mesurer
effectivement la complexité d'un algorithme quantique. Rappelons que
dans le cas d'un algorithme classique, la complexité mesure en temps :
on estime le temps mis par l'algorithme sur une entrée de taille n,
asymptotiquement. Cela revient à compter le nombre d'opérations
«atomiques» réalisées au cours d'une exécution.
Les algorithmes polynômiaux en n sont considérés comme
étant utilisables en pratique, alors que les exponentiels mettraient
beaucoup trop de temps sur des entrées, même petites, pour
être utiles.
Sur un ordinateur quantique, on mesure de même le temps
d'exécution. On va utiliser le résultat de de la proposition
d'universalité : on considère que l'application de CNOT ou d'un
opérateur agissant sur un 1-qubit se fait en temps constant. Une mesure
prend également un temps constant. Ainsi, lorsqu'on dispose d'un circuit
quantique, on établit sa complexité en décomposant chaque
opérateur en CNOT et en opérations de 1-qubit, puis on compte.
Dans toute la suite, les opérateurs agissant sur les n-qubits se
décomposent en un nombre polynômial en n de portes de base. Ainsi,
compter un nombre polynômial de ces portes quantiques ou des portes de
base est équivalent. On ne se souciera donc plus de ce détail de
définition, et on comptera directement les opérateurs agissant
sur des n-qubits. L'aspect pratique des algorithmes polynômiaux à
opposer aux exponentiels reste évidemment le même : un algorithme
polynômial serait assez rapide si un ordinateur quantique
l'exécutait, alors qu'un exponentiel serait trop long sur des
entrées de taille usuelle.
| 
