Algorithme de Deutsch-Jozsa

L'algorithme de Deutsch-Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998. Bien qu'il ne soit pas d'un grand intérêt pratique, il s'agit d'un des premiers algorithmes quantiques qui est plus efficace qu'un algorithme classique. Dans le cas du problème de Deutsch-Jozsa, nous disposons d'une boîte noire quantique, connu sous le nom d'oracle qui implémente une fonction mathématique . Nous savons que cette fonction est soit constante (la sortie est 0 ou 1 pour toutes les entrées) soit équilibrée (la sortie est 0 dans la moitié des cas, 1 dans les autres). Le but du problème est de savoir si la fonction est constante ou équilibrée à l'aide de l'oracle. Si un algorithme classique et déterministe est utilisé, il faut évaluations de la fonction mathématique dans le pire des cas pour être certain de trouver la solution (c'est-à-dire tester la moitié des entrées possibles, plus une) tel qu'expliqué ci-dessous. La fonction accepte entrées que nous nommerons avec . Tester la fonction sur un seul cas d'entrée (par exemple ) ne permet évidemment pas de conclure. Mais cela fournit un premier résultat qui servira de référence. Calculons maintenant . Dans le meilleur des cas, le résultat est différent de et nous pouvons immédiatement conclure que la fonction est équilibrée, sans avoir besoin d'aller plus loin. Sinon, nous ne pouvons rien conclure et il convient de calculer . Et ainsi de suite... Dans le pire des cas, nous arrivons au point où la moitié des valeurs possibles en entrée ont été testées et elles ont toutes retourné le résultat . Nous ne pouvons toujours pas conclure puisque cette proportion de résultats identiques est possible que la fonction soit constante ou équilibrée ! Par contre, dès le test sur la valeur d'entrée suivante : Si le résultat est identique à alors il est certain que la fonction est constante Si le résultat est différent de alors il est certain que la fonction est équilibrée Nous voyons donc que, dans le pire des cas, le nombre d'évaluations de à réaliser est de "la moitié des cas possibles plus un", soit .