concept

complexité

La mesure des ressources de calcul requises, qui double à chaque qubit ajouté dans une simulation.
75 articles liés

Description

La complexité, dans le contexte de l'informatique quantique, désigne la croissance exponentielle des ressources de calcul nécessaires pour simuler un système quantique sur un ordinateur classique. À chaque qubit ajouté, l'espace des états double, de sorte qu'un système de n qubits nécessite 2^n amplitudes complexes pour être décrit complètement. Cette mise à l'échelle exponentielle est la raison fondamentale pour laquelle les ordinateurs quantiques sont si difficiles à simuler classiquement — même quelques centaines de qubits dépassent la mémoire de toute machine classique imaginable. Cette complexité est à la fois un défi et une opportunité : elle rend les systèmes quantiques difficiles à comprendre, mais elle sous-tend également le potentiel des ordinateurs quantiques à résoudre des problèmes insolubles pour les ordinateurs classiques.

Histoire

La complexité exponentielle de la simulation quantique a été formulée pour la première fois par Richard Feynman en 1982, qui a proposé les ordinateurs quantiques comme un moyen de simuler efficacement les systèmes quantiques. Le cadre théorique formel de la complexité a été développé par David Deutsch et d'autres dans les années 1980-1990.

Comment ça marche

La complexité provient de l'intrication quantique et de la superposition. Une simulation classique doit suivre les amplitudes de probabilité de tous les états possibles, qui croissent comme 2^n. Pour n=50, cela représente environ 10^15 amplitudes, déjà au-delà de la mémoire classique pratique. Les ordinateurs quantiques exploitent cette complexité en manipulant directement ces amplitudes via des portes quantiques, effectuant des opérations qui nécessiteraient un nombre exponentiel d'étapes classiques. La complexité se manifeste également dans la difficulté de la correction d'erreurs, car les états quantiques sont fragiles et nécessitent une redondance pour se protéger contre la décohérence.

En pratique

Cette complexité est à la base de l'avantage quantique dans la simulation de molécules, de matériaux et d'autres systèmes quantiques, avec des applications dans la découverte de médicaments, la cryptographie et l'optimisation.

Anecdote

Un ordinateur quantique avec seulement 300 qubits nécessiterait plus de bits classiques pour être simulé qu'il n'y a d'atomes dans l'univers observable.

Concept graph →

Articles liés · 75

Physique quantique2026-08-161 minarXiv:2608.15795express
Un système quantique complexe se révèle à travers de petites parties
Les systèmes quantiques composés de nombreuses particules sont à la base des futurs ordinateurs et des réseaux sécurisés. Mais plus il y a de particules, plus il est difficile de comprendre comment elles sont organisées : le nombre d'états possibles augmente de façon exponentielle. La méthode habituelle, qui consiste à tout mesurer, prend un temps considérable.
Physique quantique2026-08-111 minarXiv:2608.10663express
Pont quantique entre les nœuds
Un réseau aléatoire classique ressemble à une carte routière : pour que quatre villes soient reliées par un carrefour complexe, il faut tracer de nombreuses autoroutes. Dans le monde des particules quantiques, tout est différent.
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.
Physique quantique2026-07-312 minarXiv:2607.29582express
Urgences quantiques pour les réseaux électriques
Un réseau électrique bourré d'électronique de puissance ressemble à un immense orchestre sans chef. Chaque convertisseur, chaque ligne apporte sa note, et parfois les instruments se mettent à jouer faux.
Physique quantique2026-07-261 minarXiv:2607.23773express
Comment distinguer l'écheveau du fil
Le monde quantique est plein d'étranges connexions. Deux particules peuvent se retrouver « intriquées » : l'état de l'une influence instantanément l'autre, même si des kilomètres les séparent. Mais comment savoir si elles sont réellement intriquées ?
La complexité bascule à mi-chemin
L'eau se transforme en glace à zéro degré — brusquement, sans états intermédiaires. Quelque chose de similaire se produit avec la complexité lorsque l'on prend un état quantique aléatoire d'un système entier et que l'on ne regarde qu'une partie de celui-ci. Tant que cette partie occupe moins de la moitié du système, sa complexité croît régulièrement.
Génie logiciel2026-07-113 minarXiv:2607.10347express
Un système quantique brouille les plans, mais pas les ingénieurs
Les dispositifs quantiques ne sont plus des curiosités de laboratoire. On les assemble, on les règle et on les répare comme du matériel ordinaire — sauf qu'à l'intérieur, il n'y a pas simplement du courant, mais des enchevêtrements de particules capables d'être dans plusieurs états à la fois.
Physique quantique2026-07-071 minarXiv:2607.06071express
Effet Mpemba quantique : le chaud refroidit plus vite, mais seulement à des températures extrêmement basses
L'effet Mpemba est une énigme où l'eau chaude gèle parfois plus vite que l'eau tiède. On l'explique généralement par la façon dont l'eau perd de la chaleur et de l'entropie (une mesure du désordre). Mais dans un verre d'eau, le chaos empêche de modéliser précisément le phénomène.
La valse à trois des trous noirs : quand le chaos orchestre les fusions
Au cœur de presque chaque galaxie sommeille un trou noir supermassif — chef d'orchestre invisible de l'orchestre stellaire. Lorsque les galaxies entrent en collision, leurs monstres centraux se rapprochent, s'enlaçant dans une danse gravitationnelle.
Un ordinateur quantique résout pour la première fois les équations d'Einstein
On frappe un diapason avec un maillet — et il vibre, tandis que le son s'estompe progressivement. C'est à peu près ce qui se passe pour un trou noir lorsqu'on le perturbe : il émet des ondes gravitationnelles — des ondulations de l'espace lui-même — puis se calme.
Gravité : classique ou quantique ?
La gravité semble simple : elle nous maintient au sol et fait tourner les planètes. Mais si elle était classique, c'est-à-dire décrite par les équations d'Einstein comme une courbure de l'espace-temps, tandis que toute la matière suivrait les lois quantiques du modèle standard, alors un simple bit…
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.
Physique quantique2026-06-041 minarXiv:2606.06316express
Un tamis quantique attrape les pannes rarissimes
Extraire une seule puce défectueuse parmi un million, sans aucun indice sur la nature du défaut, est un problème classique de chercher une aiguille dans une botte de foin. Un ordinateur classique testerait chaque puce une par une.
Physique quantique2026-06-012 minarXiv:2606.02715express
Piège à 11 000 atomes : un record vers l'ordinateur quantique
Un piège invisible fait de lumière laser a retenu 11 000 atomes, un nombre record pour l'ingénierie quantique. Auparavant, les physiciens ne manipulaient que des dizaines de ces particules ; désormais, on compte par milliers.
Physique quantique2026-05-292 minarXiv:2605.31442express
La roulette quantique au billet gagnant
Imaginez une bibliothèque où, au lieu de livres, se trouvent toutes les combinaisons imaginables de quelques dizaines de particules quantiques. Le nombre de ces combinaisons croît comme une boule de neige : ajoutez une particule — et le volume double. Pour une cinquantaine de particules, il y a plus d'étagères que d'atomes dans l'Univers visible.
L'Univers comme une horloge parfaite : pas de « cerveaux de Boltzmann »
Dans un univers éternel où le désordre augmente (entropie), la majeure partie du temps se déroule dans un vide homogène. De temps à autre, des structures complexes s'assemblent par hasard, comme des consciences éphémères — les « cerveaux de Boltzmann ».
Physique quantique2026-05-222 minarXiv:2605.23584express
La saveur des neutrinos change selon un horaire précis
Les neutrinos sont des particules quasi insaisissables qui traversent tout ce qui nous entoure. Dans un nuage dense, par exemple lors de l'explosion d'une étoile, ils se mettent à changer collectivement de type, ou de « saveur ». Ce processus ressemble à une foule où les gens changeraient de couleur de vêtements de manière synchronisée, mais pas tous d'un coup, plutôt par vagues.
Un assistant quantique débusque les fraudes rares
Dans l'océan des transactions bancaires, les fraudes sont plus rares que les étoiles à neutrons dans l'espace — seulement 0,1 % de toutes les opérations. Un détecteur ordinaire s'habitue à tout ce flux propre et perd de sa vigilance. C'est là qu'intervient le système hybride Q-SYNTH avec son générateur quantique.
Physique atomique2026-05-201 minarXiv:2605.21250express
Un piège à ions reproduit les processus des cellules vivantes
Le transfert d'énergie dans la photosynthèse ressemble à un toboggan : il s'affaisse sous le poids d'un enfant, modifiant la trajectoire du suivant. De même dans une feuille : l'état excité d'une molécule redessine instantanément le « paysage » de ses voisines.
Physique quantique2026-05-173 minarXiv:2605.17418express
Le paradoxe de l'ornithorynque : quand deux canaux valent mieux qu'un
Deux interprètes simultanés sont assis dans la même cabine. Le premier traduit de l'anglais vers le russe, mais avale la moitié des mots. Le second traduit du russe vers le français, et perd aussi la moitié. Si on les met ensemble, on pourrait penser que cela donnera un mélange confus : les pertes s'additionnent, et l'auditeur ne recevra qu'un quart du sens.
Physique quantique2026-04-302 minarXiv:2605.00205express
Quantique et cellule : trois chemins au carrefour
Trois artisans travaillent dans le même atelier. Le premier tente de comprendre si de minuscules sabliers sont intégrés dans les machines de la nature elle-même. Le deuxième ajuste un pointeur laser sur son microscope pour apercevoir des détails invisibles à l'œil nu.
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-182 minarXiv:2604.16953express
La chaleur du corps comme indice : un regard quantique sur le cancer du sein
L'air chaud au-dessus de l'asphalte tremble, révélant une surface surchauffée. C'est un peu comme cela que fonctionne une caméra thermique médicale : la peau au-dessus d'une tumeur est souvent légèrement plus chaude que la peau saine – de quelques fractions de degré seulement.
Physique quantique2026-04-141 minarXiv:2604.13176express
Un ordinateur quantique capture des particules cosmiques
Les qubits d'un ordinateur quantique supraconducteur ressemblent à des cordes tendues. Lorsqu'une particule venue du cosmos ou de la désintégration d'un élément radioactif passe à proximité, elle frappe ces cordes, qui se mettent à vibrer.
La galaxie perd la mémoire en un instant
Lancez deux cailloux identiques du sommet d'une montagne : si l'un atterrit un centimètre plus à gauche, au bout d'une minute ils se retrouveront dans des vallées différentes. La galaxie est comme cette montagne, mais avec des milliards de cailloux et une pente qui s'étire sur des millions d'années.
Physique quantique2026-04-081 minarXiv:2604.07452express
Les neutrinos s'intriquent comme une foule dans une pièce exiguë
À l'intérieur d'une étoile en explosion, les neutrinos filent si nombreux qu'ils commencent à s'influencer mutuellement. Leurs états quantiques s'entremêlent, comme des fils dans un écheveau serré où l'on ne distingue plus à qui appartient chaque brin.
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.
18 qubits dans un seul cristal
Dix-huit minuscules cellules s'alignent en deux rangées sur un morceau de germanium. Chaque cellule est une boîte quantique, un piège pour un électron dont le spin sert de qubit. Auparavant, de tels systèmes ne pouvaient être assemblés qu'en petites quantités, mais ici, c'est tout un réseau qui fonctionne comme un ensemble unique.
Des touches quantiques sur la toile du cosmos
Tout a commencé par d'infimes scintillements quantiques sur la toile primitive. L'expansion de l'univers — l'expansion avalancheuse proposée par Alan Guth — a étiré ces touches jusqu'à la taille des galaxies.
Monopôles magnétiques sur glace quantique
Les monopôles magnétiques sont comme des moitiés d'aimant qui ne peuvent pas exister seules dans un matériau ordinaire. Mais dans la glace de spin, ils apparaissent par paires, reliés par un fil invisible — la corde de Dirac.
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-201 minarXiv:2603.20372express
Un simulateur quantique copie un vrai aimant
Une balançoire à trois places ne se calme jamais : l'un des trois atomes est toujours en suspens. Tel est l'aimant frustré — une danse éternelle sans repos. Pour l'étudier, des physiciens ont construit un simulateur quantique de 256 atomes reproduisant exactement le cristal TmMgGaO₄.
Physique quantique2026-03-161 minarXiv:2603.15804express
Double signal : le bruit quantique recule
Le bit quantique (qubit) est semblable à un murmure à peine perceptible dans le brouhaha des voix. Un amplificateur ordinaire rend le murmure plus fort, mais avec lui, le brouhaha aussi, ce qui empêche de saisir l'essentiel.
Physique quantique2026-03-031 minarXiv:2603.03496express
Un ordinateur quantique trouve ce que l'ordinateur classique n'a pas pu
L'ordinateur quantique IBM Heron R3 a réussi là où la méthode classique a échoué. Il s'agit de trouver l'état fondamental – le niveau d'énergie le plus bas – d'un système de 49 bits quantiques. La méthode classique SCI (interaction de configurations sélectionnée) énumère les possibilités, mais sur ce problème, elle n'a pas trouvé la bonne réponse.
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.