Les ordinateurs quantiques
Algorithmes quantiques
Avec la mécanique qui vient d'être décrite pour entrer une fonction, certains ont proposé des algorithmes qui résolvent des problèmes absolument sans intérêt, mais bien plus vite que ne pourrait le faire un ordinateur classique.
L'oracle de Deutsch est le plus connu, et consiste à détecter, en une passe, si une fonction est balancée ou non, c'est-à-dire si elle est constante (par exemple f0 et f3) ou non (f1 et f2). On entre la fonction dans la boite, puis en une passe, on a la réponse. Super. Un ordinateur classique devra au moins faire deux passes, forcément, ce gros nul.
Algorithme d'identification de fonction : on met une fonction binaire à deux entrées dans la boite noire, et en une passe, on devine laquelle. L'ordinateur classique en est incapable.
Dans les deux cas, il aura fallu ajouter un peu de "sauce" autour de la fonction pour extraire correctement la réponse : c'est un principe général, il faut préparer correctement, puis exploiter les sorties de manière à extraire le résultat désiré.
Si ça vous intéresse vraiment, vous trouverez facilement de la documentation là-dessus. Il existe même un zoo des algorithmes quantiques : http://quantumalgorithmzoo.org/
On va plutôt se pencher sur ceux qui ont (habituellement) plus d'intérêt, à savoir : chercher dans une base de données ou factoriser.
Mais avant, on va regarder quelques fonctions qui seront bien utiles.