Calcul Quantique: un tutoriel 

 

Samuel L. Braunstein

Abstrait:

Imaginez un ordinateur dont la mémoire est exponentiellement plus grande que sa taille physique apparente; un ordinateur qui peut manipuler un ensemble exponentiel d’entrées simultanément; un ordinateur qui calcule dans la zone crépusculaire de l’espace de Hilbert. Vous penseriez à un ordinateur quantique. Relativement peu de concepts simples de la mécanique quantique sont nécessaires pour faire des ordinateurs quantiques une possibilité. La subtilité a été d’apprendre à manipuler ces concepts. Un tel ordinateur est-il inévitable ou sera-t-il trop difficile à construire?

Dans cet article, nous donnons un tutoriel sur la façon dont la mécanique quantique peut être utilisée pour améliorer le calcul. Notre défi: résoudre un problème exponentiellement difficile pour un ordinateur conventionnel — celui de factoriser un grand nombre. En prélude, nous passons en revue les outils standards de calcul, les portes universelles et les machines. Ces idées sont ensuite appliquées d’abord aux ordinateurs classiques, sans dissipation, puis aux ordinateurs quantiques. Un modèle schématique d’un ordinateur quantique est décrit ainsi que certaines des subtilités de sa programmation. L’algorithme de Shor [ 1 , 2] pour factoriser efficacement les nombres sur un ordinateur quantique est présenté en deux parties: la procédure quantique au sein de l’algorithme et l’algorithme classique qui appelle la procédure quantique. La structure mathématique dans l’affacturage qui rend possible l’algorithme de Shor est discutée. Nous concluons avec une perspective sur la faisabilité et les perspectives du calcul quantique dans les années à venir.

Commençons par décrire le problème actuel: factoriser un nombre N en ses facteurs premiers (par exemple, le nombre 51688 peut être décomposé comme ). Un moyen pratique de quantifier la rapidité avec laquelle un algorithme particulier peut résoudre un problème consiste à se demander comment le nombre d’étapes pour compléter l’algorithme varie avec la taille de l’entrée utilisée par l’algorithme. Pour le problème d’affacturage, cette entrée est juste le nombre N que nous voulons factoriser; d’où la longueur de l’entrée est . (La base du logarithme est déterminée par notre système de numérotation, donc une base de 2 donne la longueur en binaire, une base de 10en décimal.) Les algorithmes `Reasonable ‘sont ceux qui sont mis à l’échelle comme un polynôme de petit degré dans la taille d’entrée (avec un degré de 2 ou 3 peut-être ).

Sur les ordinateurs conventionnels, l’algorithme d’affacturage le plus connu fonctionne par étapes [ 3 ]. Cet algorithme, par conséquent, évolue exponentiellement avec la taille d’entrée . Par exemple, en 1994, un nombre de 129 chiffres (connu sous le nom de RSA129 [ 3 ‘ ]) a été factorisé avec succès en utilisant cet algorithme sur environ 1600 postes de travail dispersés dans le monde entier; toute la factorisation a pris huit mois [ 4 ]. En utilisant ceci pour estimer le préfacteur de la mise à l’échelle exponentielle ci-dessus, nous trouvons qu’il faudrait environ 800 000 ans pour factoriser un nombre de 250 chiffres avec la même puissance d’ordinateur; de même, un nombre de 1000 chiffres nécessiteraitannées (significativement plus long que l’âge de l’univers). La difficulté à factoriser de grands nombres est cruciale pour les systèmes cryptographiques à clé publique, tels que ceux utilisés par les banques. Là, de tels codes reposent sur la difficulté de factoriser des nombres avec environ 250 chiffres.

Récemment, un algorithme a été développé pour factoriser des nombres sur un ordinateur quantique qui court par étapes où est petit [ 1 ]. Ceci est à peu près quadratique dans la taille d’entrée, donc factoriser un nombre de 1000 chiffres avec un tel algorithme ne nécessiterait que quelques millions d’étapes. L’implication est que les systèmes de chiffrement à clé publique basés sur l’affacturage peuvent être cassables.

Pour vous donner une idée de la façon dont cette amélioration exponentielle pourrait être possible, nous passons en revue une expérience de mécanique quantique élémentaire qui démontre où un tel pouvoir peut être caché [ 5].] L’expérience à deux fentes est prototypique pour observer le comportement de la mécanique quantique: Une source émet des photons, des électrons ou d’autres particules qui arrivent à une paire de fentes. Ces particules subissent une évolution unitaire et finalement une mesure. Nous voyons un modèle d’interférence, avec les deux fentes ouvertes, qui disparaît complètement si l’une des fentes est couverte. Dans un certain sens, les particules traversent les deux fentes en parallèle. Si une telle évolution unitaire représentait un calcul (ou une opération dans un calcul), alors le système quantique effectuerait des calculs en parallèle. Le parallélisme quantique est gratuit. La sortie de ce système serait donnée par l’interférence constructive entre les calculs parallèles.


 

 

Sourcehttp://www-users.cs.york.ac.uk/~schmuel/comp/comp.html

Leave a Reply

Your email address will not be published. Required fields are marked *