Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Grover
Résumé
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 à la recherche brute.
Parmi les problèmes dans 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Cours associés (12)
COM-611: Quantum Information Theory and Computation
Today one is able to manipulate matter at the nanoscale were quantum behavior becomes important and possibly information processing will have to take into account laws of quantum physics. We introduce
PHYS-454: Quantum optics and quantum information
This lecture describes advanced concepts and applications of quantum optics. It emphasizes the connection with ongoing research, and with the fast growing field of quantum technologies. The topics cov
MATH-646: Reading group in quantum computing
Quantum computing has received wide-spread attention lately due the possibility of a near-term breakthrough of quantum supremacy. This course acts as an introduction to the area of quantum computing.