Pourquoi et comment un ordinateur quantique est-il plus rapide qu'un ordinateur ordinaire?

Je lis actuellement un livre (et beaucoup de wikipedia) sur la physique quantique et je n'ai pas encore compris comment un ordinateur quantique peut être plus rapide que les ordinateurs que nous avons aujourd'hui.

Comment un ordinateur quantique peut-il résoudre un problème en temps sub-exponentiel qu'un ordinateur classique ne peut résoudre qu'en temps exponentiel?

Un ordinateur quantique en soi n'est pas plus rapide. Au lieu de cela, il a un modèle de calcul différent . Dans ce modèle, il existe des algorithmes pour certains problèmes (pas tous!) Qui sont asymptotiquement plus rapides que les algorithmes classiques les plus rapides (ou connus pour certains problèmes).

Je recommande de lire The Limits of Quantum de Scott Aaronson: il s'agit d'un court article populaire expliquant ce que l'on peut attendre des ordinateurs quantiques.

L'idée de base est que les dispositifs quantiques peuvent être dans plusieurs états à la fois. En règle générale, une particule peut avoir sa rotation montante et descendante en même temps. Ceci s'appelle la superposition. Si vous combinez n particule, vous pouvez avoir quelque chose qui peut superposer états. Ensuite, si vous parvenez à étendre des opérations boléennes à des états superposés (ou à des symboles superposés), vous pouvez effectuer plusieurs calculs en même temps. Cela a des contraintes mais peut accélérer certains algorithmes. Un problème physique majeur est qu’il est plus difficile de maintenir la superposition sur des systèmes plus grands.$2^n$

C’est un problème ouvert qui fait l’objet de recherches pointues si les algorithmes quantiques seront un jour plus rapides que les algorithmes «classiques», tant au niveau théorique qu’appliqué. dans la théorie de la complexité, cela se reflète dans la question, par exemple BQP =? P c'est-à-dire si la classe "P" de l'informatique quantique est équivalente ou non à la classe classique P (temps polynomial) et il y a beaucoup d'autres questions ouvertes connexes.

Il existe un point de donnée très intéressant et significatif: l’ algorithme primé de Shors factorise les nombres en temps quantique P, mais on ne sait toujours pas s’il existe un algorithme de factorisation classique à temps-P.

Une nouvelle direction au cours des dernières années concerne les travaux en informatique quantique adiabatique, qui sont plus faciles à implémenter / à mettre au point que d’autres méthodes standard impliquant le transport par bits (mais néanmoins extrêmement difficiles à mettre en œuvre).

le seul ordinateur quantique construit à ce jour est celui de Dwave Systems et fait actuellement l’objet d’un examen scientifique approfondi et de nombreuses controverses quant à ses effets et à ses performances quantiques; il est très coûteux et ne surpasse fondamentalement pas un ordinateur de bureau, lorsque le code classique est entièrement optimisé (humain / manuel). Cependant, on peut affirmer à juste titre qu'aucune autre entité de recherche constituée par des entreprises, des gouvernements ou des universités ne semble être à un niveau aussi proche de son niveau d'avancement appliqué / technique / technique jusqu'à présent.

Pour le moment, les perspectives scientifiques sont nuageuses et certains experts scientifiques / critiques / sceptiques, par exemple Dyakonov, ont longtemps cru / argumenté que des ordinateurs de gestion de la qualité évolutifs ne se matérialiseront jamais en raison de difficultés techniques insurmontables et / ou d'obstacles.

J'ai une preuve qui dit que même la puissance quantique a ses limites.

Les ordinateurs Quantum trouvent très difficile d’atteindre un kilobit de bits. Mais même s'ils y arrivent seulement, c'est assez puissant.

16384 qbits feraient 128 dimensions d'espace par 128 pas de temps, recherche exhaustive, c'est incroyable, 100 pas de temps arbre de probabilité de 100 dimensions !!! mais ne vous attendez pas à plus que ce montant pour quantum dans un proche avenir.

Un système quantique est un système qui existe dans un ou plusieurs états quantiques à différentes probabilités déterminées par des contraintes environnementales. En supposant qu'un ordinateur quantique contienne tous les états d'un système quantique à n bits, l'extraction de l'un de ces états réduit le système à un de ces états. Cela s'apparente à une fonction de hachage utilisant O (1) pour rechercher un compartiment sans itération. Deux choses sont nécessaires, le stockage quantique des systèmes à n bits et une fonction de type hachage pour réduire l'état requis. Les contraintes jouent le rôle de différentes fonctions de hachage pour réduire le système à n bits à l'état souhaité.

Pensez-y de la manière suivante: il existe des problèmes qui peuvent être résolus en résolvant un grand nombre de sous-cas individuels [exemple: factorisation par division de procès]. La résolution de ces problèmes prend beaucoup de temps si l’on doit résoudre les sous-dossiers les uns après les autres. Ils peuvent être résolus beaucoup plus rapidement si l'on peut fournir suffisamment de matériel pour résoudre tous les sous-cas en parallèle, mais ce n'est pas pratique car la quantité de matériel nécessaire augmente avec la taille du problème. L’informatique quantique exploite la fonctionnalité de superposition d’états de la mécanique quantique pour simuler la fourniture d’un matériel suffisant, c’est-à-dire que chaque état de la superposition est la «machine» de l’un des sous-cas. Notez que cette simulation est effectuée non par logiciel, mais par nature elle-même.