Je m'étouffe quand je lis ce genre de connerie[1] dans wikipedia :

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 d'un élément dans une grande liste (Algorithme de Grover)

Voici ma liste :

  1. Simulations de mécanique quantique
  2. Problèmes d'algèbre
    1. Décomposition en facteurs premiers et logarithme discret (Algorithme de Shor)
    2. Décomposition de groupes abéliens
    3. Recherche spatiale
    4. Résolution des équations de Pell
    5. Recherches d'idéaux
    6. Approximations de sommes de Gauss
    7. Décalage de symboles de Legendre
    8. Problème du sous-groupe caché
  3. Problèmes de recherche
    1. Sans structure (Algorithme de Grover)
    2. Collision
    3. Moyenne
    4. Graphes connexes
    5. Arbres couvrant minimal
    6. Chemin le plus court avec une source unique
    7. Flot en réseau
  4. Approximation de problèmes #P-complets
    1. Polynômes de Jones
    2. Polynômes HOMFLYPT
  5. Marches quantiques
    1. NAND Tree (Algorithme de Farhi)
      1. Évaluation de formules booléennes
    2. Recherche de triangles
    3. Recherche d'éléments distincts
    4. Vérification de multiplication de matrices
    5. Test de la commutativité d'un groupe

Et encore, je ne suis pas à jour.

Notes

[1] Cet article est un exemple du pire de wikipedia, il y a des erreurs ÉNORMES, il faudrait le réécrire en entier.