Algorithme BHT - BHT algorithm
En informatique quantique , l' algorithme de Brasard-Hoyer-Tappar ou algorithme BHT est un algorithme quantique qui résout le problème de collision . Dans ce problème, on donne n et une fonction r à 1 et doit trouver deux entrées que f mappe à la même sortie. L'algorithme BHT ne fait que des requêtes à f , qui correspond à la limite inférieure de dans le modèle de boîte noire .
L'algorithme a été découvert par Gilles Brassard , Peter Hoyer et Alain Tapp en 1997. Il utilise l'algorithme de Grover , découvert l'année précédente.
Algorithme
Intuitivement, l'algorithme combine l'accélération de la racine carrée du paradoxe de l' anniversaire en utilisant le hasard (classique) avec l'accélération de la racine carrée de l'algorithme (quantique) de Grover.
Tout d'abord, n 1/3 entrées de f sont sélectionnées au hasard et f est interrogé sur chacune d'entre elles. S'il y a une collision entre ces entrées, nous renvoyons la paire d'entrées en collision. Sinon, toutes ces entrées correspondent à des valeurs distinctes par f . Ensuite, l'algorithme de Grover est utilisé pour trouver une nouvelle entrée à f qui entre en collision. Puisqu'il y a n entrées à f et n 1/3 de celles-ci formeraient une collision avec les valeurs déjà interrogées, l'algorithme de Grover peut trouver une collision avec des requêtes supplémentaires à f .
