Mesurer le coût computationnel

Nous allons maintenant aborder un cadre mathématique permettant de mesurer le coût computationnel, en nous concentrant sur les besoins de ce cours. L'analyse des algorithmes et la complexité computationnelle sont des sujets à part entière, qui ont bien plus à dire sur ces notions.

Pour commencer, considère la figure suivante tirée de la leçon précédente, qui représente une abstraction de très haut niveau d'un calcul.

Le calcul lui-même peut être modélisé ou décrit de différentes façons, par exemple par un programme Python, une machine de Turing, un circuit booléen ou un circuit quantique. Notre attention se portera sur les circuits (booléens et quantiques).

Encodages et longueur de l'entrée

Commençons par l'entrée et la sortie d'un problème computationnel, que nous supposerons être des chaînes binaires. D'autres symboles pourraient être utilisés, mais pour simplifier nous nous limiterons aux entrées et sorties sous forme de chaînes binaires. Grâce aux chaînes binaires, nous pouvons encoder une grande variété d'objets intéressants que les problèmes à résoudre peuvent concerner, tels que des nombres, des vecteurs, des matrices et des graphes, ainsi que des listes de ces objets et d'autres.

Par exemple, pour encoder des entiers non négatifs, nous pouvons utiliser la notation binaire. Le tableau suivant liste l'encodage binaire des neuf premiers entiers non négatifs, ainsi que la longueur (c'est-à-dire le nombre total de bits) de chaque encodage.

Nombre	Encodage binaire	Longueur
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

On peut facilement étendre cet encodage pour gérer les entiers positifs et négatifs en ajoutant un bit de signe aux représentations si on le souhaite. Il est aussi parfois commode d'autoriser des zéros non significatifs dans les représentations binaires des entiers non négatifs, ce qui ne change pas la valeur encodée mais permet aux représentations de remplir une chaîne ou un mot de taille fixe.

Utiliser la notation binaire pour représenter les entiers non négatifs est à la fois courant et efficace, mais si on le voulait, on pourrait choisir une autre façon de représenter les entiers non négatifs en chaînes binaires, comme celles suggérées dans le tableau suivant. Les détails de ces alternatives n'ont pas d'importance ici — le point est simplement de clarifier que nous avons des choix pour les encodages que nous utilisons.

Nombre	Encodage unaire	Encodage lexicographique
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(Dans ce tableau, le symbole $\varepsilon$ représente la chaîne vide, qui ne contient aucun symbole et a une longueur égale à zéro. Naturellement, pour éviter une source évidente de confusion, on utilise un symbole spécial tel que $\varepsilon$ pour représenter la chaîne vide plutôt que de ne rien écrire littéralement.)

D'autres types d'entrées, comme les vecteurs et les matrices, ou des objets plus complexes tels que des descriptions de molécules, peuvent aussi être encodés sous forme de chaînes binaires. Tout comme pour les entiers non négatifs, une grande variété de schémas d'encodage peut être sélectionnée ou inventée. Quel que soit le schéma que nous adoptons pour encoder les entrées d'un problème donné, nous interprétons la longueur d'une chaîne d'entrée comme représentant la taille de l'instance du problème à résoudre.

Par exemple, le nombre de bits nécessaires pour exprimer un entier non négatif $N$ en notation binaire, parfois noté $\operatorname{lg}(N),$ est donné par la formule suivante.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

En supposant que nous utilisons la notation binaire pour encoder l'entrée du problème de factorisation des entiers, la longueur d'entrée pour le nombre $N$ est donc $\operatorname{lg}(N).$ Notons en particulier que la longueur (ou la taille) de l'entrée $N$ n'est pas $N$ lui-même ; quand $N$ est grand, il ne faut pas autant de bits pour exprimer $N$ en notation binaire.

D'un point de vue strictement formel, chaque fois que nous considérons un problème ou une tâche computationnelle, il faut comprendre qu'un schéma spécifique a été sélectionné pour encoder les objets fournis en entrée ou produits en sortie. Cela permet de voir abstraitement les calculs qui résolvent des problèmes intéressants comme des transformations de chaînes binaires en entrée vers des chaînes binaires en sortie.

Les détails de la façon dont les objets sont encodés en chaînes binaires doivent nécessairement être importants pour ces calculs à un certain niveau. En général, cependant, on ne s'inquiète pas trop de ces détails lors de l'analyse du coût computationnel, afin d'éviter de s'attarder sur des détails d'importance secondaire. Le raisonnement de base est que nous nous attendons à ce que le coût computationnel de la conversion entre des schémas d'encodage « raisonnables » soit négligeable par rapport au coût de la résolution du problème réel. Dans les cas où ce n'est pas le cas, les détails peuvent (et doivent) être précisés.

Par exemple, un calcul très simple convertit entre la représentation binaire d'un entier non négatif et son encodage lexicographique (que nous n'avons pas expliqué en détail, mais qu'on peut inférer du tableau ci-dessus). Pour cette raison, le coût computationnel de la factorisation des entiers ne différerait pas significativement si nous décidions de passer de l'un de ces encodages à l'autre pour l'entrée $N.$ En revanche, encoder des entiers non négatifs en notation unaire entraîne une explosion exponentielle du nombre total de symboles requis, et nous ne le considérerions pas comme un schéma d'encodage « raisonnable » pour cette raison.

Opérations élémentaires

Considérons maintenant le calcul lui-même, représenté par le rectangle bleu dans la figure ci-dessus. La façon dont nous mesurerons le coût computationnel est de compter le nombre d'opérations élémentaires que chaque calcul requiert. Intuitivement, une opération élémentaire est une opération portant sur un petit nombre fixe de bits ou de qubits, qui peut être effectuée rapidement et facilement — comme le calcul du ET logique de deux bits. En revanche, exécuter la fonction factorint n'est pas raisonnablement considéré comme une opération élémentaire.

D'un point de vue formel, il existe différents choix pour ce qui constitue une opération élémentaire selon le modèle de calcul utilisé. Notre attention se portera sur les modèles à base de circuits, et plus précisément les circuits quantiques et booléens.

Ensembles de portes universelles

Dans les modèles de calcul à base de circuits, il est typique que chaque porte soit vue comme une opération élémentaire. Cela soulève la question de savoir précisément quelles portes nous autorisons dans nos circuits. En se concentrant pour l'instant sur les circuits quantiques, nous avons vu plusieurs portes jusqu'ici dans cette série, notamment les portes $X,$ $Y,$ $Z,$ $H,$ $S,$ et $T,$ les portes swap, les versions contrôlées de portes (y compris les portes CNOT, Toffoli et Fredkin), ainsi que les portes représentant les mesures dans la base standard. Dans le contexte du jeu CHSH, nous avons aussi vu quelques portes de rotation supplémentaires.

Nous avons également abordé les portes de requête dans le contexte du modèle de requête, et nous avons aussi vu que toute opération unitaire $U,$ agissant sur n'importe quel nombre de qubits, peut être vue comme une porte si on le souhaite — mais nous ignorerons ces deux options pour les besoins de cette discussion. Nous ne travaillerons pas dans le modèle de requête (bien que l'implémentation des portes de requête à l'aide d'opérations élémentaires soit abordée plus loin dans la leçon), et considérer des portes unitaires arbitraires, agissant potentiellement sur des millions de qubits, comme des opérations élémentaires ne mène pas à des notions de coût computationnel significatives ou réalistes.

En nous en tenant aux portes quantiques opérant sur de petits nombres de qubits, une approche pour décider lesquelles sont considérées comme élémentaires serait d'établir un critère précis — mais ce n'est pas l'approche standard, ni celle que nous adopterons. Au contraire, nous faisons simplement un choix.

Voici un choix standard, que nous adopterons comme ensemble de portes par défaut pour les circuits quantiques :

• Portes unitaires à un seul qubit de cette liste : $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ et $T^{\dagger}$
• Portes CNOT
• Mesures dans la base standard à un seul qubit

Une alternative courante consiste à considérer les portes Toffoli, Hadamard et $S$ comme élémentaires, en plus des mesures dans la base standard. Parfois, toutes les portes à un seul qubit sont considérées comme élémentaires, bien que cela conduise à un modèle d'une puissance irréaliste lorsque la précision avec laquelle les portes sont effectuées n'est pas correctement prise en compte.

Les portes unitaires de notre collection par défaut forment ce qu'on appelle un ensemble de portes universel. Cela signifie que nous pouvons approximer n'importe quelle opération unitaire sur n'importe quel nombre de qubits avec le degré de précision souhaité, en utilisant uniquement des circuits composés de ces portes. Pour être clair, la définition de l'universalité n'impose aucune exigence sur le coût de telles approximations, c'est-à-dire sur le nombre de portes de notre ensemble dont nous avons besoin. En fait, un argument assez simple basé sur la notion mathématique de mesure révèle que la plupart des opérations unitaires doivent avoir un coût extrêmement élevé. Prouver l'universalité des ensembles de portes quantiques n'est pas chose simple et ne sera pas traité dans ce cours.

Pour les circuits booléens, nous prendrons les portes ET, OU, NON et FANOUT comme représentant les opérations élémentaires. Nous n'avons en fait pas besoin à la fois des portes ET et OU — nous pouvons utiliser les lois de De Morgan pour convertir de l'une à l'autre en plaçant des portes NON sur les trois fils d'entrée/sortie — mais il est néanmoins à la fois typique et commode d'autoriser les deux. Les portes ET, OU, NON et FANOUT forment un ensemble universel pour les calculs déterministes, ce qui signifie que n'importe quelle fonction de n'importe quel nombre fixe de bits d'entrée vers n'importe quel nombre fixe de bits de sortie peut être implémentée avec ces portes.

Le principe de report des mesures

Les portes de mesure dans la base standard peuvent apparaître à l'intérieur des circuits quantiques, mais il est parfois commode de les retarder jusqu'à la fin. Cela nous permet de voir les calculs quantiques comme étant constitués d'une partie unitaire (représentant le calcul lui-même), suivie d'une simple phase de lecture où les qubits sont mesurés et les résultats sont produits en sortie. Cela peut toujours être fait, à condition d'être prêt à ajouter un qubit supplémentaire pour chaque mesure dans la base standard. Dans la figure suivante, le circuit de droite illustre comment cela peut être fait pour la porte de gauche.

Plus précisément, le bit classique dans le circuit de gauche est remplacé par un qubit à droite (initialisé à l'état $\vert 0\rangle$), et la mesure dans la base standard est remplacée par une porte CNOT, suivie d'une mesure dans la base standard sur le qubit du bas. L'idée est que la mesure dans la base standard dans le circuit de droite peut être repoussée jusqu'à la fin du circuit. Si le bit classique dans le circuit de gauche est ensuite utilisé comme bit de contrôle, nous pouvons utiliser le qubit du bas dans le circuit de droite comme contrôle à la place, et l'effet global sera le même. (Nous supposons que le bit classique dans le circuit de gauche n'est pas écrasé après la mesure par une autre mesure — mais si c'était le cas, nous pourrions toujours utiliser un nouveau bit classique plutôt que d'écraser celui utilisé pour une mesure précédente.)

Taille et profondeur d'un circuit

Taille d'un circuit

Le nombre total de portes dans un circuit est appelé la taille de ce circuit. Ainsi, en supposant que les portes de nos circuits représentent des opérations élémentaires, la taille d'un circuit représente le nombre d'opérations élémentaires qu'il nécessite — autrement dit, son coût computationnel. On écrit $\operatorname{size}(C)$ pour désigner la taille d'un circuit donné $C.$

Par exemple, considère le circuit booléen suivant pour calculer le XOR de deux bits.

La taille de ce circuit est 7 car il y a 7 portes au total. (Les opérations FANOUT ne sont pas toujours comptées comme des portes, mais pour les besoins de cette leçon nous les compterons comme telles.)

Temps, coût et profondeur d'un circuit

Le temps est une ressource d'une importance cruciale, ou une contrainte limitante, pour les calculs. Les exemples ci-dessus, comme la tâche de factoriser RSA1024, renforcent ce point de vue. La fonction factorint ne rate pas à proprement parler la factorisation de RSA1024, c'est juste que nous n'avons pas assez de temps pour la laisser se terminer.

La notion de coût computationnel, en tant que nombre d'opérations élémentaires nécessaires pour effectuer un calcul, est censée être un substitut abstrait pour le temps requis pour implémenter un calcul. Chaque opération élémentaire demande un certain temps à effectuer, et plus un calcul en nécessite, plus il prendra de temps, au moins en général. Dans un souci de simplicité, nous continuerons à faire cette association entre le coût computationnel et le temps nécessaire pour exécuter des algorithmes.

Mais remarque que la taille d'un circuit ne correspond pas nécessairement directement au temps qu'il faut pour l'exécuter. Dans notre circuit booléen pour calculer le XOR de deux bits, par exemple, les deux portes FANOUT pourraient être effectuées simultanément, tout comme les deux portes NON et les deux portes ET. Une autre façon de mesurer l'efficacité des circuits, qui tient compte de cette possibilité de parallélisation, est leur profondeur. Il s'agit du nombre minimum de couches de portes nécessaires dans le circuit, où les portes de chaque couche opèrent sur des fils différents. De manière équivalente, la profondeur d'un circuit est le nombre maximum de portes rencontrées sur n'importe quel chemin d'un fil d'entrée à un fil de sortie. Pour le circuit ci-dessus, par exemple, la profondeur est 4.

La profondeur d'un circuit est une façon de formaliser le temps d'exécution des calculs parallèles. C'est un sujet avancé, et il existe des constructions de circuits très sophistiquées connues pour minimiser la profondeur requise pour certains calculs. Il existe également des questions fascinantes sans réponse concernant la profondeur des circuits. (Par exemple, on sait encore peu de choses sur la profondeur de circuit nécessaire pour calculer des PGCD.) Nous n'aurons pas grand-chose de plus à dire sur la profondeur des circuits dans cette série, hormis quelques faits intéressants au fil des leçons, mais il convient de reconnaître clairement que la parallélisation est une source potentielle d'avantages computationnels.

Attribuer des coûts aux différentes portes

Une dernière remarque concernant la taille des circuits et le coût computationnel : il est possible d'attribuer des coûts différents aux portes, plutôt que de voir chaque porte comme contribuant également au coût total.

Par exemple, comme déjà mentionné, les portes FANOUT sont souvent considérées comme gratuites pour les circuits booléens — ce qui revient à dire que nous pourrions choisir que les portes FANOUT aient un coût nul. Autre exemple : lorsqu'on travaille dans le modèle de requête et qu'on compte le nombre de requêtes qu'un circuit effectue à une fonction d'entrée (sous forme de boîte noire), on attribue effectivement un coût unitaire aux portes de requête et un coût nul aux autres portes, comme les portes Hadamard. Un dernier exemple est qu'on attribue parfois des coûts différents aux portes selon la difficulté de leur implémentation, ce qui peut varier selon le matériel considéré.

Bien que toutes ces options soient judicieuses dans différents contextes, pour cette leçon nous garderons les choses simples et nous en tiendrons à la taille du circuit comme représentation du coût computationnel.

Coût en fonction de la longueur de l'entrée

Nous nous intéressons principalement à la façon dont le coût computationnel évolue à mesure que les entrées deviennent de plus en plus grandes. Cela nous amène à représenter les coûts des algorithmes comme des fonctions de la longueur de l'entrée.

Familles de circuits

Les entrées d'un problème computationnel donné peuvent varier en longueur, devenant potentiellement arbitrairement grandes. Chaque circuit, en revanche, a un nombre fixe de portes et de fils. Pour cette raison, lorsque nous pensons aux algorithmes en termes de circuits, nous avons généralement besoin de familles infiniment grandes de circuits pour représenter les algorithmes. Par famille de circuits, nous entendons une suite de circuits qui croît en taille, permettant d'accommoder des entrées de plus en plus grandes.

Par exemple, imaginons que nous ayons un algorithme classique pour la factorisation des entiers, comme celui utilisé par factorint. Comme tous les algorithmes classiques, cet algorithme peut être implémenté avec des circuits booléens — mais pour ce faire, nous aurons besoin d'un circuit distinct pour chaque longueur d'entrée possible. Si nous examinions les circuits résultants pour différentes longueurs d'entrée, nous verrions que leurs tailles croissent naturellement à mesure que la longueur d'entrée augmente — reflétant le fait que factoriser des entiers de 4 bits est beaucoup plus facile et nécessite bien moins d'opérations élémentaires que factoriser des entiers de 1024 bits, par exemple.

Cela nous amène à représenter le coût computationnel d'un algorithme par une fonction $t,$ définie de telle sorte que $t(n)$ est le nombre de portes dans le circuit qui implémente l'algorithme pour des entrées de $n$ bits. En termes plus formels, un algorithme dans le modèle de circuit booléen est décrit par une suite de circuits $\{C_1, C_2, C_3,\ldots\},$ où $C_n$ résout le problème dont on parle pour des entrées de $n$ bits (ou, plus généralement, pour des entrées dont la taille est paramétrée d'une certaine façon par $n$), et la fonction $t$ représentant le coût de cet algorithme est définie par

$$t(n) = \operatorname{size}(C_n).$$

Pour les circuits quantiques, la situation est similaire, où des circuits de plus en plus grands sont nécessaires pour accommoder des chaînes d'entrée de plus en plus longues.

Exemple : l'addition d'entiers

Pour expliquer davantage, prenons un moment pour considérer le problème de l'addition d'entiers, qui est bien plus simple que la factorisation des entiers ou même le calcul des PGCD.

Addition d'entiers

Entrée : entiers $N$ et $M$
Sortie : $N+M$

Comment pourrions-nous concevoir des circuits booléens pour résoudre ce problème ?

Pour simplifier, limitons-nous au cas où $N$ et $M$ sont tous deux des entiers non négatifs représentés par des chaînes de $n$ bits en notation binaire. Nous autorisons n'importe quel nombre de zéros non significatifs dans ces encodages, de sorte que

$$0\leq N,M\leq 2^n - 1.$$

La sortie sera une chaîne binaire de $(n+1)$ bits représentant la somme, ce qui est le nombre maximum de bits nécessaires pour exprimer le résultat.

Nous commençons par un algorithme — l'algorithme standard d'addition des représentations binaires — qui est l'analogue en base $2$ de la façon dont l'addition est enseignée dans les écoles primaires à travers le monde. Cet algorithme peut être implémenté avec des circuits booléens comme suit.

En commençant par les bits de poids faible, nous pouvons calculer leur XOR pour déterminer le bit de poids faible de la somme. Ensuite, nous calculons le bit de retenue, qui est le ET logique des deux bits de poids faible de $N$ et $M.$ Ces deux opérations ensemble sont parfois connues sous le nom de demi-additionneur.

En utilisant le circuit XOR que nous avons maintenant vu plusieurs fois, combiné avec une porte ET et deux portes FANOUT, nous pouvons construire un demi-additionneur avec 10 portes. Si pour une raison quelconque nous changions d'avis et décidions d'inclure les portes XOR dans notre ensemble d'opérations élémentaires, nous aurions besoin de 1 porte ET, 1 porte XOR et 2 portes FANOUT pour construire un demi-additionneur.

En passant aux bits de poids plus fort, nous pouvons utiliser une procédure similaire, mais en incluant cette fois le bit de retenue de chaque position précédente dans notre calcul. En cascadant deux demi-additionneurs et en prenant le OU des bits de retenue qu'ils produisent, nous pouvons créer ce qu'on appelle un additionneur complet.

Cela nécessite 21 portes au total : 2 portes ET, 2 portes XOR (nécessitant chacune 7 portes à implémenter), une porte OU et 4 portes FANOUT.

Enfin, en cascadant les additionneurs complets, nous obtenons un circuit booléen pour l'addition d'entiers non négatifs. Par exemple, le circuit suivant calcule la somme de deux entiers de 4 bits.

En général, cela nécessite

$$21 (n-1) + 10 = 21 n - 11$$

portes. Si nous avions décidé d'inclure les portes XOR dans notre ensemble d'opérations élémentaires, nous aurions besoin de $2n-1$ portes ET, $2n-1$ portes XOR, $n-1$ portes OU et $4n-2$ portes FANOUT, pour un total de $9n-5$ portes. Si en plus nous décidons de ne pas compter les portes FANOUT, c'est $5n-3$ portes.

Notation asymptotique

D'un côté, il est utile de savoir précisément combien de portes sont nécessaires pour effectuer divers calculs, comme dans l'exemple de l'addition d'entiers ci-dessus. Ces détails sont importants pour réellement construire les circuits.

D'un autre côté, si nous effectuons des analyses à ce niveau de détail pour tous les calculs qui nous intéressent, y compris ceux pour des tâches bien plus compliquées que l'addition, nous serons très vite noyés dans les détails. Pour garder les choses gérables, et pour supprimer intentionnellement les détails d'importance secondaire, nous utilisons typiquement la notation Grand-O lors de l'analyse des algorithmes. Grâce à cette notation, nous pouvons exprimer l'ordre de croissance des fonctions.

Formellement, si nous avons deux fonctions $g(n)$ et $h(n),$ nous écrivons que $g(n) = O(h(n))$ s'il existe un nombre réel positif $c > 0$ et un entier positif $n_0$ tels que

$$g(n) \leq c\cdot h(n)$$

pour tout $n \geq n_0.$ En général, $h(n)$ est choisi pour être une expression aussi simple que possible, afin que la notation puisse être utilisée pour révéler le comportement asymptotique d'une fonction en termes simples. Par exemple, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Cette notation peut être étendue aux fonctions à plusieurs arguments de manière assez directe. Par exemple, si nous avons deux fonctions $g(n,m)$ et $h(n,m)$ définies sur des entiers positifs $n$ et $m,$ nous écrivons que $g(n,m) = O(h(n,m))$ s'il existe un nombre réel positif $c > 0$ et un entier positif $k_0$ tels que

$$g(n,m) \leq c\cdot h(n,m)$$

chaque fois que $n+m \geq k_0.$

En reliant cette notation à l'exemple de l'addition d'entiers non négatifs, nous concluons qu'il existe une famille de circuits booléens $\{C_1, C_2,\ldots,\},$ où $C_n$ additionne deux entiers non négatifs de $n$ bits, telle que $\operatorname{size}(C_n) = O(n).$ Cela révèle la caractéristique la plus essentielle de la façon dont le coût de l'addition évolue avec la taille de l'entrée : il évolue linéairement.

Remarque aussi que cela ne dépend pas du détail spécifique de si nous considérons que les portes XOR ont un coût unitaire ou un coût de $7.$ En général, utiliser la notation Grand-O nous permet de faire des affirmations sur les coûts computationnels qui ne sont pas sensibles à de tels détails de bas niveau.

D'autres exemples

Voici quelques autres exemples de problèmes de la théorie algorithmique des nombres, en commençant par la multiplication.

Multiplication d'entiers

Entrée : entiers $N$ et $M$
Sortie : $NM$

Créer des circuits booléens pour ce problème est plus difficile que créer des circuits pour l'addition — mais en réfléchissant à l'algorithme de multiplication standard, nous pouvons concevoir des circuits de taille $O(n^2)$ pour ce problème (en supposant que $N$ et $M$ sont tous deux représentés par des représentations binaires de $n$ bits). Plus généralement, si $N$ a $n$ bits et $M$ a $m$ bits, il existe des circuits booléens de taille $O(nm)$ pour multiplier $N$ et $M.$

Il existe en fait d'autres façons de multiplier qui ont un meilleur comportement en termes d'échelle. Par exemple, l'algorithme de multiplication de Schönhage-Strassen peut être utilisé pour créer des circuits booléens pour multiplier deux entiers de $n$ bits à un coût $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ La complexité de cette méthode entraîne cependant beaucoup de surcoût, la rendant seulement pratique pour des nombres ayant des dizaines de milliers de bits.

Un autre problème de base est la division, que nous interprétons comme le calcul à la fois du quotient et du reste étant donné un diviseur et un dividende entiers.

Division d'entiers

Entrée : entiers $N$ et $M\neq0$
Sortie : entiers $q$ et $r$ satisfaisant $0\leq r < |M|$ et $N = q M + r$

Le coût de la division entière est similaire à celui de la multiplication : si $N$ a $n$ bits et $M$ a $m$ bits, il existe des circuits booléens de taille $O(nm)$ pour résoudre ce problème. Et comme pour la multiplication, des méthodes asymptotiquement supérieures sont connues.

Nous pouvons maintenant comparer les algorithmes connus pour le calcul des PGCD avec ceux pour l'addition et la multiplication. L'algorithme d'Euclide pour calculer le PGCD d'un nombre $N$ de $n$ bits et d'un nombre $M$ de $m$ bits nécessite des circuits booléens de taille $O(nm),$ similaire aux algorithmes standards pour la multiplication et la division. De même que pour la multiplication et la division, il existe des algorithmes de PGCD asymptotiquement plus rapides — dont certains nécessitant $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ opérations élémentaires pour calculer le PGCD de deux nombres de $n$ bits.

Un calcul un peu plus coûteux qui surgit en théorie des nombres est l'exponentiation modulaire.

Exponentiation modulaire entière

Entrée : entiers $N,$ $K,$ et $M$ avec $K\geq 0$ et $M\geq 1$
Sortie : $N^K \hspace{1mm} (\text{mod }M)$

Par $N^K\hspace{1mm} (\text{mod }M)$ nous entendons le reste de la division de $N^K$ par $M,$ c'est-à-dire l'entier unique $r$ satisfaisant $0\leq r < M$ et $N^K = q M + r$ pour un certain entier $q.$

Si $N$ a $n$ bits, $M$ a $m$ bits et $K$ a $k$ bits, ce problème peut être résolu par des circuits booléens de taille $O(k m^2 + nm).$ Ce n'est pas du tout évident. La solution ne consiste pas à calculer d'abord $N^K$ puis à prendre le reste, ce qui nécessiterait d'utiliser un nombre exponentiel de bits rien que pour stocker le nombre $N^K.$ Au contraire, nous pouvons utiliser l'algorithme d'exponentiation rapide (connu alternativement sous le nom de méthode binaire et exponentiation par carrés répétés), qui exploite la représentation binaire de $K$ pour effectuer tout le calcul modulo $M.$ En supposant que $N,$ $M$ et $K$ sont tous des nombres de $n$ bits, nous obtenons un algorithme en $O(n^3)$ — ou un algorithme en temps cubique. Et là encore, il existe des algorithmes connus qui sont plus complexes mais asymptotiquement plus rapides.

Coût de la factorisation des entiers

Contrairement aux algorithmes que nous venons de discuter, les algorithmes connus pour la factorisation des entiers sont bien plus coûteux — comme on pourrait s'y attendre d'après la discussion plus tôt dans la leçon.

Une approche simple pour la factorisation est la division par essais, où un algorithme parcourt la liste $2,\ldots,\sqrt{N}$ pour trouver un facteur premier d'un nombre d'entrée $N.$ Cela nécessite $O(2^{n/2})$ itérations dans le pire cas lorsque $N$ est un nombre de $n$ bits. Chaque itération nécessite une division par essai, ce qui représente $O(n^2)$ opérations élémentaires par itération (en utilisant un algorithme standard pour la division entière). On obtient des circuits de taille $O(n^2 2^{n/2}),$ qui est exponentielle en la taille d'entrée $n.$

Il existe des algorithmes pour la factorisation des entiers avec un meilleur comportement en termes d'échelle. Le crible algébrique des corps de nombres mentionné précédemment, par exemple, qui est un algorithme faisant appel à l'aléatoire, est généralement considéré (mais pas rigoureusement prouvé) comme nécessitant

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

opérations élémentaires pour factoriser des entiers de $n$ bits avec haute probabilité. Bien qu'il soit assez significatif que $n$ soit élevé à la puissance $1/3$ dans l'exposant de cette expression, le fait qu'il apparaisse dans l'exposant reste un problème qui cause un mauvais comportement en termes d'échelle — et explique en partie pourquoi RSA1024 reste hors de sa portée.

Coût polynomial versus coût exponentiel

Les algorithmes classiques pour l'addition, la multiplication, la division des entiers et le calcul des plus grands communs diviseurs nous permettent de résoudre ces problèmes en un clin d'œil pour des entrées de milliers de bits. L'addition a un coût linéaire tandis que les trois autres problèmes ont un coût quadratique (ou sous-quadratique en utilisant des algorithmes asymptotiquement rapides). L'exponentiation modulaire est plus coûteuse mais peut toujours être effectuée assez efficacement, avec un coût cubique (ou sous-cubique en utilisant des algorithmes asymptotiquement rapides).

Ce sont tous des exemples d'algorithmes à coût polynomial, ce qui signifie qu'ils ont un coût $O(n^c)$ pour un certain choix d'une constante fixe $c > 0.$ En guise d'approximation grossière de premier ordre, les algorithmes à coût polynomial sont abstraitement considérés comme représentant des algorithmes efficaces.

En revanche, les algorithmes classiques connus pour la factorisation des entiers ont un coût exponentiel. Parfois, le coût du crible algébrique des corps de nombres est décrit comme sous-exponentiel parce que $n$ est élevé à la puissance $1/3$ dans l'exposant, mais en théorie de la complexité il est plus typique de réserver ce terme aux algorithmes dont le coût est

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

pour tout $\varepsilon > 0.$ Les problèmes dits NP-complets sont une classe de problèmes dont on ne sait pas (et dont on conjecture largement qu'ils n'ont pas) d'algorithmes à coût polynomial. Une formulation à base de circuits de l'hypothèse du temps exponentiel postule quelque chose d'encore plus fort, à savoir qu'aucun problème NP-complet ne peut avoir un algorithme à coût sous-exponentiel.

L'association des algorithmes à coût polynomial avec les algorithmes efficaces doit être comprise comme une abstraction approximative. Bien sûr, si le coût d'un algorithme évolue en $n^{1000}$ ou $n^{1000000}$ pour des entrées de taille $n,$ c'est exagéré de décrire cet algorithme comme efficace. Cependant, même un algorithme dont le coût évolue en $n^{1000000}$ doit faire quelque chose d'ingénieux pour éviter d'avoir un coût exponentiel, ce qui est généralement ce que l'on attend des algorithmes basés d'une façon ou d'une autre sur la « force brute » ou la « recherche exhaustive ». Même les raffinements sophistiqués du crible algébrique des corps de nombres, par exemple, ne parviennent pas à éviter ce comportement exponentiel en termes de coût. Les algorithmes à coût polynomial, en revanche, parviennent à tirer parti de la structure du problème d'une manière qui évite un comportement exponentiel.

En pratique, l'identification d'un algorithme à coût polynomial pour un problème n'est qu'une première étape vers une véritable efficacité. Grâce à des raffinements algorithmiques, les algorithmes à coût polynomial avec de grands exposants peuvent parfois être améliorés de manière spectaculaire, ramenant le coût à un comportement polynomial plus « raisonnable ». Parfois les choses deviennent plus faciles quand on sait qu'elles sont possibles — donc l'identification d'un algorithme à coût polynomial pour un problème peut aussi avoir pour effet d'inspirer de nouveaux algorithmes encore plus efficaces.

En considérant les avantages de l'informatique quantique sur l'informatique classique, nos regards se tournent généralement d'abord vers les avantages exponentiels, ou du moins super-polynomiaux — en trouvant idéalement des algorithmes quantiques à coût polynomial pour des problèmes dont on ne connaît pas d'algorithmes classiques à coût polynomial. Les avantages théoriques de cet ordre ont le plus de chances de mener à de véritables avantages pratiques — mais identifier de tels avantages est un défi extrêmement difficile. Seuls quelques exemples sont actuellement connus, mais la recherche continue.

Les avantages polynomiaux (mais non super-polynomiaux) en coût computationnel du quantique sur le classique sont également intéressants et ne doivent pas être écartés — mais étant donné l'écart actuel entre les technologies de calcul quantique et classique, ils semblent actuellement assez moins convaincants. Un jour, cependant, ils pourraient devenir significatifs. L'algorithme de Grover, par exemple, qui est abordé dans une leçon ultérieure, offre un avantage quadratique du quantique sur le classique pour ce qu'on appelle la recherche non structurée, et a un potentiel d'applications larges.

Un coût caché du calcul par circuits

Il y a une dernière question qui mérite d'être mentionnée, bien que nous ne nous en préoccupions pas davantage dans ce cours. Il y a un coût computationnel « caché » lorsqu'on travaille avec des circuits, et il concerne les spécifications des circuits eux-mêmes. À mesure que les entrées deviennent de plus en plus longues, des circuits de plus en plus grands sont nécessaires — mais nous devons avoir accès aux descriptions de ces circuits d'une façon ou d'une autre pour pouvoir les implémenter.

Pour tous les exemples dont nous avons discuté, ou dont nous discuterons dans les leçons suivantes, il existe un algorithme sous-jacent à partir duquel les circuits sont dérivés. Généralement, les circuits d'une famille suivent un motif de base facile à extrapoler pour des entrées de plus en plus grandes, comme cascader des additionneurs complets pour créer des circuits booléens pour l'addition ou effectuer des couches de portes Hadamard et d'autres portes selon un motif simple à décrire.

Mais que se passe-t-il s'il y a des coûts computationnels prohibitifs associés aux motifs dans les circuits eux-mêmes ? Par exemple, la description de chaque membre $C_n$ dans une famille de circuits pourrait, en principe, être déterminée par une fonction de $n$ extrêmement difficile à calculer.

La réponse est que c'est effectivement un problème — et nous devons donc imposer des restrictions supplémentaires aux familles de circuits au-delà d'avoir un coût polynomial pour qu'elles représentent véritablement des algorithmes efficaces. La propriété d'uniformité pour les circuits y répond en stipulant que, dans diverses formulations précises, il doit être computationnellement facile d'obtenir la description de chaque circuit d'une famille. Toutes les familles de circuits dont nous discuterons possèdent cette propriété — mais c'est néanmoins une question importante à connaître en général lorsqu'on étudie les modèles de calcul par circuits d'un point de vue formel.