Contrairement à une certaine croyance populaire, les ordinateurs ne sont pas tout-puissants (et ils ne le seront jamais). Il existe des problèmes qui ne peuvent pas être résolus par un ordinateur et d'autres problèmes dont le temps de résolution (par un ordinateur) est totalement déraisonnable. La complexité algorithmique permet de formaliser les limites de l'informatique. Avec l'avènement des ordinateurs quantiques, on peut se demander si ces limites théoriques vont être bouleversées. Dans cet exposé, nous tenterons de donner quelques éléments de réponse à cette question. L'exposé sera divisé en deux parties. Dans un premier temps, nous ferons connaissance avec la complexité algorithmique (classique). Ensuite, nous présenterons brièvement quelques concepts théoriques liés aux ordinateurs quantiques, et tenterons de comprendre en quoi ces derniers diffèrent des ordinateurs classiques.
