concept

coût de calcul

Les ressources (temps, mémoire) nécessaires pour effectuer un calcul ou une simulation.
46 articles liés

Description

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.

Histoire

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.

Comment ça marche

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.

En pratique

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.

Anecdote

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.

Concept graph →

Articles liés · 46

Physique quantique2026-08-092 minarXiv:2608.10027express
Ordinateurs thermiques : le prix de la précision
Un ordinateur classique calcule en faisant circuler des charges électriques dans des fils. Mais peut-on calculer avec la chaleur ? Un réseau de tubes parcourus par de l'eau chaude et froide peut effectuer des opérations logiques simples si l'on connecte les tubes dans le bon ordre.
Physique quantique2026-08-032 minarXiv:2608.02773express
Un code quantique qui ne craint pas les erreurs
Un ordinateur quantique ressemble à un orchestre où chaque musicien-qubit se dérègle facilement. Le moindre bruit, et la mélodie du calcul se transforme en cacophonie. Pour que l'orchestre joue en harmonie, il faut un chef qui repère instantanément les fausses notes et les corrige sans interrompre l'exécution. C'est exactement le rôle des codes de correction d'erreurs.
Univers sans horloge : le temps venu de la géométrie
L'horloge dans l'Univers est une affaire délicate. Habituellement, dans les calculs de la naissance du monde, le rôle d'horloge est joué par un champ scalaire particulier — une sorte de fluide invisible remplissant tout l'espace. Il tictaque, et les physiciens observent comment le monde évolue par rapport à ce tictac. Mais ces horloges sont artificielles, introduites pour plus de commodité.
Pourquoi l'intelligence artificielle répète les mêmes erreurs
Les catastrophes technologiques, comme Tchernobyl, surviennent rarement de façon soudaine. Elles couvent pendant des années : les organisations ignorent les avertissements, car leur complexité évoque la croissance de l'entropie — cette mesure du chaos inexorable qui s'accumule en silence jusqu'à ce qu'il s'abatte comme une avalanche.
Physique quantique2026-07-072 minarXiv:2607.06404express
Le code quantique à l'identique
Un ordinateur quantique ressemble à un orchestre sans chef : chaque qubit est un musicien, et la moindre fausse note fait dérailler toute la symphonie. Pour éviter que la musique ne se transforme en cacophonie, on a inventé des codes quantiques qui corrigent les erreurs.
Trier l'or : optimiser les pipelines d'IA avec les méthodes des bases de données
L'or ne se trouve pas en surface — il est caché dans des tonnes de stérile. Pour extraire un gramme de métal précieux, les chercheurs d'or tamisent des mètres cubes de terre.
Physique quantique2026-06-192 minarXiv:2606.21664express
Les jeux quantiques percent le secret d'un vieux théorème mathématique
En 1953, le mathématicien Alexandre Grothendieck a démontré un théorème qui est devenu une pierre angulaire de la théorie des produits tensoriels. Il affirme que pour les espaces de fonctions ordinaires, deux normes naturelles — la projective et l'injective — sont équivalentes à une constante universelle près.
L'eau mouillée et le processeur pensant
Dans les années 1990, le philosophe John Searle a imaginé une expérience de pensée : une personne est assise dans une pièce et, sans connaître le chinois, suit des instructions pour fournir des réponses correctes en chinois. De l'extérieur, on dirait qu'elle comprend la langue, mais à l'intérieur, ce n'est qu'un suivi mécanique de règles.
Comment les neutrinos s'intriquent dans les entrailles des étoiles
Dans le cœur incandescent d'une étoile mourante naît un flux invisible : le gaz de neutrinos. Les particules filent à travers la matière presque sans s'arrêter, mais lorsque leur densité est énorme, elles commencent à se sentir mutuellement. Les anciens calculs décrivaient cela comme une bousculade dans une foule : chaque choc change la direction, mais aucun lien ne s'établit entre les passants.
Comment les aimants changent la nature d'une transition quantique
Une longue chaîne d'atomes, et chacun est un minuscule aimant. Ils se parlent entre eux et avec le champ commun, comme des musiciens dans un orchestre qui entendent à la fois le chef et leurs voisins. Lorsque le champ externe change, l'orchestre joue soit en désordre, soit tous les instruments entrent en synchronie — c'est cela, une transition de phase quantique.
Physique quantique2026-05-241 minarXiv:2605.25302express
Causalité : pourquoi on ne peut pas la mesurer
Le monde quantique joue à un jeu étrange avec la causalité. Si dans la vie ordinaire, on sale toujours la soupe avant de la servir, ici les ingrédients se retrouvent dans l'assiette en même temps, et le cuisinier ne se souvient plus de l'ordre. Les physiciens se sont demandé : peut-on mesurer cette « recette » ? La réponse est non.
Physique quantique2026-05-082 minarXiv:2605.08351express
Des événements quantiques sans scénario prédéfini
En cuisine, l'ordre des opérations est strictement dicté par la recette : d'abord couper, puis faire revenir, et pas autrement. En physique quantique, le rôle de la recette est joué par la causalité – un événement est la cause d'un autre, et on ne peut pas les intervertir.
Un assistant IA s'attaque aux calculs les plus ardus de la cosmologie
L'expansion de l'univers s'accélère, et il se pourrait que la gravité ne fonctionne pas comme nous le croyons. Les physiciens élaborent des théories alternatives, mais pour les vérifier, il faut calculer comment les ondulations primordiales après le Big Bang ont donné naissance aux galaxies.
Physique quantique2026-04-292 minarXiv:2604.26813express
La magie que les électrons ont volée
L'ordinateur quantique promet de résoudre des problèmes qu'un ordinateur ordinaire ne peut pas résoudre. Mais où se situe la frontière ? Les auteurs de ces travaux sont tombés sur un cas surprenant : des électrons appariés se comportent comme un orchestre discipliné.
Les parois magnétiques, clé des ordinateurs quantiques
Une rangée de dominos : quand le premier tombe, poussant son voisin, une onde parcourt la chaîne. La frontière entre les dominos tombés et ceux encore debout est une image fidèle d'une paroi magnétique. Dans les films magnétiques microscopiques, ces parois séparent des zones d'aimantation différente.
Physique quantique2026-04-081 minarXiv:2604.07639express
Physique quantique2026-04-071 minarXiv:2604.06322express
Les ordinateurs quantiques vont défier la gravité
La grande énigme de la physique est de concilier la courbure de l'espace-temps avec la mécanique quantique. À la longueur de Planck, des milliards de milliards de fois plus petite qu'un atome, les lois cessent de fonctionner. Cette frontière a été ouverte par Max Planck.
Physique quantique2026-03-301 minarXiv:2603.28627express
Le boulier quantique : une faille à 10 000 atomes
Au lieu de millions de particules figées, 10 000 atomes qui fonctionnent comme les boules d'un boulier quantique. Chaque boule peut être à la fois un zéro et un un. Mais surtout, si une erreur se glisse dans le calcul, on peut physiquement déplacer les atomes : comme si on réassemblait le boulier en marche pour que le bug ne gâche pas le résultat.
Physique quantique2026-03-262 minarXiv:2603.25519express
Le minage quantique du bitcoin : pourquoi l'énergie stellaire ne suffira pas
Le minage de bitcoins ressemble à une loterie : les mineurs épluchent des milliards de nombres pour en trouver un qui soit gagnant. Un ordinateur classique le fait à l'aveugle, en dépensant de l'électricité.
Physique quantique2026-02-251 minarXiv:2602.22211express
Physique chimique2026-02-212 minarXiv:2602.18821express
La cuisine quantique de l'eau
Une casserole d'eau sur la cuisinière, c'est juste de l'eau, mais à l'intérieur de chaque molécule, une danse incessante se joue. Les atomes d'hydrogène et d'oxygène frémissent, même au zéro absolu, car tel est le monde quantique. Ces frémissements modifient la quantité de chaleur que l'eau emmagasine et la façon dont elle s'écoule.
La complexité à la frontière de l'ordre et du chaos
Un film magnétique, découpé en minuscules cellules-flèches, se comporte comme une foule sur une place. Tant qu'il fait froid, toutes les flèches pointent dans la même direction — un ordre parfait. Chauffez le film, et les flèches se mettent à s'agiter, comme des passants qui ont perdu leur but.
Physique quantique2026-02-062 minarXiv:2602.06544express
Complexité sur les graphes : comment les marches quantiques accélèrent le temps
Une marche quantique ressemble à un homme ivre qui tourne au hasard à chaque intersection. Mais au lieu de rues, il y a des nœuds de graphe, et au lieu de pas, des transitions quantiques. Les scientifiques ont découvert que cette marche possède une mesure cachée : la complexité de Krylov.
Physique quantique2026-01-281 minarXiv:2601.20818express
Les ordinateurs quantiques apprennent à se réparer tout seuls
Les ordinateurs quantiques ont désormais un mécanisme d'auto-réparation intégré. Le nouveau schéma bidimensionnel fonctionne comme un tissu vivant : chaque cellule-qubit interagit avec ses voisines selon des règles locales, supprimant automatiquement le désordre aléatoire — l'entropie.
Physique quantique2026-01-242 minarXiv:2601.17580express
Les erreurs d'un ordinateur quantique apprennent à se corriger elles-mêmes
Un ordinateur quantique, c'est comme un orchestre où chaque musicien joue sa partition, mais parfois se trompe. Pour éviter que la musique ne devienne une cacophonie, il faut un chef qui corrige les erreurs à temps. Dans le calcul quantique, le rôle du chef est tenu par des codes correcteurs d'erreurs.
Physique quantique2026-01-121 minarXiv:2601.08068express
L'ordinateur quantique économise non seulement du temps, mais aussi de l'énergie
Pour faire du pop-corn, le micro-ondes ne dépense de l'électricité que pour chauffer les grains. La cuisinière à gaz, elle, chauffe tout le brûleur et l'air autour. C'est la même différence entre une puce quantique à photons et un superordinateur classique lorsqu'ils résolvent un problème imaginé par Scott Aaronson.
Optique2026-01-042 minarXiv:2601.01399express
La lumière compte en quatre dimensions
Un ordinateur ordinaire voit le monde de manière plate : pour lui, les nombres ne sont que des points sur une ligne. Mais une image en couleur ou une scène tridimensionnelle exige davantage — quatre nombres qui décrivent à la fois la position et la rotation.
Physique quantique2025-12-172 minarXiv:2512.15001express
Physique quantique2025-12-161 minarXiv:2512.14842express
Le bruit aide les ordinateurs quantiques
Pour dissoudre rapidement du sucre, pas besoin de remuer délicatement — il suffit de secouer le verre. Un principe similaire s'applique aux systèmes quantiques : le bruit, généralement considéré comme une nuisance, accélère la transition vers l'état thermique.
Physique quantique2025-12-151 minarXiv:2512.13908express
La magie sur une puce : cultiver des états quantiques
Les ordinateurs quantiques ont besoin d'états magiques — des particules auxiliaires spéciales pour fonctionner sans erreur. Autrefois, on les obtenait par purification répétée, semblable à une distillation sans fin : chaque étape ajoutait de l'entropie (du désordre), comme des mauvaises herbes dans un jardin, et dévorait les ressources.
Physique quantique2025-10-301 minarXiv:2510.26547express
Saut quantique : un jour au lieu de 22 ans
Transformer le CO₂ en carburant, c'est un peu comme trouver la seule bonne façon de ranger des milliards d'objets dans une valise. Un ordinateur classique essaie les combinaisons une par une, y passant des décennies, tandis qu'un ordinateur quantique semble voir toutes les possibilités d'un coup.
Physique quantique2025-10-291 minarXiv:2510.25838express
Une puce quantique bat des supercalculateurs : deux heures contre des années
La tâche évoque un labyrinthe géant avec une seule sortie parmi des milliards d'impasse. Un ordinateur classique vérifie chaque couloir pas à pas — il faudrait des siècles. Le processeur quantique lance une onde qui se propage simultanément dans toutes les directions. Le bon chemin répond en écho, s'amplifie, et la réponse arrive en quelques heures.
L'escaladeur quantique : des sauts par-dessus les gorges de l'optimisation
Trois mille mètres au-dessus du niveau de la mer, une paroi verticale. L'escaladeur classique grimpe par une seule voie, pas à pas, et se retrouve souvent coincé dans un minimum local, une petite niche d'où il n'y a pas de passage vers le haut.
Les neuf vies d'un photon : comment « Jiuzhang 4.0 » a survécu aux pertes et laissé la classique derrière lui
Une impulsion laser d'une durée d'une nanoseconde et demie frappe un cristal non linéaire, et naît un flux de lumière comprimée. C'est ainsi que commence l'expérience sur le processeur quantique « Jiuzhang 4.0 » en Chine.
Architecture vélo : un ordinateur quantique modulaire
L'ordinateur quantique, c'est comme un orchestre où chaque musicien joue sa partition, mais la moindre fausse note ruine la symphonie. Les qubits physiques qui le composent sont bruyants et commettent des erreurs. Pour protéger les calculs, on les regroupe en qubits logiques grâce à la correction d'erreurs quantique.
Portes non hermitiennes : le prix d'une accélération imaginaire
En 2019, un groupe de théoriciens s'est posé une question simple : que se passerait-il si l'on intégrait dans un ordinateur quantique ordinaire un unique élément irréversible, une porte qui « mange » un peu de probabilité ? La réponse s'est avérée dévastatrice.
Mémoire en optomécanique : un chef d'orchestre laser apprend à la lumière et au son à se souvenir
Dans une pièce sombre, un résonateur capture la lumière comme une toile d'araignée capture des gouttes de rosée. L'impulsion laser s'engouffre à l'intérieur, et la membrane mécanique se met à vibrer en rythme, laissant une trace dans la trame même du système.
Un tamis quantique pour le réseau électrique
Chaque jour, le réseau électrique doit résoudre un casse-tête : quelles centrales démarrer pour couvrir la demande de manière fiable sans se ruiner. Pour 15 générateurs et 24 heures, le nombre de plannings possibles dépasse 2,3×$$10^{108}$$, soit plus que le nombre d'atomes dans l'Univers visible.