Les ordinateurs quantiques sont confrontés à la difficulté de gérer la complexité. Cette information est uniquement accessible aux abonnés.
Bien que les théoriciens de la complexité ne soient pas très intéressés par le domaine de l'information quantique en raison de la hype entourant la question, les avancées récentes et surprenantes dans les codes correcteurs d'erreurs pourraient les convaincre de rejoindre ceux qui voient l'utilité de la complexité quantique de manière pragmatique et optimiste.
Écrit par Charles Antoine, un chercheur et professeur à l'université Pierre et Marie Curie, travaillant au Laboratoire de Physique Théorique de la Matière Condensée.
Il est possible que vous ne le sachiez pas, mais il y a une grande valeur cachée dans certaines actions de votre vie quotidienne. Par exemple, lorsque vous vous creusez la tête pour résoudre une grille de Sudoku ou pour organiser vos affaires dans votre valise. Sans le savoir, vous êtes en train d'aborder le problème complexe de « P versus NP », l'un des sept problèmes mathématiques les plus importants pour lesquels l'institut américain Clay a offert un million de dollars à quiconque trouvera la solution. Ce prix n'est pas seulement financier, car le problème « P versus NP » est l'un des plus profonds et féconds en mathématiques, avec un lien étroit avec l'informatique quantique.
Dans les années 1970, des informaticiens ont posé le problème de savoir si certains problèmes complexes pouvaient être résolus rapidement de manière algorithmique. Ils ont créé des catégories appelées « classes de complexité » pour classer les problèmes en fonction du temps de calcul et de l'espace mémoire nécessaires. Deux catégories principales ont été identifiées : la catégorie des problèmes « P » (« polynomiaux ») qui peuvent être résolus facilement (comme le tri alphabétique) et la catégorie des problèmes « NP » (« non polynomiaux ») qui sont plus complexes et pour lesquels on ne peut que vérifier si une solution est correcte en un temps raisonnable (comme l'assemblage d'un puzzle complexe).
Cet article est exclusivement disponible pour les abonnés des offres Access et Premium.
Études économiques et tous les articles sur le patrimoine : l'abonnement Access est parfait pour vous !
Nos vidéos
Paris sportifs en ligne : qui remporte vraiment la mise ?
Portugal, Espagne, Grèce : la revanche des pays du sud de l'Europe
Les jeunes rencontrent-ils des difficultés avec le travail ?
La concurrence peut-elle faire baisser les tarifs des billets de train de la SNCF ?
En vedette
Après une période de croissance, les constructeurs automobiles ralentissent sur les prix haut de gamme
Les autorisations de construction sont maintenant liées à la disponibilité en eau
Les conflits qui paralysent le champ pétrolier libyen de Repsol
Sciences & Avenir
Quel est le record ultime dans l'épreuve du 100 mètres aux JO de Paris 2024 ?
Le défi du diamant de laboratoire face au diamant naturel
La fausse viande : justifiable en cas de faim ?
Pratique
P
L'ensemble des individus
Tous les droits sont protégés – propriété de Les Echos 2024
