Classification des problèmes à résoudre et complexité

1. L’informatique classique face à l’informatique quantique

a. Complexité des problèmes à résoudre Complexité:des problèmes

Pour le moment, nous avons vu comment fonctionne l’informatique quantique et comment réaliser des premiers algorithmes quantiques utilisant des portes quantiques. Toutefois, on perçoit encore mal l’intérêt de l’informatique quantique. En effet, son intérêt se place forcément dans l’idée que l’informatique quantique serait parfois plus performante que l’informatique classique sur certains problèmes.

Nous détaillerons donc une manière de classer des problèmes, notamment de recherche opérationnelle, selon leurs complexités. Certaines classes de problèmes sont aujourd’hui impossibles à résoudre avec l’informatique classique. Trouver ou approcher une solution de certaines instances de ces problèmes supposerait de laisser tourner des algorithmes classiques pendant des centaines d’années. L’informatique quantique constitue donc un espoir (théorique) d’atteindre des solutions exactes ou approchées sur des instances de problèmes qui échappent à nos capacités actuelles. Recherche opérationnelle

b. Parallélisation quantique ou la puissance du registre quantique

Nous avons...

Pour consulter la suite, découvrez le livre suivant :
couv_DPQINF.png
60-signet.svg
En version papier
20-ecran_lettre.svg
En version numérique
41-logo_abonnement.svg
En illimité avec l'abonnement ENI
130-boutique.svg
Sur la boutique officielle ENI
Précédent
Téléportation quantique
Suivant
Typologie des problèmes