algorithme de Grover

En informatique quantique, l’algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi éléments non classés en temps proportionnel à et avec un espace de stockage proportionnel à . Il a été découvert par Lov Grover en 1996. Dans les mêmes conditions (recherche parmi des éléments non classés), un algorithme classique ne peut faire mieux qu'une recherche dans un temps proportionnel à , en testant successivement le critère sur chaque élément. L'étendue de la gamme de critères pouvant être utilisée par cet algorithme lui donne un caractère universel, ce qui en fait un des algorithmes les plus importants et potentiellement le plus utile de l'informatique quantique. L'exemple classique d'utilisation de cet algorithme est la recherche, dans un annuaire téléphonique ordinaire classé alphabétiquement, du nom qui correspond à un numéro de téléphone donné. L'algorithme de Grover fonctionne toujours en lui présentant les nombres entiers de 1 à N, représentant dans le cas de l'annuaire une position dans ce dernier. Le critère de sélection est dans ce cas : la position correspond à un numéro de téléphone donné. La position étant connue, on en déduit le nom ou toute autre information liée à la position. Plus généralement, l'ensemble des nombres entiers de 1 à N peut indexer un ensemble de solutions possibles à un problème. Dans ce cas, s'il est possible de vérifier rapidement qu'une solution résout un problème (ce qui est généralement le cas, et ce qui définit même toute une classe importante de problèmes dits de complexité NP), alors il est possible à l'aide de cet algorithme d'accélérer notablement la recherche des solutions de ces problèmes par rapport à une « recherche brute ». Parmi les problèmes NP (et même NP-Complet) qui pourraient être résolus par cet algorithme se trouvent notamment : * le problème SAT ; * la coloration de graphe ; * la détermination d'un chemin hamiltonien dans un graphe ; * des puzzles, cryptographiques comme « SEND+MORE=MONEY », ou numériques comme le sudoku. Malgré tout, ce genre de problème est souvent de complexité exponentielle par rapport au nombre d'éléments du problème (typiquement, si n est le nombre d'éléments mis en jeu dans le problème). Même si cet algorithme apporte une optimisation non négligeable (quadratique) par rapport à une recherche brute, il transforme un problème de complexité en , qui demeure exponentielle. Certains algorithmes classiques, adaptés à un problème particulier, peuvent faire mieux, surtout si on tolère une solution approximative, ou probabiliste. Mais cet algorithme présente le double avantage d'être généraliste (dès que l'on a l'algorithme pour vérifier une solution, on a automatiquement l'algorithme pour trouver la solution), et de garantir de trouver la ou les solution(s) optimale(s). Il a été prouvé en 1999, par , que l'algorithme de Grover est l'algorithme quantique le plus efficace pouvant traiter le problème de la recherche non structurée. Il est impossible de faire mieux qu'une amélioration quadratique de la complexité, en utilisant le parallélisme du calcul quantique.