Quelles sont les applications de l'algorithme de recherche de Grover?

On parle généralement de l'algorithme de recherche de Grover en termes de recherche d'une entrée marquée dans une base de données non triée. Il s'agit d'un formalisme naturel qui permet de l'appliquer directement à la recherche de solutions aux problèmes NP (où une bonne solution est facilement reconnaissable).

J'étais intéressé à découvrir d'autres applications de la recherche de Grover pour trouver le minimum, la moyenne et la médiane d'un ensemble de nombres. Cela me laisse me demander s'il existe d'autres applications moins évidentes de la recherche de Grover (ou des applications de ses généralisations telles que l'amplification d'amplitude) qui sont déjà connues? Tout bref aperçu sur la façon dont cela est fait serait apprécié.

Outre celles que vous avez mentionnées, une autre application de l'algorithme de Grover (modifié) dont je suis au courant consiste à résoudre le problème de collision en théorie de la complexité, en informatique quantique et en mathématiques computationnelles . Il est également appelé l' algorithme BHT .

Présentation :

Le problème de collision se réfère le plus souvent à la version 2-à-1 qui a été décrite par Scott Aaronson dans sa thèse de doctorat. Étant donné que est pair et une fonction f : { 1 , . . . , N } → { 1 , . . . , n } nous savons à l'avance que f vaut 1 pour 1 ou 2 pour 1. Nous ne sommes autorisés à faire des requêtes sur la valeur de f ( i ) que pour tout i ∈ { 1 , 2 $n$$f:\{1,...,n\}\to\{1,...,n\}$$f$$f(i)$ . Le problème demande alors combien de requêtes nous devons faire pour déterminer avec certitude si f est 1-to-1 ou 2-to-1.$i\in\{1,2,...,n\}$$f$

La résolution de la version 2-à-1 nécessite de manière déterministe requêtes, et en général la distinction des fonctions r-to-1 des fonctions 1-à-1 nécessite n / r + 1 requêtes.$n/2+1$$n/r+1$

Solution classique déterministe :

Il s'agit d'une application simple du principe du pigeonhole: si une fonction est r-to-1, alors après requêtes, nous sommes assurés d'avoir trouvé une collision. Si une fonction est 1 à 1, aucune collision n'existe. Si nous n'avons pas de chance, les requêtes n / r pourraient renvoyer des réponses distinctes. Donc, n / r + 1 requêtes sont nécessaires.$n/r+1$$n/r$$n/r+1$

Solution classique randomisée :

Si nous autorisons l'aléatoire, le problème est plus facile. Par le paradoxe de l'anniversaire, si nous choisissons des requêtes (distinctes) au hasard, alors avec une forte probabilité, nous trouvons une collision dans n'importe quelle fonction 2-à-1 fixe après requêtes.$\Theta(\sqrt{n})$

Solution Quantum BHT :

Intuitivement, l'algorithme combine l'accélération de la racine carrée du paradoxe d'anniversaire en utilisant l'aléatoire (classique) avec l'accélération de la racine carrée de l'algorithme (quantique) de Grover.

Premièrement, entrées à f sont choisis au hasard et f est interrogé à chacun d'eux. S'il y a 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. Comme il n'y a que n 2 / 3 de ces entrées à f , l'algorithme de Grover peut trouver un (si elle existe) en faisant seulement O ( $n^{1/3}$$f$$f$$f$$f$$n^{2/3}$$f$requêtes àf.$\mathcal{O}(\sqrt{n^{2/3}})=\mathcal{O}(n^{1/3})$$f$

Sources:

1. https://en.wikipedia.org/wiki/Collision_problem

2. https://en.wikipedia.org/wiki/BHT_algorithm

3. Algorithme quantique pour le problème de collision - Gilles Brassard, Peter Hoyer, Alain Tapp

L'algorithme de Grover est également largement utilisé en cryptographie quantique. Il peut être utilisé pour résoudre des problèmes tels que le problème du logarithme transcendantal, le problème de recherche de racine polynomiale, etc.

L'algorithme de Grover peut être utilisé pour résoudre tout problème d'optimisation numérique plus rapidement que la recherche par force brute, car tout problème d'optimisation peut être formulé comme un problème de recherche (où vous recherchez une sortie de fonction supérieure / inférieure à certaines fixes) $M$ dans chaque exécution, et vous répétez pour un nombre logarithmique d'exécutions en utilisant la recherche binaire à la maison dans l'optimal $M$): https://epubs.siam.org/doi/abs/10.1137/040605072?journalCode=sjope8 .

En fait, l'algorithme de Grover est l'algorithme quantique le plus connu pour de nombreux problèmes d'optimisation difficiles (tels que les problèmes NP-complets) qui n'ont pas beaucoup de structure qui se prête à un algorithme classique plus intelligent que la recherche par force brute: https: // link.springer.com/chapter/10.1007/978-3-540-78773-0_67 .