Bonjour,

Quelques réflexions sur le sujet (à affiner si des pros passent par là).

L'ordinateur classique traite l'information sous forme de bits. Chaque bit représente un état binaire exclusif : \(0\) ou \(1\).

L'ordinateur quantique utilise des qubits.
Grâce aux lois de la mécanique quantique, un qubit peut exister dans une superposition d'états : c'est-à-dire une combinaison linéaire des états et |0> et |1> ("état quantique" dont l'issue de mesure sera probabiliste.)
L'espace de complexité et la puissance de calcul:
La puissance ne vient pas d'une horloge plus rapide, mais de la capacité à explorer des solutions multiples en une seule opération grâce à l'intrication et l'interférence quantiques.

L'intrication permet aux qubits d'être liés de manière "mystérieuse".
- les qubits intriqués possèdent des **corrélations non classiques**,
- la mesure de l'un donne des informations sur l'autre,
- mais cela ne permet pas de transmettre de l'information plus vite que la lumière.
Cela crée des corrélations puissantes qui sont exploitées par les algorithmes quantiques."

L'interférence quantique est utilisée pour "amplifier" les solutions correctes et "annuler" les solutions incorrectes, guidant le calcul vers le résultat souhaité, un peu comme deux ondes qui se renforcent ou s'annulent.

Dans le monde classique, la puissance est proportionnelle au nombre de circuits intégrés.
Pour doubler les capacités de mémoire ou de calcul, vous devez doubler le matériel.

Dans le monde quantique, la puissance de calcul augmente à chaque fois que l'on ajoute un qubit supplémentaire.
Un ordinateur doté de n qubits peut représenter une superposition de 2^n états en même temps.
Ce n'est pas que chaque qubit ajoute une puissance fixe, mais plutôt que l'ensemble des états que l'ordinateur peut explorer (ou plutôt "traiter en un seul bloc d'interférences")simultanément double avec chaque nouveau qubit
C'est cette capacité d'explorer un espace d'états gigantesque qui permet de résoudre certains problèmes beaucoup plus efficacement.

La superposition donne une **représentation simultanée d'états, mais à la fin, la mesure ne donne qu'un seul résultat.
L'accélération vient surtout de "l'interférence constructive/destructive" qui favorise certaines réponses.

On dit souvent que 300 qubits bien intriqués peuvent représenter simultanément plus d'états qu'il n'y a d'atomes dans l'univers observable… attention que "représenter" ne signifie pas "lire toutes les composantes ou faire des calculs utiles avec …"
****
Comparaison :

La spécialisation : L'ordinateur quantique n'est pas un remplaçant direct du PC ou du supercalculateur.
Il excelle dans des problèmes spécifiques (optimisation, modélisation moléculaire ou cryptographie) pour lesquels les algorithmes classiques nécessitent un temps exponentiellement plus long.

Le coût algorithmique : Pour un même problème, le mode de travail des deux machines est fondamentalement différent.

L'évaluation des performances : La puissance ne dépend pas uniquement du nombre de qubits, mais aussi de leur "probité" (taux d'erreur).

Au sujet de l'ordinateur quantique :
il se fonde sur les principes de la mécanique quantique pour effectuer des calculs. Contrairement aux ordinateurs classiques, qui utilisent des bits représentatifs des 0 ou des 1, les ordinateurs quantiques utilisent des qubits (q pour quantique) un qubit peut représenter un 0 ou un 1, mais aussi des combinaisons des deux, grâce à un phénomène quantique appelé superposition.
Cette particularité permet aux ordinateurs quantiques de traiter simultanément beaucoup plus d'information que les ordinateurs classiques. Ils pourraient résoudre des problèmes actuellement incalculables par les ordinateurs classiques en un temps raisonnable, simuler l'assemblage des molécules pour découvrir de nouveaux
médicaments, casser les systèmes de cryptage actuels ou améliorer les algorithmes d'apprentissage machine ou de l'intelligence artificielle. L'ordinateur quantique exploite principalement le concept de qubit, la superposition (le fait d'être dans un état combinaison de 0 et de 1); l'intrication quantique (corrélation particulière entre états quantiques, restant effective même après éloignement arbitraire des entités concernées), les interférences
ondulatoires.

d'accord mais au niveau des formules qu'est ce que ça donnerait ?

Bonjour,
Tenter de comparer la complexité d'un ordi classique versus un ordi
quantique par une simple expression mathématique, cela reviendrait à comparer la 'complexité' d'une Formule 1 et d'un tracteur agricole.

Tous deux ont un moteur, mais l'un est conçu pour la vitesse sur piste, l'autre pour le couple et le travail de la terre.
Ils n'effectuent pas des tâches analogues.
Vouloir les "comparer" n'a guère de sens pratique.

Un algorithme classique en représente un mur du temps infranchissable (calcul séquentiel).

Un algorithme quantique, quant à lui, exploite la physique (superposition et intrication) pour redéfinir la nature même de la tâche.

Vouloir les comparer sur une simple ligne de notation mathématique est complexe, l'expression des complexités sont différente pour chaque type de même problème pour les 2 sortes d'ordinateurs.  

Quelques exemple pour étayer :  

Comment déterniner la valeur de n ?

n dépend uniquement des données du problème et de la manière dont on les code. Il ne dépend jamais de la machine (classique ou quantique).

exemple de tableau récapitulatif de la complexité pour trois cas, exprimée en fonction de la taille exacte des données (n).

Exemple de problèmes :

1. Le Cadenas (Recherche non triée)
Définition de n : Le nombre total de bits nécessaires pour écrire les combinaisons.
Ordinateur Classique :
Explication : Complexité exponentielle. Il faut tester les clés une par une.

Ordinateur Quantique :
Explication : Grâce à l'algorithme de Grover, on passe à la racine carrée du nombre de possibilités. C'est un gain massif, même si cela reste techniquement exponentiel.

2. Le Tri d'une liste de mots
Définition de n : Le nombre total de bits de toute la liste (Mots X Lettres X Bits/lettre).
Ordinateur Classique :
Explication : Complexité quasi-linéaire. C'est extrêmement efficace.

Ordinateur Quantique :
Explication : Aucun gain. Le quantique n'accélère pas le tri de données textuelles ou de fichiers stockés sur un disque dur classique.

3. L'Itinéraire GPS (Problème du voyageur de commerce)
Le but est de trouver le chemin le plus court passant par un ensemble de villes.
Définition de n : Le nombre total de bits pour stocker la carte (coordonnées des villes et distances).
Ordinateur Classique : (ou pire selon les variantes, généralement modélisé par où V est le nombre de villes).

Ordinateur Quantique :
Explication : Ce problème fait partie de la classe dite "NP-difficile".
L'ordinateur quantique (via Grover ou des algorithmes d'optimisation comme l'QAOA) permet d'accélérer la recherche, mais il ne sait pas résoudre ce problème de manière instantanée (polynomiale). Le calcul reste difficile à grande échelle.

Ce qu'il faut retenir:
L'avantage du quantique dépend entièrement de la structure mathématique du problème :
Gain gigantesque (Exponentiel à Polynomial) : Uniquement sur des problèmes mathématiques très précis (ex: la factorisation d'un nombre pour casser un code secret, via l'algorithme de Shor).
Gain modéré (Racine carrée) : Sur les recherches exhaustives (cadenas, labyrinthes, itinéraires).Aucun gain : Sur la gestion de données pures (trier, filtrer, copier des fichiers).
****
Exemple où l'ordinateur quantique écrase complètement l'ordinateur classique, en faisant passer la complexité d'une fonction exponentielle à une fonction polynomiale ?

La factorisation en nombres premiers (via l'Algorithme de Shor)
C'est ce calcul exact qui protège aujourd'hui vos transactions bancaires et vos messages chiffrés (le système RSA).

Le Problème:
On vous donne un nombre géant N (qui est le produit de deux nombres premiers p et q, soit N = p X q.
La mission est de trouver p et q.

Définition de n : Le nombre de bits nécessaires pour écrire le nombre N.
Par exemple, pour le chiffrement standard actuel RSA-2048, (n = 2048) bits.

1. Sur un ordinateur classique:
Trouver les facteurs d'un grand nombre est une tâche titanesque.
Le meilleur algorithme classique connu (appelé le Crible généralisé sur les corps de nombres) a une complexité quasi-exponentielle.
Complexité classique : Environ
En pratique : Pour factoriser un nombre de (n = 2048) bits, il faudrait des milliards d'années à un supercalculateur classique.
C'est pour cela que vos données bancaires sont en sécurité aujourd'hui.

2. Sur un ordinateur quantique (Algorithme de Shor)
Shor a découvert qu'en utilisant les superpositions et une propriété quantique appelée la "Transformée de Fourier Quantique", on pouvait transformer ce problème de recherche en un problème de détection de fréquences (ou de périodes).
Complexité quantique :
En pratique : La complexité devient polynomiale.
Pour le même nombre de (n = 2048) bits, le calcul ne demande plus des milliards d'années, mais environ (2048^3 8,5) milliards d'opérations élémentaires.
Un ordinateur quantique parfait exécuterait cela en quelques minutes ou heures.