Recherche non structurée

Résumé

Nous commencerons par une description du problème que résout l'algorithme de Grover. Comme d'habitude, nous noterons $\Sigma = \{0,1\}$ l'alphabet binaire tout au long de cette discussion.

Supposons que

$$f:\Sigma^n \rightarrow \Sigma$$

soit une fonction de chaînes binaires de longueur $n$ vers des bits. Nous supposerons que nous pouvons calculer cette fonction efficacement, mais qu'elle est par ailleurs arbitraire et que nous ne pouvons pas compter sur le fait qu'elle possède une structure particulière ou une implémentation spécifique qui nous convient.

Ce que fait l'algorithme de Grover, c'est rechercher une chaîne $x\in\Sigma^n$ pour laquelle $f(x) = 1.$ Nous appellerons de telles chaînes des solutions au problème de recherche. S'il y a plusieurs solutions, l'une quelconque d'entre elles est considérée comme une sortie correcte, et s'il n'y a pas de solutions, une réponse correcte nécessite que nous signalions qu'il n'y a pas de solutions.

Cette tâche est décrite comme un problème de recherche non structurée car on ne peut pas compter sur le fait que $f$ possède une structure particulière pour la faciliter. Nous ne recherchons pas dans une liste ordonnée, ni dans une structure de données spécifiquement conçue pour faciliter la recherche ; nous cherchons essentiellement une aiguille dans une botte de foin.

Intuitivement, nous pouvons imaginer que nous avons un circuit booléen extrêmement complexe qui calcule $f,$ et que nous pouvons facilement exécuter ce circuit sur une chaîne d'entrée sélectionnée si nous le choisissons. Mais parce que le circuit est si complexe, nous n'avons aucun espoir de comprendre le circuit en l'examinant (au-delà d'avoir la capacité de l'évaluer sur des chaînes d'entrée sélectionnées).

Une façon d'effectuer cette tâche de recherche classiquement est de simplement itérer sur toutes les chaînes $x\in\Sigma^n,$ en évaluant $f$ sur chacune pour vérifier si c'est une solution ou non. Désormais, écrivons

$$N = 2^n$$

par commodité. Il y a $N$ chaînes dans $\Sigma^n,$ donc itérer sur toutes nécessite $N$ évaluations de $f.$ En supposant que nous sommes limités à évaluer $f$ sur des entrées choisies, c'est le mieux que nous puissions faire avec un algorithme déterministe si nous voulons garantir le succès. Avec un algorithme probabiliste, nous pourrions espérer gagner du temps en choisissant aléatoirement des chaînes d'entrée pour $f,$ mais nous aurons quand même besoin de $O(N)$ évaluations de $f$ si nous voulons que cette méthode réussisse avec haute probabilité.

L'algorithme de Grover résout ce problème de recherche avec haute probabilité avec seulement $O(\sqrt{N})$ évaluations de $f.$ Pour être clair, ces évaluations de fonctions doivent se produire en superposition, de façon similaire aux algorithmes de requêtes discutés dans la leçon Algorithmes de requêtes quantiques, notamment l'algorithme de Deutsch, l'algorithme de Deutsch-Jozsa et l'algorithme de Simon. Contrairement à ces algorithmes, l'algorithme de Grover adopte une approche itérative : il évalue $f$ sur des superpositions de chaînes d'entrée et entremêle ces évaluations avec d'autres opérations qui ont pour effet de créer des patterns d'interférence, menant à une solution avec haute probabilité (si elle existe) après $O(\sqrt{N})$ itérations.

Énoncé formel du problème

Nous allons formaliser le problème que résout l'algorithme de Grover en utilisant le modèle de calcul par requêtes. C'est-à-dire que nous supposerons avoir accès à la fonction $f:\Sigma^n\rightarrow\Sigma$ par l'intermédiaire d'une porte de requête définie de la manière habituelle :

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

pour tout $x\in\Sigma^n$ et $a\in\Sigma.$ C'est l'action de $U_f$ sur les états de base standard, et son action en général est déterminée par linéarité.

Comme il a été discuté dans la leçon Fondements algorithmiques quantiques, si nous avons un circuit booléen pour calculer $f,$ nous pouvons transformer cette description de circuit booléen en un circuit quantique implémentant $U_f$ (en utilisant un certain nombre de qubits d'espace de travail qui commencent et terminent le calcul dans l'état $\vert 0\rangle$). Ainsi, bien que nous utilisions le modèle de requêtes pour formaliser le problème que résout l'algorithme de Grover, il n'est pas limité à ce modèle ; nous pouvons exécuter l'algorithme de Grover sur toute fonction $f$ pour laquelle nous avons un circuit booléen.

Voici un énoncé précis du problème, nommé Recherche car nous cherchons une solution, c'est-à-dire une chaîne $x$ qui fait que $f$ s'évalue à $1.$

Recherche

Entrée : une fonction $f:\Sigma^n\rightarrow\Sigma$
Sortie : une chaîne $x\in\Sigma^n$ satisfaisant $f(x) = 1,$ ou « aucune solution » si aucune telle chaîne $x$ n'existe

Remarque que ce n'est pas un problème de promesse — la fonction $f$ est arbitraire. Il sera toutefois utile de considérer la variante de promesse suivante du problème, où il est garanti qu'il y a exactement une solution. Ce problème est apparu comme exemple de problème de promesse dans la leçon Algorithmes de requêtes quantiques.

Recherche unique

Entrée : une fonction de la forme $f:\Sigma^n \rightarrow \Sigma$
Promesse : il y a exactement une chaîne $z\in\Sigma^n$ pour laquelle $f(z) = 1,$ avec $f(x) = 0$ pour toutes les chaînes $x\neq z$
Sortie : la chaîne $z$

Remarque également que le problème Ou mentionné dans la même leçon est étroitement lié à Recherche. Pour ce problème, l'objectif est simplement de déterminer si une solution existe ou non, par opposition à trouver effectivement une solution.