1. Algorithme de Grover : Introduction et Complexité [0]

thumbnail
  1. L'algorithme de Grover est un algorithme de recherche dans une liste. [0]
  2. Complexité des algorithmes de recherche classiques : [1]
    1. Liste ordonnée (triée) :
      1. On peut effectuer une recherche par dichotomie. [3]
      2. Ceci demande jusqu'à tests, ce qui est une complexité faible. [3]
    2. Liste non ordonnée :
      1. On doit tester les éléments un par un. [5]
      2. La complexité est en . [5]
  3. Algorithme de Grover (Liste non ordonnée) : [6]
    1. Il fonctionne sur les ordinateurs quantiques. [6]
    2. Sa complexité est en . [6]
    3. C'est moins bien que la recherche sur liste ordonnée, mais bien mieux que la recherche classique sur liste non ordonnée. [6]
    4. Exemple : Pour un milliard d'éléments (), la recherche classique demande tests. [7]
    5. L'algorithme de Grover ne demande que 30 000 tests, ce qui est un gain énorme. [7]
  4. Inconvénient de l'algorithme de Grover : [8]
    1. C'est un algorithme probabiliste. [8]
    2. Il ne renvoie pas le bon résultat dans tous les cas (ex: correct dans 90% des cas). [9]
    3. Ce n'est pas toujours grave, car on peut souvent vérifier la réponse. [10]
    4. Si la réponse est incorrecte, on peut relancer l'algorithme pour obtenir la bonne réponse. [10]

2. Illustration Naïve de l'Algorithme de Grover [11]

thumbnail
  1. Scénario de recherche : [11]
    1. On a une liste de rectangles. [11]
    2. On cherche le rang du rectangle rouge (ici, le numéro 6). [12]
  2. Algorithme classique : [14]
    1. On teste chaque rectangle séquentiellement ("Es-tu le rectangle rouge ? Non."). [14]
    2. Il faut tester beaucoup de rectangles. [15]
  3. Algorithme quantique de Grover : [16]
    1. Les rectangles représentent les coefficients d'un état quantique (ex: 8 rectangles pour 3 qubits). [16]
    2. Initialement, tous les rectangles ont la même hauteur. [18]
    3. Une mesure initiale donnerait chaque rang de façon équiprobable, sans avancement. [19]
    4. Opération 1 : Changement de signe (Oracle) : [20]
      1. On effectue une opération globale : "Si tu es le rectangle rouge, change ton signe". [20]
      2. Cette opération est faite simultanément sur tous les rectangles. [21]
      3. Les rectangles noirs restent inchangés. [23]
      4. Le rectangle rouge a maintenant la même hauteur, mais négative. [23]
    5. Opération 2 : Calcul de la moyenne : [24]
      1. On calcule la moyenne de la hauteur des rectangles. [24]
      2. Comme un rectangle est négatif, la moyenne baisse légèrement. [24]
      3. La moyenne est maintenant un peu en dessous de la hauteur des rectangles noirs. [24]
    6. Opération 3 : Symétrie par rapport à la moyenne : [25]
      1. On effectue une symétrie par rapport à la moyenne calculée. [25]
      2. Les rectangles noirs (au-dessus de la moyenne) se retrouvent un peu en dessous. [25]
      3. Le rectangle rouge (très en dessous de la moyenne) se retrouve très au-dessus de la moyenne. [25]
      4. Le rectangle rouge se distingue clairement. [25]
    7. Mesure finale : [26]
      1. Si on mesure maintenant, on a beaucoup plus de chances d'obtenir le rang correspondant au rectangle rouge. [26]
      2. Si les rectangles noirs sont encore de taille non négligeable, on recommence l'algorithme. [27]
      3. Les rectangles noirs deviennent de plus en plus petits, et le rouge de plus en plus grand. [28]
      4. Après itération, on aura de très fortes probabilités de mesurer le bon rang. [28]

3. Modélisation et Circuit de l'Algorithme de Grover [29]

thumbnail

3.1. Modélisation de l'élément recherché (Rang ) [30]

  1. L'algorithme de Grover consiste à exécuter un circuit une fois. [29]
  2. Définition de la fonction $f$ (Oracle) : [30]
    1. est définie de vers . [31]
    2. est la liste des entiers de 0 à . [32]
    3. La fonction vaut 1 uniquement au rang (le rang à déterminer). [34]
    4. Pour tout autre rang , . [36]
    5. Ceci signifie que le rang est spécial (), et partout ailleurs vaut zéro. [37]
  3. Description du circuit : [38]
    1. Le circuit est composé de lignes quantiques (regroupées) et une ligne quantique à part. [38]
    2. Le circuit se termine par une mesure des premières lignes. [39]
    3. La mesure renvoie bits, qui est l'écriture binaire d'un entier. [40]
    4. Résultat de la mesure : La mesure renvoie le rang recherché avec une probabilité très forte. [41]
    5. La probabilité est supérieure à . [41]
    6. Exemple : Si , la probabilité est très proche de 1. [42]
    7. Si le rang correct n'est pas obtenu, on relance l'algorithme pour avoir une très forte probabilité de tomber sur . [43]

3.2. Détails du Circuit et Complexité [45]

  1. Initialisation : [45]
    1. Les premières lignes quantiques sont initialisées avec . [45]
    2. La ligne spéciale est initialisée par . [45]
  2. Application des portes : [46]
    1. On applique la transformation d'Hadamard (porte H) sur chacune des premières lignes. [46]
    2. On applique aussi une porte H sur la ligne spéciale. [46]
    3. Ensuite, on a une succession de portes de Grover. [46]
  3. Porte de Grover : [49]
    1. C'est la combinaison de deux portes. [49]
    2. La première est l'oracle associé à la fonction . [50]
    3. La seconde est une symétrie . [50]
  4. Nombre d'itérations et Complexité : [51]
    1. Il faut utiliser environ portes de Grover. [51]
    2. Chaque application de l'oracle évalue la fonction , ce qui correspond à une complexité 1. [52]
    3. Chaque porte de Grover correspond à une complexité 1. [52]
    4. Il y a environ portes (en ignorant le coefficient ). [53]
    5. La complexité est donc en . [53]

4. Vision Géométrique de la Transformation de Grover [54]

thumbnail
  1. Représentation des Qubits : [55]
    1. Les qubits sont représentés dans un plan à deux axes. [55]
    2. L'axe vertical représente le qubit de base . [56]
    3. L'axe horizontal représente , la somme de tous les autres qubits de base (sauf ). [56]
    4. L'état est la somme de tous les états quantiques de base, y compris . [57]
    5. L'état initial est très proche de l'axe horizontal. [58]
    6. Il forme un petit angle avec l'axe horizontal. [58]
  2. Transformation de Grover (Rotation) : [59]
    1. Géométriquement, la transformation de Grover est une rotation d'angle . [59]
    2. L'état s'éloigne de l'axe horizontal et se rapproche de l'axe vertical. [59]
    3. On itère ces transformations de Grover (rotations d'angle ). [60]
    4. On s'arrête lorsque l'état est le plus près possible de l'axe vertical. [60]
    5. Quand le qubit est proche de l'axe vertical (), on le mesure. [61]
    6. Il y a de grandes chances que le qubit s'effondre sur , permettant de récupérer le rang . [61]
  3. La transformation de Grover est composée de l'oracle, suivi d'une symétrie. [62]

5. Détails de l'Oracle et de la Symétrie [63]

thumbnail

5.1. L'Oracle (Symétrie Axiale Horizontale) [63]

  1. L'oracle est associé à la fonction , qui vaut 1 uniquement au rang . [63]
  2. Action de l'oracle : [64]
    1. Si on applique l'oracle avec un rang , on obtient . [64]
    2. Si , on obtient (signe négatif). [64]
    3. Pour tous les autres rangs , on obtient (signe positif). [64]
    4. En ignorant le facteur commun, le rang est distingué par un signe . [65]
    5. Si l'oracle est appliqué à l'état (somme de tous les états), seul le terme aura un signe . [68]
  3. Interprétation géométrique de l'oracle : [70]
    1. Le plan distingue l'axe vertical () et l'axe horizontal (somme des autres états). [71]
    2. L'oracle change le signe devant . [74]
    3. Ceci transforme le qubit en son symétrique par rapport à l'axe horizontal. [74]

5.2. La Symétrie (Symétrie Axiale d'Axe ) [75]

  1. est la seconde partie de la transformation de Grover. [75]
  2. L'état est l'image de par la transformation d'Hadamard. [76]
  3. est la somme normalisée de tous les états quantiques de base. [76]
  4. Définition de la symétrie $S_{\psi_H}$ : [77]
    1. . [77]
    2. L'application à un qubit donne . [77]
  5. Interprétation géométrique de $S_{\psi_H}$ : [78]
    1. Géométriquement, correspond à une symétrie d'axe . [78]
    2. Si est le vecteur vert, l'application de sur un vecteur bleu donne le vecteur rouge. [79]
    3. Le vecteur rouge est le symétrique du vecteur bleu par rapport à l'axe vert. [79]

5.3. Conclusion : La Transformation de Grover est une Rotation [80]

  1. La transformation de Grover est l'oracle suivi de la symétrie . [81]
  2. Composition des symétries : [82]
    1. L'oracle correspond à une symétrie axiale d'axe horizontal (). [82]
    2. La symétrie est une symétrie axiale d'axe (l'axe vert). [82]
    3. L'angle entre ces deux axes est . [82]
    4. Attention : En réalité, cet angle est très petit. [83]
    5. La composition de deux symétries axiales donne une rotation. [84]
    6. L'angle de cette rotation est le double de l'angle entre les deux axes. [84]
    7. La transformation de Grover est donc une rotation d'angle . [85]
    8. L'image d'un qubit par est obtenue en effectuant la rotation d'angle . [85]