Le modèle de calcul par requêtes

Lorsqu'on modélise des calculs en termes mathématiques, on a généralement en tête le type de processus représenté par la figure suivante, où une information est fournie en entrée, un calcul s'effectue, et une sortie est produite.

Même s'il est vrai que les ordinateurs d'aujourd'hui reçoivent continuellement des entrées et produisent des sorties, interagissant ainsi avec nous et avec d'autres ordinateurs d'une façon que la figure ne reflète pas, l'intention n'est pas de représenter le fonctionnement continu des ordinateurs. Il s'agit plutôt de créer une abstraction simple du calcul, en se concentrant sur des tâches computationnelles isolées. Par exemple, l'entrée pourrait encoder un nombre, un vecteur, une matrice, un graphe, la description d'une molécule, ou quelque chose de plus complexe, tandis que la sortie encode une solution à la tâche computationnelle visée.

Le point essentiel est que l'entrée est fournie au calcul, généralement sous la forme d'une chaîne binaire, sans qu'aucune partie en soit cachée.

Description du modèle

Dans le modèle de calcul par requêtes, l'entrée complète n'est pas fournie au calcul comme dans le modèle standard évoqué ci-dessus. L'entrée est plutôt mise à disposition sous la forme d'une fonction, à laquelle le calcul accède en effectuant des requêtes. On peut aussi voir les calculs dans le modèle par requêtes comme ayant un accès aléatoire aux bits (ou segments de bits) de l'entrée.

On dit souvent que l'entrée est fournie par un oracle ou une boîte noire dans le contexte du modèle par requêtes. Ces deux termes suggèrent qu'une description complète de l'entrée est cachée au calcul, et que le seul moyen d'y accéder est de poser des questions. C'est comme si on consultait l'Oracle de Delphes au sujet de l'entrée : il ne nous dit pas tout ce qu'il sait, il ne répond qu'à des questions précises. Le terme boîte noire prend tout son sens lorsqu'on considère l'entrée comme représentée par une fonction ; on ne peut pas regarder à l'intérieur de la fonction pour comprendre comment elle fonctionne, on peut seulement l'évaluer sur les arguments qu'on choisit.

Dans cette leçon, on travaillera exclusivement avec des chaînes binaires, par opposition à des chaînes contenant différents symboles. On écrira donc $\Sigma = \{0,1\}$ ci-après pour désigner l'alphabet binaire par commodité. On réfléchira à différents problèmes computationnels, dont quelques exemples simples sont décrits bientôt, mais pour tous, l'entrée sera représentée par une fonction de la forme

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

pour deux entiers positifs $n$ et $m.$ On pourrait naturellement choisir un autre nom à la place de $f,$ mais on s'en tient à $f$ tout au long de la leçon.

Dire qu'un calcul effectue une requête signifie qu'une chaîne $x \in \Sigma^n$ est sélectionnée, puis la chaîne $f(x)\in\Sigma^m$ est mise à la disposition du calcul par l'oracle. La manière précise dont cela fonctionne pour les algorithmes quantiques sera discutée sous peu — il faut s'assurer que c'est réalisable avec une opération quantique unitaire permettant d'effectuer des requêtes en superposition — mais pour l'instant on peut y penser intuitivement à un niveau élevé.

Enfin, la façon dont on mesure l'efficacité des algorithmes par requêtes est simple : on compte le nombre de requêtes qu'ils nécessitent. Cela est lié au temps nécessaire pour effectuer un calcul, mais ce n'est pas exactement la même chose, car on ignore le temps consacré aux opérations autres que les requêtes, et on traite chaque requête comme si elle avait un coût unitaire. On peut prendre en compte les opérations autres que les requêtes si on le souhaite (ce qui est parfois fait), mais restreindre l'attention au seul nombre de requêtes aide à garder les choses simples.

Exemples de problèmes par requêtes

Voici quelques exemples simples de problèmes par requêtes.

• OU. La fonction d'entrée prend la forme $f:\Sigma^n \rightarrow \Sigma$ (donc $m=1$ pour ce problème). La tâche est de renvoyer $1$ s'il existe une chaîne $x\in\Sigma^n$ pour laquelle $f(x) = 1,$ et de renvoyer $0$ s'il n'en existe pas. Si on considère la fonction $f$ comme représentant une séquence de $2^n$ bits auxquels on a accès aléatoire, le problème consiste à calculer le OU de ces bits.

• Parité. La fonction d'entrée prend à nouveau la forme $f:\Sigma^n \rightarrow \Sigma.$ La tâche est de déterminer si le nombre de chaînes $x\in\Sigma^n$ pour lesquelles $f(x) = 1$ est pair ou impair. Pour être précis, la sortie requise est $0$ si l'ensemble $\{x\in\Sigma^n : f(x) = 1\}$ a un nombre pair d'éléments et $1$ s'il en a un nombre impair. Si on considère la fonction $f$ comme représentant une séquence de $2^n$ bits auxquels on a accès aléatoire, le problème consiste à calculer la parité (ou le OU exclusif) de ces bits.

• Minimum. La fonction d'entrée prend la forme $f:\Sigma^n \rightarrow \Sigma^m$ pour tout choix d'entiers positifs $n$ et $m.$ La sortie requise est la chaîne $y \in \{f(x) : x\in\Sigma^n\}$ qui vient en premier dans l'ordre lexicographique (c'est-à-dire l'ordre du dictionnaire) de $\Sigma^m.$ Si on considère la fonction $f$ comme représentant une séquence de $2^n$ entiers encodés sous forme de chaînes de longueur $m$ en notation binaire auxquels on a accès aléatoire, le problème consiste à calculer le minimum de ces entiers.

On considère aussi des problèmes par requêtes avec une promesse sur l'entrée. Cela signifie qu'on dispose d'une sorte de garantie sur l'entrée, et qu'on n'est pas responsable de ce qui se passe si cette garantie n'est pas satisfaite. Une autre façon de décrire ce type de problème est de dire que certaines fonctions d'entrée (celles pour lesquelles la promesse n'est pas satisfaite) sont considérées comme des entrées « peu importe ». Aucune exigence n'est imposée aux algorithmes lorsqu'ils reçoivent des entrées « peu importe ».

Voici un exemple de problème avec une promesse :

• Recherche unique. La fonction d'entrée prend la forme $f:\Sigma^n \rightarrow \Sigma,$ et on promet qu'il existe 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.$ La tâche est de trouver cette unique chaîne $z.$

Les quatre exemples qui viennent d'être décrits sont naturels, dans le sens où ils sont faciles à décrire et on peut imaginer une variété de situations ou de contextes dans lesquels ils pourraient se présenter.

En revanche, certains problèmes par requêtes ne sont pas « naturels » du tout. En fait, dans l'étude du modèle par requêtes, on invente parfois des problèmes très compliqués et très artificiels pour lesquels il est difficile d'imaginer que quelqu'un voudrait vraiment les résoudre en pratique. Cela ne signifie pas pour autant que ces problèmes ne sont pas intéressants ! Des choses qui peuvent sembler artificielles ou non naturelles au départ peuvent fournir des indices inattendus ou inspirer de nouvelles idées. L'algorithme quantique de Shor pour la factorisation, qui s'est inspiré de l'algorithme de Simon, en est un excellent exemple. L'étude du modèle par requêtes consiste aussi à rechercher des extrêmes, ce qui peut éclairer à la fois les avantages potentiels et les limites du calcul quantique.

Portes de requête

Lorsqu'on décrit des calculs avec des circuits, les requêtes sont effectuées par des portes spéciales appelées portes de requête.

La façon la plus simple de définir des portes de requête pour les circuits booléens classiques est de les laisser simplement calculer la fonction d'entrée $f$ directement, comme le suggère la figure suivante.

Lorsqu'un circuit booléen est créé pour un problème par requêtes, la fonction d'entrée $f$ est accédée via ces portes, et le nombre de requêtes effectuées par le circuit est simplement le nombre de portes de requête qui apparaissent dans le circuit. Les fils d'entrée du circuit booléen lui-même sont initialisés à des valeurs fixes, qui doivent être considérées comme faisant partie de l'algorithme (et non comme des entrées du problème).

Par exemple, voici un circuit booléen avec des portes de requête classiques qui résout le problème de parité décrit ci-dessus pour une fonction de la forme $f:\Sigma\rightarrow\Sigma$ :

Cet algorithme effectue deux requêtes car il comporte deux portes de requête. Il fonctionne de la façon suivante : la fonction $f$ est interrogée sur les deux entrées possibles, $0$ et $1,$ et les résultats sont insérés dans un circuit booléen qui calcule le XOR. (Ce circuit particulier est apparu comme exemple de circuit booléen dans la leçon Circuits quantiques du cours Bases de l'information quantique.)

Pour les circuits quantiques, cette définition des portes de requête ne fonctionne pas, car ces portes seront non-unitaires pour certains choix de la fonction $f.$ On définit donc à la place des portes de requête unitaires qui agissent comme l'indique cette figure sur les états de la base standard :

Ici, l'hypothèse est que $x\in\Sigma^n$ et $y\in\Sigma^m$ sont des chaînes quelconques. La notation $y\oplus f(x)$ désigne le OU exclusif bit à bit de deux chaînes, qui ont une longueur $m$ dans ce cas. Par exemple, $001 \oplus 101 = 100.$

Intuitivement, ce que fait la porte $U_f$ (pour toute fonction $f$ choisie) est de répercuter la chaîne d'entrée supérieure $x$ et d'appliquer un XOR de la valeur de la fonction $f(x)$ sur la chaîne d'entrée inférieure $y,$ ce qui est une opération unitaire pour tout choix de la fonction $f.$ En fait, c'est une opération déterministe, et elle est sa propre inverse. Cela implique que, sous forme matricielle, $U_f$ est toujours une matrice de permutation, c'est-à-dire une matrice avec un seul $1$ dans chaque ligne et chaque colonne, et toutes les autres entrées valant $0.$ Appliquer une matrice de permutation à un vecteur réordonne simplement les entrées du vecteur (d'où le terme matrice de permutation), et ne change donc pas la norme euclidienne de ce vecteur — ce qui révèle que les matrices de permutation sont toujours unitaires.

Il convient de souligner que, lorsqu'on analyse des algorithmes par requêtes en comptant simplement le nombre de requêtes, on ignore complètement la difficulté de construire physiquement les portes de requête — tant pour les versions classiques que quantiques décrites ci-dessus. Intuitivement, la construction des portes de requête fait partie de la préparation de l'entrée, et non de la recherche d'une solution.

Cela peut sembler déraisonnable, mais il faut garder à l'esprit qu'on ne cherche pas à décrire le calcul pratique ni à rendre compte de toutes les ressources nécessaires. On définit plutôt un modèle théorique qui aide à mettre en lumière les avantages potentiels du calcul quantique. On aura davantage à dire sur ce point dans la leçon suivante lorsqu'on se penchera sur un modèle de calcul plus standard où les entrées sont fournies explicitement aux circuits sous forme de chaînes binaires.