Calculateur quantique - Définition

Introduction

Mécanique quantique

Postulats de la mécanique quantique Histoire de la mécanique quantique Concepts fondamentaux État quantique · Superposition · Observable · Intrication · Mesure · Principe d'incertitude · de correspondance · Dualité · Décohérence Expériences Fentes de Young · Expérience de Stern et Gerlach · Chat de Schrödinger · Gomme quantique · Paradoxe EPR · Téléportation quantique · Expérience d'Aspect Formalisme Notation Bra-Ket · Équation de Schrödinger · Matrice densité · Représentation de Schrödinger · de Heisenberg · d'interaction Statistiques Maxwell-Boltzmann · Échange · Fermi-Dirac · Fermion · Bose-Einstein · Boson Théories avancées Théorie quantique des champs · Axiomes de Wightman · Électrodynamique quantique · Chromodynamique quantique · Gravité quantique · Diagramme de Feynman Interprétations Problème de la mesure · Copenhague · Ensemble · Variables cachées · Transactionnelle · Mondes multiples · Histoires consistantes · Logique quantique · Réduction par l'observation (consciente) Physiciens Planck · de Broglie · Schrödinger · Heisenberg · Bohr · Pauli · Born · Dirac · von Neumann · Einstein · Bohm · Feynman · Everett · Penrose

Cette boîte : voir • disc. • mod.

Un calculateur quantique ou ordinateur quantique, repose sur des propriétés quantiques de la matière : superposition et intrication d'états quantiques. De petits calculateurs quantiques ont déjà été construits dès les années 1990 et des progrès sont en cours. Ce domaine en essor est soutenu financièrement par plusieurs organisations, entreprises ou gouvernements, du fait de l'importance de l'enjeu : au moins un algorithme conçu pour utiliser un circuit quantique, l'algorithme de Shor, rendrait possible de nombreux calculs combinatoires hors de portée d'un ordinateur classique en l'état actuel des connaissances. La possibilité de casser les méthodes cryptographiques classiques est souvent mise en avant. La difficulté actuelle majeure (depuis 2008) concerne la réalisation physique de l'élément de base de l'ordinateur quantique : le qubit. Le phénomène de décohérence, c’est-à-dire de perte des effets quantiques sur le long terme, est le principal frein au développement de l’ordinateur quantique.

Intérêt des calculateurs quantiques

Selon l'empirique loi de Moore, la taille des transistors approchera celle de l'atome à l'horizon 2020. A cette échelle, les effets quantiques perturbent le fonctionnement des composants électroniques. Si de grands (plus de 300 qubits) calculateurs quantiques pouvaient être construits — ce qui n'est pas assuré — ils seraient capables d'après David Deutsch de simuler le comportement de l’univers lui-même. Ils pourraient également résoudre des problèmes de cryptanalyse en un temps polynomial et non exponentiel comme un ordinateur classique. Les ordinateurs quantiques font appel à des techniques de calcul totalement différentes de celles habituellement connues. Ils se basent sur des propriétés quantiques de la matière. De nombreux systèmes (transistors des ordinateurs classiques, afficheurs LCD, imprimantes à laser...) exploitent certes des effets quantiques dans leur fonctionnement, mais représentent l’information sous forme de bits classiques. Un calculateur quantique utilise au contraire des qubits (bits quantiques) contenant plusieurs informations intriquées. Un algorithme dû à Peter Shor permet d’utiliser un calculateur quantique pour « casser » le code RSA. Cette découverte a stimulé la recherche sur le sujet.

Des moyens de chiffrement quantique existent également dans le commerce. Ils ne demandent pas de calculateur quantique, mais demandent une mise en place plus complexe qu’un cryptage standard.

Que des calculateurs quantiques de taille intéressante soient possibles ou non à terme, leur premier avenir commercial ne sera probablement pas dans le grand public : le calcul quantique exige peu d’entrées et peu de sorties. Il ne se prête donc a priori qu'aux calculs dont la complexité réside dans la combinatoire. On trouve ces problèmes dans l’ordonnancement et autres calculs de recherche opérationnelle, en bio-informatique, et bien entendu en cryptographie.

Algorithmes utilisant des circuits quantiques

Comme vu plus haut, c’est la combinatoire qui constitue le champ de travail privilégié des futures cartes de calcul quantique, si elles existent un jour.

Ainsi il peut être très difficile de trouver tous les facteurs premiers d’un grand nombre (par exemple de 1000 chiffres). Ce problème de factorisation est difficile pour un ordinateur ordinaire à cause de l’explosion combinatoire. Un circuit de calcul quantique pourrait résoudre ce problème en un temps polynomial, c’est-à-dire que pour l’ordinateur quantique, la difficulté augmenterait polynomialement au lieu d’augmenter exponentiellement.

Une analogie possible est de se représenter un calculateur quantique comme un processeur SIMD (carte graphique, par exemple) dont le nombre de pipelines serait 2^N fois le nombre N de qubits. L’analogie s’arrête là, un calculateur quantique ne pouvant fournir qu’un bit de résultat à la fois (l’état quantique étant détruit par l’observation), après quoi le calcul doit être recommencé pour demander le suivant.

Cette capacité permettrait à un ordinateur quantique de casser une bonne partie des systèmes cryptographiques actuellement utilisés, en particulier la plupart des méthodes de chiffrement asymétriques : RSA, ElGamal ou Diffie-Hellman. Ces algorithmes sont utilisés pour protéger des pages Web, des messages électroniques, et beaucoup d’autres types de données. Parvenir à passer ces protections serait un avantage majeur pour l’organisation ou le pays qui y parviendrait, et une réédition de l’exploit réalisé pour Enigma.

La seule façon de rendre sûr un algorithme tel que RSA est d’augmenter la taille de la clé en fonction de l'évolution des technologies qui permettent de casser des clés toujours de plus en plus longues, ralentissant en même temps le codage des messages sur les réseaux utilisateurs. Cette clé doit être plus grande que le plus grand des circuits de calcul quantique existants. Or la taille des moyens de calcul dont dispose par exemple la National Security Agency ne sera évidemment jamais rendue publique. La conséquence en est que les pays ou organismes voulant se protéger verront augmenter de plusieurs ordres de grandeur le coût et le délai de leurs communications, sans même jamais savoir si cela sert à quelque chose. Si le RSA peut donc être rendu sûr, c'est donc au prix d’une lourde réorganisation des communications, de leur coût, et de leur commodité.

Des circuits quantiques sont déjà utilisés pour des simulations de mécanique quantique. C’est la raison pour laquelle Richard Feynman les avait imaginés au départ. Ils sont également très utiles, car les calculs quantiques deviennent complexes dès qu’on sort de quelques cas triviaux.

Un autre algorithme, bien que de gain moins spectaculaire, a été découvert par la suite : la recherche quantique rapide dans une base de données (en anglais : quantum database search) par l’algorithme de Grover. Au lieu de parcourir tous les éléments d’une liste pour trouver celui qui répond le mieux à un critère (par exemple : recherche d’une personne dans l’annuaire pour trouver son numéro de téléphone), cet algorithme utilise des propriétés de superposition pour que la recherche se fasse de façon globale. Les résultats devraient être en , N étant le nombre de fiches (et O représentant la comparaison asymptotique), soit mieux qu’une base de données classique bien optimisée, sous réserve de disposer d’un registre quantique de taille suffisante pour les calculs. Curieusement, le procédé rappelle dans son principe celui des anciennes fiches à tringles permettant d’accéder directement aux informations recherchées.

Des circuits de calcul quantique apportent donc un plus aux ordinateurs classiques dans quatre types d’applications :

• la décomposition en produit de facteurs premiers ;
• le logarithme discret ;
• les simulations de physique quantique.
• la recherche dans une base de données