L'algorithme de Grover, publié par Lov Grover en 1996, offre une accélération quadratique pour la recherche non structurée. Pour un espace de recherche de N éléments, la recherche classique nécessite O(N) requêtes tandis que celui de Grover n'en nécessite que O(√N). L'algorithme fonctionne en appliquant de manière répétée l'« opérateur de diffusion de Grover » (qui amplifie l'amplitude de l'état cible tout en supprimant les autres) via un processus appelé amplification d'amplitude. Après environ π√N/4 itérations, mesurer l'état donne l'élément cible avec une forte probabilité. L'algorithme de Grover est prouvé optimal. Aucun algorithme quantique ne fait mieux pour la recherche non structurée. Les applications incluent la recherche en base de données, la résolution de problèmes NP-difficiles et la cryptanalyse quantique. HLQuantum inclut une implémentation de Grover intégrée.
Termes associés
Circuit Quantique
FundamentalsUne séquence de portes quantiques appliquées à un registre de qubits, suivie de mesures.
Porte Hadamard
GatesLa porte H : crée une superposition égale de |0⟩ et |1⟩ à partir d'un état de base.
QFT
AlgorithmsQuantum Fourier Transform : l'analogue quantique de la transformée de Fourier discrète, exponentiellement plus rapide.
Algorithme de Deutsch-Jozsa
AlgorithmsUn algorithme quantique précoce qui détermine si une fonction cachée est constante ou équilibrée en une seule requête, contre jusqu'à la moitié des entrées possibles classiquement, historiquement important comme première preuve que les ordinateurs quantiques peuvent offrir une accélération exponentielle.
Estimation d'Amplitude
AlgorithmsUn algorithme quantique qui estime l'amplitude de probabilité d'un résultat marqué de façon quadratiquement plus rapide que l'échantillonnage de Monte-Carlo classique, base des accélérations quantiques proposées en tarification de produits dérivés et en analyse de risque.