Piste B · Informatique quantique · Découverte · 20 min

Ce que les ordinateurs quantiques peuvent et ne peuvent pas faire

Accélérations connues, limites démontrées et idées reçues.

Prérequis : Superposition et intrication pour calculer

Pas un ordinateur plus rapide en tout

Un ordinateur quantique n'accélère pas tous les calculs. Pour la plupart des tâches courantes, un ordinateur classique reste plus adapté. Il existe en revanche des problèmes précis pour lesquels on connaît des algorithmes quantiques nettement plus efficaces que les meilleurs algorithmes classiques connus.

Deux exemples reviendront dans la piste B. L'algorithme de Shor factorise de grands entiers en temps polynomial, ce qui menace certains chiffrements actuels. L'algorithme de Grover accélère la recherche dans une liste non structurée, mais l'accélération est seulement quadratique : il faut de l'ordre de $\sqrt N$ requêtes au lieu de $N$ .

Les ordinateurs quantiques ne résolvent pas, à notre connaissance, les problèmes NP-complets en temps polynomial. Méfiez-vous des annonces qui affirment le contraire.

Visualisation interactive

Pour une recherche dans une liste non triée de N éléments : nombre moyen de requêtes classiques ( $N/2$ ) contre l'ordre de grandeur de Grover ( $\approx \tfrac\pi4\sqrt N$ ).

Taille de la liste N1,0×10^6

Échelle logarithmique

Classique, en moyenne N/2

5,00×10^5

Grover ≈ (π/4)√N

7,85×10^2

Questions de compréhension

1. L'accélération de Grover est…

2. Quel algorithme menace certains systèmes de chiffrement à clé publique ?

3. Sait-on qu'un ordinateur quantique résout les problèmes NP-complets en temps polynomial ?

Connectez-vous pour enregistrer vos résultats et votre progression.

Au laboratoire : Algorithme de Grover pas à pas

Exercice appliqué

Combien d'itérations de Grover faut-il environ pour $N = 10^6$ ? Comparez au nombre moyen de requêtes classiques.

Code exécutable

Comparez les deux coûts pour plusieurs tailles de liste. Python s'exécute dans votre navigateur (Pyodide), rien n'est envoyé à un serveur.

Tuteur IA