Les défis posés par la complexité pour les ordinateurs quantiques sont abordés dans cet article, uniquement accessible aux abonnés.
Bien que les théoriciens de la complexité aient tendance à ne pas s'intéresser à l'information quantique en raison de la surenchère autour de ce domaine, les avancées récentes et surprenantes dans les codes correcteurs d'erreur pourraient les convaincre de rejoindre les partisans de l'utilité de la complexité quantique.
Écrit par Charles Antoine, qui travaille comme chercheur au laboratoire de physique théorique de la matière condensée et enseigne à l'université Pierre et Marie Curie.
Il est fascinant de découvrir que certaines actions de notre vie quotidienne cachent un potentiel insoupçonné. Par exemple, lorsque vous vous creusez les méninges pour résoudre une grille de Sudoku ou pour optimiser le rangement de vos affaires dans votre valise, vous êtes en réalité confronté au problème complexe de « P versus NP ». Ce problème fait partie des sept défis mathématiques du millénaire pour lesquels l'institut américain Clay a offert une récompense d'un million de dollars à quiconque parviendra à le résoudre. Cependant, cette récompense n'est pas seulement financière, car le défi de « P versus NP » est l'un des dilemmes les plus profonds et les plus fructueux en mathématiques, notamment dans le domaine de l'informatique quantique.
Dans les années 1970, des informaticiens ont constaté que certains problèmes complexes semblaient ne pas pouvoir être résolus rapidement de manière algorithmique. Ils ont créé des catégories de problèmes basées sur le temps de calcul et l'espace mémoire nécessaires pour les résoudre. Deux catégories principales ont ainsi été définies : les problèmes « P » (polynomiaux) pouvant être résolus facilement (comme le tri alphabétique d'une liste de noms) et les problèmes « NP » (non polynomiaux), qui semblent plus complexes et pour lesquels il est plus facile de vérifier si une solution est correcte que de la trouver (comme l'assemblage d'un puzzle de un million de pièces).
Cette information est uniquement disponible pour les abonnés des niveaux Access et Premium.
Études économiques et tous les articles sur le patrimoine : l'abonnement Access est idéal pour vous !
Nos vidéos
Paris sportifs en ligne : qui sortent vraiment gagnants ?
Portugal, Espagne, Grèce : la reprise des pays du Sud de l'Europe
Les jeunes ont-ils réellement des difficultés avec le travail ?
Est-ce que la concurrence dans le secteur ferroviaire peut faire baisser les prix des billets de train ?
À la une
Après deux années de hausse, les constructeurs automobiles ralentissent sur les prix haut de gamme
Les autorisations de construire sont maintenant conditionnées par la disponibilité en eau
La vendetta ridicule qui bloque le champ pétrolier libyen de Repsol
Sciences & perspectives
Jeux Olympiques de Paris 2024 : quel est le record ultime dans l'épreuve du 100 mètres ?
Quand les diamants de laboratoire rivalisent avec les diamants naturels
La fausse viande : la fin ne justifie pas les moyens
Pratique
P
L'équipe
Tous les droits sont protégés – © Les Echos 2024
