Les ordinateurs quantiques
Algorithmes quantiques

Voilà ce qu'on sait :

• On peut réaliser des qubits -on a vu la polarisation du photon, mais on se demande bien comment ça marche vraiment pour d'autres systèmes physiques.
• Il faudra, par un moyen à définir, faire communiquer ces qubits entre eux pour que la puissance de calcul puisse être mise en œuvre.
• Des gens ont défini des portes, un peu comme dans les ordinateurs classiques, mais on a vite vu que c'était quelque chose de très différent : on multiplie des matrices, on ne peut pas voir ce qui se passe à l'intérieur, on peut uniquement faire une mesure qui ne donne qu'un résultat probabiliste : il faudra recommencer la même mesure pas mal de fois pour faire des statistiques, mais bon, ce n'est qu'une question de temps, rien de bloquant.
• Donc on peut multiplier des matrices qui peuvent être vite gigantesques, on sent que la force de ces ordinateurs quantiques traine par là. Sauf que :
  • C'est bien joli, mais il faudra bien rentrer les données à un moment ou à un autre ! Si on peut les calculer, passe encore, mais s'il faut entrer une encyclopédie, ça risque d'être extrêmement fastidieux, surtout qu'on sait qu'actuellement, les temps de cohérence sont faibles : c'est mal barré.
  • n qubits, c'est 2ⁿ nombres complexes à entrer, puisqu'il existe 2ⁿ états possibles (pour 2 qubits, on a quatre états de base et un nombre complexe devant chaque terme, pour 3 qubit, c'est huit…)

Certes, on peut multiplier des matrices, mais ça ne nous donne pas encore un algorithme. On a l'habitude d'avoir des tests conditionnels dans le classique, et là, c'est loin d'être évident. Ceci dit, il parait qu'un ordinateur quantique peut reproduire la logique d'un ordinateur classique, ce serait prouvé (avec des machines de Turing), donc restons optimiste.

On va commencer par voir de quoi il retourne côté algorithme, afin de mieux sentir "comment ça pourrait marcher". On verra dans un autre chapitre comment on programme effectivement une porte de Hadamard ou une porte CNOT sur un vrai qubit -après avoir vu ce qu'on pourrait utiliser comme qubit physique.

Des algorithmes, il en existe surtout deux de connus : Grover qui permet de trier, et Shor qui permet de factoriser (le plus dangereux pour la cybersécurité).

On trouvera une liste de beaucoup d'algorithmes connus en 2018 dans le papier Quantum Algorithms for Wireless Communications https://ieeexplore.ieee.org/document/8540839 (un tutoriel en fait).