Salut, habrozhiteli! Nous avons récemment remis le
livre de Chris Bernhard,
Quantum Computing for Real IT . Ici, ils ont décidé de partager un extrait du livre "Grover's Algorithm and Data Search"
Nous entrons dans l'ère du big data. La recherche efficace d'ensembles de données gigantesques est actuellement une préoccupation brûlante pour de nombreuses grandes entreprises. L'algorithme de Grover est théoriquement capable d'accélérer les recherches de données.
Love Grover a inventé son algorithme en 1996. Comme les algorithmes de Deutsch et Simon, il a une vitesse d'exécution plus élevée que les algorithmes classiques en termes de complexité des requêtes. Cependant, nous ne pourrons pas implémenter l'algorithme de récupération de données actuel sans oracles qui pourraient poser leurs questions. Nous devons construire un algorithme qui effectue le travail de l'oracle. Mais avant de commencer à parler de la mise en œuvre de l'algorithme Grover, voyons ce qu'il fait et comment.
Algorithme de Grover
Imaginez que vous avez quatre cartes à jouer. Ils sont bouleversés. Vous savez que l'un d'eux est un as de vers et vous devez le trouver. Combien de cartes devrez-vous retourner jusqu'à ce que vous sachiez où se trouve l'as de vers?
Si vous êtes chanceux, vous trouverez la carte souhaitée au premier essai, si vous n'êtes pas chanceux, vous pouvez retourner trois cartes, et aucune d'entre elles ne sera un as de vers. Dans le pire des cas, en retournant trois cartes, vous saurez avec certitude que la dernière carte est l'as de ver que vous recherchez. Ainsi, nous pouvons découvrir où se trouve l'as en retournant une à trois cartes. En moyenne, vous devez retourner les cartes 2,25.
C'est l'une des tâches que l'algorithme de Grover résout. Avant de commencer la description de l'algorithme, nous reformulons le problème. Nous avons quatre séquences binaires: 00, 01, 10 et 11. Nous avons une fonction f qui renvoie 0 pour trois de ces séquences et 1 pour la quatrième séquence. Nous devons trouver la séquence binaire correspondant à la valeur de sortie 1. Par exemple, nous pouvons obtenir les résultats suivants: f (00) = 0, f (01) = 0, f (10) = 1 et f (11) = 0. Maintenant, le problème est est de savoir combien de fois la fonction doit être calculée pour obtenir le résultat f (10) = 1. Ici, nous avons simplement reformulé le problème en remplaçant les cartes à jouer par des fonctions, donc la réponse à cette question est déjà connue: comme auparavant, en moyenne, il sera nécessaire de calculer la fonction 2,25 fois.
Comme avec tous les algorithmes de requête de complexité, nous construisons un oracle - une porte qui encapsule une fonction. L'oracle de notre exemple, où il n'y a que quatre séquences binaires, est illustré à la Fig. 9.1.
La chaîne de l'algorithme Grover est représentée sur la Fig. 9.2.
L'algorithme effectue deux étapes. Sur le premier, le signe de l'amplitude de probabilité est inversé, associé à l'endroit que nous essayons de trouver. Le second renforce cette amplitude de probabilité. Voyons comment la chaîne procède.
Après transmission via les valves Hadamard, les deux qubits supérieurs obtiennent l'état
et le qubit inférieur a un état
L'état combiné peut s'écrire
Les qubits passent ensuite par la porte F. Il inverse 0 et 1 dans le troisième qubit à l'emplacement que nous essayons de trouver. Pour notre cas f (10) = 1 on obtient
Il peut être réécrit comme
En conséquence, nous obtenons deux qubits supérieurs, non confondus avec les inférieurs, mais l'amplitude de probabilité
changera le signe, indiquant l'emplacement souhaité.
Si nous mesurons les deux qubits supérieurs à cette étape, nous obtenons l'un des quatre emplacements, et les quatre réponses possibles sont également probables. Nous devons faire un autre pas - pour augmenter l'amplitude de la probabilité. L'amplification est réalisée en inversant la séquence des nombres par rapport à leur moyenne. Si le nombre est supérieur à la moyenne, il bascule et devient inférieur à la moyenne. Si le nombre est inférieur à la moyenne, il bascule et devient supérieur à la moyenne. Dans chaque cas, l'éloignement de la moyenne est maintenu. Pour illustrer, nous utilisons quatre nombres: 1, 1, 1 et –1. Leur somme est de 2 et la moyenne est de 2/4 ou 1/2. Ensuite, nous commençons à trier les numéros dans la séquence. Le premier nombre est 1. Il est 1/2 au-dessus de la moyenne. Après le coup d'État, il devrait être 1/2 de moins que la moyenne. Dans ce cas, il passera à 0. Le nombre –1 est inférieur à la moyenne de 3/2. Après le coup d'État, il devrait devenir 3/2 au-dessus de la moyenne, c'est-à-dire se transformer en 2.
Deux qubits supérieurs ont actuellement un état
En tournant les amplitudes par rapport à la moyenne, on obtient
.
Une fois la mesure terminée, nous en obtiendrons certainement 10, c'est-à-dire qu'une révolution par rapport à la moyenne nous donne exactement ce dont nous avons besoin. Tout ce que nous avons à faire est de nous assurer qu’il existe une porte ou, ce qui revient au même, une matrice orthogonale décrivant une révolution par rapport à la moyenne. Une telle matrice existe:
À la suite de l'action de la valve sur les deux qubits supérieurs, nous obtenons
Dans cet exemple, où nous n'avons que deux qubits, nous ne devons utiliser l'oracle qu'une seule fois. Il nous suffit de poser la seule question. Pour le cas n = 2, l'algorithme de Grover donne une réponse exacte après une seule question, alors que dans le cas classique, en moyenne, 2,25 questions doivent être posées.
Cette idée s'étend au cas d'un nombre arbitraire de n qubits. On commence par tourner le signe de l'amplitude de probabilité, qui correspond à l'emplacement souhaité. Ensuite, nous effectuons une révolution par rapport à la moyenne. Cependant, dans ce cas, l'amplification de l'amplitude ne se produit pas aussi significativement que dans la situation à deux qubits. Prenons par exemple huit nombres, dont sept sont 1 et un est -1. Leur somme est de 6 et la moyenne est de 6/8. Après un flip, le 1 moyen tournera 1/2 et –1 tournera 10/4. Par conséquent, en présence de trois qubits, mesurant un qubit après amplification de l'amplitude, nous obtiendrons l'emplacement souhaité avec une probabilité plus élevée que les autres. Le problème est qu'il y a une chance importante d'obtenir la mauvaise réponse. Nous avons besoin d'une probabilité plus élevée d'obtenir la bonne réponse - nous devons encore amplifier l'amplitude avant de mesurer. La solution est de retransférer tous les qubits à travers la chaîne. Nous inversons à nouveau le signe de l'amplitude de probabilité associée à l'emplacement souhaité et inversons à nouveau par rapport à la moyenne.
Prenons le cas généralisé. Nous devons trouver quelque chose dans l'un des m emplacements possibles. Pour le trouver de façon classique, dans le pire des cas nous devons poser m - 1 questions. Le nombre de questions augmente proportionnellement à m. Grover a calculé une formule qui détermine combien de fois sa chaîne doit être utilisée pour obtenir la probabilité maximale d'une réponse correcte. Le nombre que cette formule donne croît proportionnellement
. Il s'agit d'une accélération quadratique.
Applications de l'algorithme Grover
Il y a plusieurs problèmes avec l'implémentation de l'algorithme. Tout d'abord, l'accélération quadratique est évaluée par rapport à la demande de complexité. Pour utiliser l'oracle, vous devez le créer, et si vous n'effectuez pas cette tâche avec soin, le nombre d'étapes effectuées par l'oracle l'emportera sur le nombre d'étapes que l'algorithme enregistre, et par conséquent, l'algorithme deviendra plus lent plutôt que plus rapide que le classique. Un autre problème est que, en déterminant l'accélération, nous supposons que l'ensemble de données est désordonné. Si l'ensemble de données a une structure spécifique, vous pouvez souvent trouver un algorithme classique qui utilise cette structure et recherche une solution beaucoup plus rapidement. Le dernier problème est lié à l'accélération. L'accélération quadratique n'est rien d'autre qu'une accélération exponentielle, que nous avons observée dans d'autres algorithmes. Est-il possible d'en faire plus? Examinons ces problèmes.
Les deux problèmes liés à la mise en œuvre de l'oracle et la présence de la structure dans l'ensemble de données sont justifiés et montrent que dans la plupart des cas, l'algorithme Grover n'a pas d'application pratique pour la recherche dans la base de données. Mais dans certaines situations, avoir une structure dans les données permet de créer un oracle qui agit avec une grande efficacité. Dans de telles situations, l'algorithme peut dépasser les algorithmes classiques. La réponse à la question de la possibilité d'obtenir un plus grand succès a déjà été donnée. Il est prouvé que l'algorithme de Grover est optimal. Il n'y a pas d'algorithme quantique capable de résoudre un problème avec une accélération plus que quadratique. L'accélération quadratique, bien qu'elle ne soit pas aussi impressionnante que l'exponentielle, offre néanmoins certains avantages. Lorsque vous travaillez avec de grands ensembles de données, toute accélération peut être utile.
Il est probable que l'algorithme Grover trouvera l'application principale non pas pour la recherche, comme cela a été présenté ci-dessus, mais pour ses variations. En particulier, l'idée d'amplifier l'amplitude peut être utile.
Nous n'avons examiné que quelques algorithmes, mais les algorithmes Shore et Grover sont considérés comme les plus importants. Il existe de nombreux autres algorithmes basés sur les idées inhérentes à ces deux.1 Maintenant tournons notre attention des algorithmes quantiques vers d'autres domaines d'application de l'informatique quantique.