Pourquoi un ordinateur quantique peut-il calculer plus vite ?

Un ordinateur quantique pourrait-il résoudre en quelques minutes un problème qui demanderait des années à une machine classique ? Certaines recherches laissent entrevoir de tels écarts, mais elles ne signifient pas que tous les logiciels deviendront plus rapides. La différence ne tient pas seulement au processeur : elle dépend avant tout de la manière dont le problème est formulé et de l’algorithme employé.

Pour le comprendre, nous allons suivre une idée simple, celle des interférences quantiques, avant d’examiner trois algorithmes célèbres : Deutsch–Jozsa, Shor et Grover. L’histoire des machines et des qubits est abordée séparément dans notre histoire de l’informatique quantique. Ici, une question nous guidera : qu’est-ce qu’un algorithme quantique permet réellement d’économiser ?

Calculer plus vite ne signifie pas seulement avoir un processeur plus puissant

Imaginons deux méthodes pour additionner les nombres de 1 à 100. La première les additionne un à un ; la seconde utilise directement la formule 100 × 101 ÷ 2. Le résultat est identique, mais le travail demandé n’est pas le même. Cette différence illustre une notion fondamentale : le choix de l’algorithme peut compter davantage que la vitesse de l’ordinateur.

Les informaticiens étudient la complexité algorithmique, c’est-à-dire l’évolution du travail nécessaire lorsque la taille d’un problème augmente. Une méthode peut demander un nombre d’opérations proportionnel à cette taille ; une autre peut voir son coût doubler à chaque élément ajouté. Pour donner un ordre de grandeur, 2³⁰ dépasse un milliard. Les méthodes classiques disposent toutefois de nombreuses astuces pour éviter les recherches naïves : un problème comportant beaucoup de possibilités n’est pas automatiquement impossible à résoudre.

Un algorithme quantique ne gagne donc pas parce qu’il « réfléchit plus vite ». Dans certains problèmes, il organise le calcul autrement et utilise moins d’étapes d’un type précis. Reste à comprendre comment.

Du bit au qubit : pourquoi les interférences sont essentielles

Un bit classique vaut 0 ou 1. Un qubit, lui, peut être préparé dans une superposition de ces deux états. Pourtant, lorsqu’on le mesure, on obtient toujours un seul résultat : 0 ou 1. Si la notion de qubit n’est pas bien comprise je vous invite à lire l’article d’introduction sur l’informatique quantique.

L’intérêt de cette superposition repose notamment sur les interférences quantiques. Imaginons deux vagues qui se rencontrent : selon leur décalage, elles peuvent se renforcer ou s’annuler.

Un phénomène comparable se produit avec les qubits. Les amplitudes quantiques associées aux résultats possibles peuvent se renforcer ou se compenser, modifiant ainsi les probabilités de les obtenir.

Pour exploiter ce phénomène, les ordinateurs quantiques utilisent des opérations appelées portes quantiques. L’une des plus simples est la porte de Hadamard (H). Appliquée à un qubit initialement à 0, elle crée une superposition donnant 50 % de chances de mesurer 0 et 50 % de mesurer 1.

Si l’on applique une seconde porte H, sans mesure intermédiaire, les amplitudes interfèrent : celles associées au résultat 1 s’annulent et le qubit revient à l’état 0. La seconde opération ne réalise pas un deuxième tirage au hasard : elle exploite la cohérence conservée depuis la première.

C’est ce principe qu’exploitent les algorithmes quantiques : organiser les interférences pour favoriser certains résultats plutôt que d’autres.

 

C’est pour cette raison que l’expression « un ordinateur quantique essaie toutes les réponses en même temps » est trompeuse. Il peut agir sur une superposition, mais il ne suffit pas de la mesurer pour récupérer toutes les réponses. La difficulté consiste à faire apparaître une information utile grâce aux interférences.

Deutsch : une petite boîte noire, une vraie différence

Imaginons une boîte noire qui reçoit un bit et renvoie un bit. Nous ignorons sa règle : elle peut toujours répondre 0, toujours répondre 1, reproduire l’entrée ou l’inverser. Nous ne cherchons pas à connaître toute la règle, seulement à savoir si les deux réponses possibles sont identiques ou différentes.

Avec une méthode classique exigeant une réponse certaine, il faut interroger la boîte avec 0 et avec 1. Si la première réponse est 0, par exemple, impossible de savoir sans la seconde si la boîte répond toujours 0 ou si elle reproduit simplement son entrée.

En 1985, David Deutsch propose une approche quantique. Dans la formulation usuelle du problème, une version quantique de la boîte, capable d’agir sur une superposition, permet de déterminer cette propriété avec une seule interrogation. L’algorithme ne lit pas les deux réponses séparément : il utilise leurs relations de phase pour savoir si elles sont égales ou différentes.

Le gain semble modeste, une interrogation au lieu de deux. Pourtant, il démontre une idée nouvelle : un circuit quantique peut obtenir une propriété globale sans consulter séparément toutes les valeurs.

Deutsch–Jozsa : une interrogation au lieu de plusieurs

En 1992, Deutsch et Richard Jozsa étendent cette expérience. Supposons que la boîte accepte désormais trois bits : il existe huit entrées possibles, de 000 à 111. Elle renvoie toujours un seul bit, 0 ou 1.

Une règle est annoncée à l’avance : la fonction est soit constante (elle répond toujours la même chose), soit équilibrée (elle répond 0 pour exactement quatre entrées et 1 pour les quatre autres). Les autres cas sont exclus. Cette condition est essentielle : on parle d’un problème à promesse.

Dans le pire des cas, une méthode classique qui doit conclure avec certitude interroge cinq entrées. Si les quatre premières donnent 0, la fonction peut encore être constante ou équilibrée. La cinquième réponse tranche nécessairement. Le circuit quantique idéal de Deutsch–Jozsa n’effectue, lui, qu’une interrogation de l’oracle quantique.

Comment est-ce possible ? Pour chaque entrée, l’algorithme associe une phase que l’on peut représenter, de façon simplifiée, par un signe : + pour une réponse 0 et − pour une réponse 1. Si la fonction est constante, les huit signes sont identiques : leur somme vaut +8 ou −8. Si elle est équilibrée, quatre signes sont positifs et quatre négatifs : la somme vaut 0. Le circuit transforme cette différence en un résultat mesurable : 000 indique une fonction constante ; tout autre résultat indique une fonction équilibrée, dans le modèle idéal. Il n’affiche pas les huit réponses : il révèle la propriété qui nous intéresse.

Il faut cependant comparer des méthodes soumises aux mêmes exigences. Si l’ordinateur classique accepte une petite probabilité d’erreur, quelques entrées choisies au hasard peuvent suffire à obtenir une réponse très probable. Deutsch–Jozsa offre donc une séparation remarquable face aux méthodes classiques exactes, mais pas une accélération exponentielle générale face à toutes les méthodes classiques possibles.

Shor et Grover : des problèmes aux enjeux plus concrets

La boîte noire de Deutsch–Jozsa est surtout un outil pour comprendre les principes. D’autres algorithmes s’attaquent à des questions plus proches des usages réels.

Shor : retrouver les facteurs d’un grand nombre

En 1994, Peter Shor présente un algorithme quantique permettant de factoriser des entiers en un temps qui croît polynomialement avec leur longueur binaire, sur une machine quantique idéale suffisamment puissante. Son idée s’appuie sur la recherche d’une période mathématique, et non sur l’essai simultané de tous les diviseurs possibles.

C’est important pour la cryptographie : la sécurité de RSA repose notamment sur la difficulté pratique de factoriser certains très grands nombres avec les méthodes classiques connues. L’algorithme de Shor pourrait donc menacer ce système si des ordinateurs quantiques assez fiables et assez grands deviennent disponibles. Il ne signifie pas que toutes les techniques cryptographiques seraient compromises. Le NIST a d’ailleurs publié en 2024 ses premiers standards de cryptographie post-quantique, destinés à résister aux attaques quantiques connues.

Grover : réduire le nombre d’essais d’une recherche

En 1996, Lov Grover propose une méthode pour rechercher une solution parmi N possibilités lorsque le problème ne présente pas de structure exploitable. Là où une recherche classique peut nécessiter un nombre d’essais proportionnel à N, l’algorithme de Grover demande un nombre de requêtes de l’ordre de √N, avec une forte probabilité de réussite.

Pour un million de candidats, cela représente un ordre de grandeur d’un millier de requêtes quantiques plutôt qu’un million d’essais classiques. Mais il faut disposer d’un moyen quantique de reconnaître la bonne réponse, et son coût compte lui aussi. Surtout, une liste triée ou un problème doté d’une structure utile peut déjà se résoudre bien plus efficacement sur un ordinateur classique. Grover n’accélère pas automatiquement toutes les recherches.

Du résultat théorique à la machine réelle

Ces résultats portent sur des problèmes et des ressources bien définis. Dire qu’un circuit n’interroge une boîte noire qu’une fois ne veut pas dire qu’il termine instantanément : préparer les qubits, construire la transformation interrogée, exécuter les opérations et mesurer la réponse prend du temps. Dans certains cas, mettre les données sous une forme accessible à l’ordinateur quantique peut même coûter très cher.

Le matériel ajoute une autre difficulté. Les qubits sont sensibles aux perturbations ; les erreurs s’accumulent lorsque les calculs s’allongent. Les dispositifs de correction d’erreurs quantiques cherchent à protéger l’information, mais ils mobilisent de nombreux qubits physiques pour former des qubits logiques plus fiables. Des résultats expérimentaux, notamment sur les mémoires quantiques protégées, montrent des progrès réels sans constituer pour autant la démonstration d’une application industrielle complète.

La simulation de molécules et de matériaux reste une piste importante : des systèmes quantiques pourraient aider à étudier des propriétés physiques difficiles à calculer classiquement. Mais, ici encore, il faut comparer une tâche précise, avec la même qualité de résultat. Ni la météo, ni la logistique, ni la découverte de médicaments ne deviennent plus rapides par la seule présence d’un processeur quantique.

À quelles conditions peut-on parler d’un avantage quantique ?

Pour évaluer une annonce, trois questions suffisent à commencer : quel problème exact a été résolu ? Quelle ressource a été économisée : des requêtes, des opérations ou du temps réel ? Et avec quelle précision, quel taux de réussite et quel coût de préparation ? Une comparaison sérieuse doit aussi utiliser les meilleures méthodes classiques pertinentes, et pas seulement une méthode volontairement naïve.

La leçon de Deutsch–Jozsa reste alors précieuse. Les interférences peuvent permettre d’obtenir certaines informations avec moins d’interrogations. Shor et Grover montrent que cette idée peut conduire à des gains plus importants, mais de nature différente. L’avenir des algorithmes quantiques ne repose donc pas sur une accélération universelle : il dépend de notre capacité à repérer les problèmes dont la structure se prête réellement à ces nouvelles méthodes de calcul.

Sources scientifiques et documents de référence

• IBM Quantum Learning — Introduction aux algorithmes par requêtes : distinction entre nombre de requêtes et coût global du calcul.
• IBM Quantum Learning — Deutsch–Jozsa : formulation du problème et rôle des interférences.
• IBM Quantum Learning — Algorithme de Shor : factorisation et recherche de période.
• IBM Quantum Learning — Algorithme de Grover : recherche non structurée et gain quadratique.
• NIST — Standards post-quantiques (2024) : conséquences pour la cryptographie.
• Google Quantum AI et collaborateurs, Nature (2025) : correction des erreurs et mémoires quantiques.