Présentation

Dans cette première leçon du cours, nous allons formuler un cadre algorithmique simple - connu sous le nom de modèle de requête - et explorer les avantages qu'offrent les ordinateurs quantiques dans ce cadre.

Le modèle d'interrogation de l'informatique est comme une boîte de Pétri pour les idées algorithmiques quantiques. Il est rigide et peu naturel dans le sens où il ne représente pas avec précision les types de problèmes de calcul qui nous intéressent généralement dans la pratique, mais il s'est néanmoins avéré incroyablement utile en tant qu'outil de développement de techniques algorithmiques quantiques. Il s'agit notamment des algorithmes quantiques les plus connus, tels que l'algorithme de Shor pour la factorisation des nombres entiers. Le modèle de requête est également un cadre très utile pour expliquer les techniques algorithmiques quantiques.

Après avoir présenté le modèle d'interrogation lui-même, nous discuterons du tout premier algorithme quantique découvert, à savoir l' algorithme de Deutsch, ainsi que d'une extension de l'algorithme de Deutsch connue sous le nom d' algorithme de Deutsch-Jozsa. Ces algorithmes démontrent les avantages quantifiables des ordinateurs quantiques par rapport aux ordinateurs classiques dans le contexte du modèle de requête. Nous discuterons ensuite d'un algorithme quantique connu sous le nom d' algorithme de Simon, qui offre un avantage plus robuste et plus satisfaisant des calculs quantiques par rapport aux calculs classiques, pour des raisons qui seront expliquées lorsque nous l'aborderons.

Vidéo de cours

Dans la vidéo suivante, John Watrous présente le contenu de cette leçon sur les algorithmes de requête quantique. Vous pouvez également ouvrir la vidéo YouTube pour cette leçon dans une fenêtre séparée. Télécharger les diapositives de cette leçon.