Les ordinateurs quantiques
Algorithmes quantiques
Avant d'attaquer les algorithmes vraiment intéressants, nous allons nous pencher sur deux fonctions qui ont l'air secondaires, mais non, elles seront fondamentales.
Ces fonctions utiles montrent la différence avec les ordinateurs classiques. L'inversion d'amplitude permet d'exploiter les nombres complexes, et la symétrie par rapport à la moyenne est carrément une fonction géniale totalement inexistante dans l'informatique classique.
Inversion d'amplitude
Si vous êtes informaticien, alors votre esprit sera bloqué sur le binaire : seuls 0 et 1 existent. On vient de voir qu'on pouvait entrer des fonctions booléennes dans nos qubits, et oh joie ineffable nous avons manipulé des zéros et des uns un truc compréhensible au moins.
Mais c'est oublier la nature de nos matrices : ça tombe bien que ce soit 0 et 1, on l'a fait un peu exprès, mais en réalité, ce sont des nombres complexes le rappel qui tue. Non seulement on se pèle une partie imaginaire, mais on peut avoir n'importe quelle valeur en amplitude, en particulier négative oh non, tout mais pas ça. Et tout ça sur le même qubit. Eh bien il faut en tirer avantage !
Avouez que vous ne l'aviez pas vu venir, celle-là. Une amplitude négative...
Et oui, le carré d'un négatif, c'est positif.
Une fonction commode est la fonction qui va inverser l'amplitude pour une ou plusieurs valeurs particulières de x, toutes les autres resteront pareilles. Ce seront les valeurs pour lesquelles f(x)=1. Quand f(x)=0, on n'inverse pas. En voici l'illustration graphique qui évite la maudite sphère de Bloch, vous êtes vernis:
sélectionnées par la fonction Vf.
Bon, pour l'instant on dirait une facétie de physicien quantique. Et effectivement, tout seul, ça n'a pas grand intérêt, puisque cela donnera exactement la même probabilité, vu que le carré d'un négatif, et bien c'est positif...
Symétrie par rapport à la moyenne
Une autre fonction qu'elle est bien, c'est la symétrie par rapport à la moyenne (inversion about average).
On calcule la moyenne des amplitudes, puis on effectue la symétrie par rapport à cette moyenne. C'est assez facile à comprendre graphiquement sur le résultat de l'opération précédente :
Les valeurs vertes, très négatives, deviennent très positives.
Cette fois, on voit que l'on a augmenté salement la probabilité d'apparition par rapport aux autres. Eh bien sûr que ça marche mieux si le nombre des amplitudes négatives est faible, en tous cas que la moyenne ne soit pas nulle sinon c'est con.
Vous devez commencer à voir venir l'utilisation qu'on peut en faire. Et surtout, la différence de raisonnement par rapport à un informaticien classique, qui est à mille lieux de percuter comment ça marche.