Au cours des dernières décennies, la vitesse et la fiabilité des ordinateurs ont spectaculairement augmenté. Les microprocesseurs actuels concentrent près d'un milliard de transistors sur quelques centimètres carrés de silicium. À l'avenir, les composants seront encore plus miniaturisés et leur taille approchera celle de simples molécules.
À cette échelle et au-dessous, les ordinateurs pourraient devenir très différents de ce que nous connaissons. En effet, leur fonctionnement sera régi par les lois de la physique quantique, qui expliquent le comportement des atomes et des particules subatomiques. Or exploiter pleinement les propriétés quantiques serait une avancée considérable : les ordinateurs quantiques pourraient effectuer certaines tâches importantes beaucoup plus vite que les ordinateurs classiques (voir Le calcul quantique peut-il tout faire ?, par S. Aaronson, page 112).
La plus connue de ces tâches est sans doute la décomposition d'un grand nombre entier en produit de deux nombres premiers. La multiplication de deux nombres premiers est une opération simple pour les ordinateurs, même si les nombres en question comportent plusieurs centaines de chiffres. Mais la factorisation, c'est-à-dire l'opération inverse, est tellement difficile que la plupart des algorithmes de cryptage en usage à l'heure actuelle y ont recours, depuis le commerce sur Internet jusqu'à la transmission de secrets d'État.
En 1994, Peter Shor, alors aux Laboratoires AT&T, aux États-Unis, a montré qu'un ordinateur quantique pourrait en théorie casser ces codes de cryptage facilement, parce qu'il serait capable de factoriser les entiers beaucoup plus vite que tout algorithme classique connu. Et en 1997, Lov Grover, également aux Laboratoires...
