Les ressources (temps, mémoire) nécessaires pour effectuer un calcul ou une simulation.Le coût computationnel désigne les ressources—telles que le temps, la mémoire et l'énergie—nécessaires pour effectuer un calcul ou une simulation. En physique et en informatique, c'est une mesure critique de faisabilité : un problème peut être théoriquement résoluble mais pratiquement impossible si le coût croît trop rapidement avec la taille. Ce concept est central pour comprendre pourquoi les ordinateurs quantiques sont nécessaires pour certaines tâches, car les simulations classiques de systèmes quantiques ont souvent un coût computationnel exponentiel.
L'étude formelle du coût computationnel a commencé dans les années 1960 avec les travaux d'informaticiens comme Juris Hartmanis et Richard Stearns, qui ont introduit les classes de complexité. L'idée d'utiliser le coût computationnel pour justifier les ordinateurs quantiques a été popularisée par Feynman au début des années 1980.
Le coût computationnel est souvent analysé à l'aide de la théorie de la complexité, qui classe les problèmes selon la façon dont les ressources requises évoluent avec la taille de l'entrée. Par exemple, un problème qui prend un temps polynomial (comme trier une liste) est considéré comme traitable, tandis qu'un problème qui prend un temps exponentiel (comme simuler classiquement un grand système quantique) devient intraitable même pour des tailles modérées. Les ordinateurs quantiques visent à réduire ce coût pour des problèmes spécifiques en exploitant la superposition et l'intrication.
L'analyse du coût computationnel guide la conception d'algorithmes et de matériel, de l'optimisation des simulations classiques en science des matériaux à la détermination des problèmes qui méritent d'être poursuivis sur des ordinateurs quantiques, comme la simulation de la dynamique moléculaire pour la découverte de médicaments.
Le célèbre « problème du voyageur de commerce »—trouver le plus court chemin à travers de nombreuses villes—a un coût computationnel qui croît de manière factorielle, ce qui signifie que même avec tous les ordinateurs du monde, il reste insoluble pour quelques centaines de villes seulement.
















