Un ordinateur quantique opère ses calculs grâce à la superposition quantique d'états quantiques. De petits ordinateurs quantiques ont déjà été récemment construits et des progrès sont en cours. Beaucoup de gouvernements et d'organisations militaires telles que l'OTAN sponsorisent des universités et des centres de recherches pour développer un tel ordinateur à des fins cryptographiques et de surveillance, pouvant servir par exemple au renseignement militaire.

Il est largement suspecté que si de grands ordinateurs quantiques pouvaient être construits, ils seraient capables de résoudre certains problèmes plus vite qu'aucun ordinateur classique. Les ordinateurs quantiques sont différents de ceux-ci, même si ces derniers utilisent des effets quantiques autre que la superposition d'états.

Structure des ordinateurs quantiques

En mécanique quantique, il est possible pour une particule d'être en deux endroits à la fois, ou en deux états à la fois. C'est comme le chat de Schrödinger : il est à la fois mort et vivant en même temps. Cette possibilité d'être dans de multiples états simultanément est appelée superposition.

La mémoire d'un ordinateur classique est faite de bits. Chaque bit porte soit un un ou un zéro. La machine calcule en manipulant ces bits. Un ordinateur quantique maintient lui un jeu de qubits. Un qubit peut porter soit un un, soit un zero, soit une superposition d'un un et d'un zéro. L'ordinateur quantique calcule en manipulant ces qubits.

Un ordinateur quantique peut être implementé en utilisant n'importe quelle petite particule qui peut avoir deux états. Des ordinateurs quantiques peuvent être construits à partir d'atomes qui sont à la fois excités et non excités au même moment. Ils peuvent être construits à partir de photons de lumière qui sont à deux endroits au même moment. Ils peuvent être construits à partir de protons et de neutrons ayant un spin soit positif soit négatif ou les deux en même temps.

Une molécule microscopique peut contenir plusieurs millions de protons et de neutrons. Elles peuvent être utilisées comme ordinateurs quantiques avec plusieurs millions de qubits.

Puissance des ordinateurs quantiques

Il peut être très difficile de prendre un grand nombre et de trouver tous ses facteurs premiers. Ce problème de factorisation passe pour difficile pour un ordinateur ordinaire. Un ordinateur quantique pourrait résoudre ce problème très rapidement. Si un nombre a n bits (s'il est long de n digits quand écrit en binaire), alors un ordinateur quantique avec juste plus de 2n qubits peut trouver ses facteurs. Il peut aussi résoudre un problème lié, celui du logarithme discret. Cette capacité permettrait à un ordinateur quantique de casser beaucoup des systèmes cryptographiques en place aujourd'hui. Beaucoup des populaires chiffrements asymétriques pourraient être rapidement cassés, incluant RSA, ElGamal et Diffie-Hellman. Ils sont utilisés pour protéger des pages Web, des messages électroniques, et beaucoup d'autres types de données. Les casser aurait une importance. La seule façon alors de rendre un algorithme tel que RSA sûr serait d'augmenter la taille de la clé jusqu'à ce qu'elle soit plus grande que le plus grand des ordinateurs quantiques jamais construits. Il semble probable qu'il sera toujours possible de créer des ordinateurs classiques ayant plus de bits que le plus grand des ordinateurs quantiques. Si cela se révèle exact, RSA pourra être rendu sûr.

Si un ordinateur quantique était basé sur les protons et neutrons d'une molécule, il serait trop petit à voir, mais pourrait factoriser des entiers ayant plusieurs miliers de bits. Un ordinateur classique utilisant les algorithmes connus pourrait aussi les factoriser. Mais pour le faire avant que le soleil s'éteigne, il aurait à être plus grand que l'univers connu. Ce serait quelque peu problématique pour sa construction.

De façon probablement pas si surprenante, les ordinateurs quantiques pourraient être utilisés pour des simulations de mécanique quantique. L'accélération pourrait être aussi grande qu'avec la factorisation. Ce serait d'un grand bénéfice pratique pour beaucoup de physiciens.

L'ordinateur quantique est donc reconnu pour avoir un gros avantage dans trois problèmes: la factorisation en nombres premiers, le logarithme discret et les simulations de physique quantique. Cependant, il n'y a pas de preuves que l'avantage est réel : un algorithme classique tout aussi rapide pourrait être découvert, bien que cela semble improbable. Il y a aussi un autre problème où les ordinateurs quantiques ont un avantage, bien que plus plus petit (quadratique). C'est la recherche quantique dans une base de données (en anglais: quantum database search). et peut être résolu par l'algorithme de Grover. Dans ce cas l'avantage est prouvable. Cela établit au-delà du doute que l'ordinateur quantique idéal est supérieur aux ordinateurs classiques.

Supposons qu'il y ait un problème, tel que trouver le mot de passe pour déchiffrer un fichier. Ce problème a quatre propriétés :

• La seule façon de le résoudre est de générer des réponses et de les vérifier.
• Il n'y a que n responses possibles à vérifier.
• Chaque réponse possible prend le même temps à vérifier.
• Il n'y a pas d'indices au sujet de la meilleure réponse. Générer les réponses aléatoirement est aussi bon que les essayer dans un certain ordre.

Il n'y a actuellement pas d'autres problèmes connus pour être bien plus facilement solvables par un ordinateur quantique. La recherche continue, et d'autres pourraient être trouvés.

Comment ils fonctionnent

Il y aurait eu n qubits, cette table aurait eu 2ⁿ lignes. Pour un n aux alentours de 100, il y aurait eu plus de lignes que d'atomes dans l'univers.

La première colonne montre tous les états possibles pour trois bits. Un ordinateur classique peut seulement porter un de ces états à la fois. un ordinateur quantique, lui, peut être dans une superposition de ces 8 états à la fois. La deuxième colonne montre l'amplitude pour chacun des 8 états. Ces 8 nombres complexes sont un instantané du contenu d'un ordinateur quantique à un moment donné. Durant le calcul, ces trois nombres changeront et interagiront les uns avec les autres. En ce sens, un ordinateur quantique à trois qubits a bien plus de mémoire qu'un ordinateur classique à trois bits.

Cependant, il n'est pas possible de voir directement ces trois nombres. Quand l'algorithme est fini, une seule mesure est accomplie. La mesure retourne une simple chaîne (string) de 3 bits et efface les 8 nombres quantiques. La chaîne de retour est générée aléatoirement. La troisième colonne donne la probabilité pour chacune des chaînes possibles. Dans cet exemple, il y a 14% de chance que la chaîne retournée soit "000", 4% que ce soit "001", ainsi de suite. Chaque nombre complexe est nommé "amplitude" et chaque probabilité une "amplitude carrée", parce qu'elle est égale à |a+bi|². La somme des huit probabilités est égale à un.