Introduction
Les algorithmes quantiques offrent des avantages prouvables sur les algorithmes classiques dans le modèle de calcul par requêtes. Mais qu'en est-il d'un modèle de calcul plus standard, où les entrées des problèmes sont fournies explicitement plutôt que sous la forme d'un oracle ou d'une boîte noire ? Il s'avère que c'est une question bien plus difficile à laquelle répondre, et pour y répondre nous devons d'abord établir une base solide sur laquelle fonder notre investigation. Tel est l'objectif principal de cette leçon.
Nous commencerons par discuter du coût de calcul, pour les calculs classiques et quantiques, et de la façon dont il peut être mesuré. C'est une notion générale qui peut s'appliquer à un large éventail de problèmes de calcul — mais pour rester simple, nous l'examinerons principalement à travers le prisme de la théorie algorithmique des nombres, qui aborde des tâches de calcul probablement familières à la plupart des lecteurs, notamment l'arithmétique de base, le calcul des plus grands communs diviseurs et la factorisation des entiers. Bien que la théorie algorithmique des nombres soit un domaine d'application étroit, ces problèmes se prêtent bien à illustrer les enjeux fondamentaux (et ils se trouvent aussi être très pertinents pour la leçon suivante).
Notre attention se porte sur les algorithmes, plutôt que sur le matériel en constante amélioration sur lequel ils s'exécutent. En conséquence, nous nous intéresserons davantage à la façon dont le coût d'exécution d'un algorithme évolue à mesure que les instances de problèmes sur lesquelles il est exécuté augmentent en taille, plutôt qu'au nombre de secondes, minutes ou heures qu'un calcul particulier requiert. Nous nous concentrons sur cet aspect du coût de calcul en reconnaissant que les algorithmes ont une importance fondamentale, et qu'ils seront naturellement déployés sur des instances de problèmes de plus en plus grandes grâce à un matériel plus rapide et plus fiable au fil du développement technologique.
Enfin, nous nous tournerons vers une tâche d'une importance critique, qui consiste à exécuter des calculs classiques sur des ordinateurs quantiques. La raison pour laquelle cette tâche est importante n'est pas que nous espérons remplacer les ordinateurs classiques par des ordinateurs quantiques — ce qui semble extrêmement improbable dans un avenir proche, si tant est que cela arrive un jour — mais plutôt parce qu'elle ouvre de nombreuses possibilités intéressantes pour les algorithmes quantiques. Plus précisément, les calculs classiques s'exécutant sur des ordinateurs quantiques deviennent disponibles en tant que sous-routines, exploitant ainsi efficacement des décennies de recherche et de développement sur les algorithmes classiques dans la quête d'avantages computationnels quantiques.
Vidéo de la leçon
Dans la vidéo suivante, John Watrous te guide à travers le contenu de cette leçon sur les fondements algorithmiques quantiques. Tu peux également ouvrir la vidéo YouTube de cette leçon dans une fenêtre séparée. Télécharge les diapositives de cette leçon.