Les ordinateurs quantiques et l'informatique quantique sont un nouveau mot à la mode qui a été ajouté à notre espace d'information avec l' intelligence artificielle , l'apprentissage automatique et d'autres termes de haute technologie. En même temps, je n'ai pas été en mesure de trouver sur Internet des documents qui me mettraient dans la tête un puzzle appelé «comment fonctionnent les ordinateurs quantiques» . Oui, il y a beaucoup d'excellents ouvrages, y compris sur le Habré (voir la liste des ressources ), les commentaires sur lesquels, comme cela arrive habituellement, sont encore plus informatifs et utiles, mais l'image dans la tête, comme on dit, ne correspondait pas.
Et récemment, des collègues sont venus me voir et m'ont demandé: «Comprenez-vous comment fonctionne un ordinateur quantique? Pouvez-vous nous le dire? »Et puis j'ai réalisé que le problème avec le pliage d'une image complète dans ma tête n'est pas seulement le mien.
En conséquence, une tentative a été faite pour compiler des informations sur les ordinateurs quantiques dans un schéma logique cohérent dans lequel, à un niveau de base, sans immersion profonde dans les mathématiques et la structure du monde quantique , il a été expliqué ce qu'était un ordinateur quantique, sur quels principes il fonctionnait, et aussi quels problèmes rencontrés scientifiques lors de sa création et de son fonctionnement.
Table des matières
Clause de non-responsabilité
(au contenu)
L'auteur n'est pas un spécialiste de l'informatique quantique, et le public cible de l'article est les mêmes experts en informatique, pas des spécialistes quantiques , qui veulent également recueillir dans leur tête une image intitulée «Comment fonctionnent les ordinateurs quantiques». Pour cette raison, de nombreux concepts de l'article sont délibérément simplifiés pour une meilleure compréhension des technologies quantiques au niveau «de base», mais sans beaucoup de simplification avec la perte de contenu et d'adéquation des informations .
À certains endroits, l'article utilise des documents provenant d'autres sources, dont une liste est donnée à la fin de l'article . Dans la mesure du possible, des liens directs et des références au texte, tableau ou image d'origine sont insérés. Si quelque part j'ai oublié quelque chose (ou quelqu'un), écrivez - je le corrigerai.
Présentation
(au contenu)
Dans ce chapitre, nous examinerons brièvement comment l'ère quantique a commencé, ce qui a motivé l'idée d'un ordinateur quantique, qui (quels pays et sociétés) sont actuellement les principaux acteurs de cette compensation, et parlerons brièvement des principales directions de développement de l'informatique quantique.
Comment tout a commencé
(au contenu)
Le point de référence de l'ère quantique est considéré comme étant 1900, lorsque M. Planck a avancé pour la première fois l' hypothèse selon laquelle l'énergie est émise et absorbée non pas en continu, mais dans des quanta (portions) séparés. L'idée a été reprise et développée par de nombreux scientifiques exceptionnels de l'époque - Bohr, Einstein, Heisenberg, Schrödinger, ce qui a finalement conduit à la création et au développement d'une science telle que la physique quantique . Il y a beaucoup de bons matériaux sur le développement de la physique quantique en tant que science sur le Web. Dans cet article, nous ne nous attarderons pas sur cela en détail, mais il était nécessaire d'indiquer la date à laquelle nous sommes entrés dans la nouvelle ère quantique.
La physique quantique a introduit dans notre vie ordinaire de nombreuses inventions et technologies, sans lesquelles il est désormais difficile d'imaginer le monde qui nous entoure. Par exemple, un laser qui est désormais utilisé partout, des appareils électroménagers (niveaux laser, etc.) aux systèmes de haute technologie (lasers de correction de la vision, bonjour meklon ). Il serait logique de supposer que, tôt ou tard, quelqu'un mettra en avant l'idée de ne pas utiliser les systèmes quantiques pour les calculs. Et donc en 1980, c'est arrivé.
Wikipédia indique que le scientifique Yuri Manin a été le premier à exprimer l'idée de l'informatique quantique en 1980. Mais ils n'ont vraiment commencé à en parler qu'en 1981, lorsque le célèbre R. Feynman, dans son rapport à la première conférence sur la physique computationnelle tenue au Massachusetts Institute of Technology , a noté qu'il était impossible de modéliser efficacement l'évolution d'un système quantique sur un ordinateur classique. Il a proposé un modèle élémentaire d'un ordinateur quantique qui serait capable de conduire une telle simulation.
Il existe un tel travail sur le Web dans lequel la chronologie du développement de l'informatique quantique est considérée plus académiquement et en détail, mais nous allons passer brièvement en revue:
Jalons de l'histoire des ordinateurs quantiques:
Comme vous pouvez le voir, 17 ans se sont écoulés (de 1981 à 1998) depuis le moment de l'idée jusqu'à sa première mise en œuvre dans un ordinateur à 2 qubits, et 21 ans (de 1998 à 2019) jusqu'au moment où le nombre de qubits est passé à 53. Il a fallu 11 ans (de 2001 à 2012) pour améliorer le résultat de l'algorithme Shore (nous y reviendrons un peu plus loin) du nombre 15 à 21. De plus, il y a seulement trois ans, nous avons réalisé ce dont parlait Feynman, et apprendre à simuler les systèmes physiques les plus simples.
Le développement de l'informatique quantique est lent. Les scientifiques et les ingénieurs sont confrontés à des tâches très complexes, les états quantiques sont très éphémères et fragiles, et pour les garder suffisamment longtemps pour effectuer des calculs, il faut construire des sarcophages pour des dizaines de millions de dollars, dans lesquels la température est maintenue juste au-dessus du zéro absolu, et qui sont protégés contre influences extérieures. Nous parlerons plus en détail de ces tâches et problèmes.
Joueurs de premier plan
(au contenu)
Les diapositives de cette section sont extraites de l'article Quantum Computer: A Big Boost Game. Conférence à Yandex , d'un chercheur du Russian Quantum Center Alexei Fedorov. Je me permettrai des citations directes:
Tous les pays technologiquement performants sont actuellement activement engagés dans le développement de technologies quantiques. Une énorme somme d'argent est investie dans ces études, des programmes spéciaux pour soutenir les technologies quantiques sont en cours de création.
La course quantique implique non seulement les États, mais aussi les entreprises privées. Au total, Google, IBM, Intel et Microsoft ont investi environ 0,5 milliard de dollars dans le développement d'ordinateurs quantiques ces dernières années, créé de grands laboratoires et centres de recherche.
Il existe de nombreux articles sur Habré et sur le Web, par exemple ici , ici et ici , dans lesquels l'état actuel des choses avec le développement des technologies quantiques dans différents pays est examiné plus en détail. Pour nous maintenant, l'essentiel est que tous les principaux pays et acteurs technologiques avancés investissent d'énormes sommes d'argent dans la recherche dans ce sens, ce qui donne l'espoir d'une sortie de l'impasse technologique actuelle.
Orientations de développement
(au contenu)
Pour le moment (je me trompe peut-être), les principaux efforts (et des résultats plus ou moins significatifs) pour tous les principaux acteurs sont concentrés dans deux directions:
- Ordinateurs quantiques spécialisés qui visent à résoudre un problème spécifique spécifique, par exemple, des problèmes d'optimisation. Un exemple de produit est les ordinateurs quantiques D-Wave.
- Ordinateurs quantiques universels - qui sont capables d'implémenter des algorithmes quantiques arbitraires (Shore, Grover, etc.). Implémentations d'IBM, Google.
D'autres vecteurs de développement que nous offre la physique quantique, tels que:
certes aussi dans la liste des domaines de recherche, mais une sorte de résultats plus ou moins significatifs semblent actuellement être là.
De plus, vous pouvez lire la feuille de route pour le développement des technologies quantiques , ainsi, google « développement des technologies quantiques », par exemple, ici , ici et ici .
Les bases. Objet quantique et systèmes quantiques
(au contenu)
La chose la plus importante à comprendre de cette section est que
Un ordinateur quantique (par opposition à un ordinateur conventionnel) utilise des objets quantiques comme supports d'information, et les objets quantiques doivent être connectés à un système quantique pour effectuer des calculs.
Qu'est-ce qu'un objet quantique?
Un objet quantique est un objet du micromonde (monde quantique) qui présente des propriétés quantiques:
- A un certain état avec deux niveaux de limite
- Il est en superposition de son état jusqu'au moment de la mesure
- Enchevêtré avec d'autres objets pour créer des systèmes quantiques
- Effectue un théorème d'interdiction de clone (vous ne pouvez pas copier l'état d'un objet)
Analysons chaque propriété plus en détail:
A un certain état avec deux niveaux de limite (état final)
Un exemple classique du monde réel est une pièce de monnaie. Elle a un état de «côté», qui prend deux niveaux limites - «aigle» et «queues».
Il est en superposition de son état jusqu'au moment de la mesure
Jetant une pièce, elle vole et tourne. Pendant qu'il tourne, il est impossible de dire à quel niveau de frontière se situe son état "latéral". Mais si nous le claquons et regardons le résultat, la superposition d'États s'effondre immédiatement dans l'un des deux frontières - «têtes» et «queues». Frapper une pièce dans notre cas est une dimension.
Enchevêtré avec d'autres objets pour créer des systèmes quantiques
C’est difficile avec une pièce, mais on va essayer. Imaginez que nous lançions trois pièces pour qu'elles tournent en s'accrochant les unes aux autres, un tel jonglage de pièces. À chaque instant, non seulement chacun d'eux est dans une superposition d'états, mais ces états s'influencent mutuellement (les pièces se heurtent).
Effectue un théorème d'interdiction de clone (vous ne pouvez pas copier l'état d'un objet)
Pendant que les pièces volent et tournent, nous ne pouvons en aucun cas créer une copie de l'état de rotation des pièces distinctes du système. Le système vit en lui-même et est très jaloux de donner des informations.
Quelques mots sur le concept même de «superposition» , dans presque tous les articles, la superposition est expliquée comme «est dans tous les états en même temps», ce qui, bien sûr, est vrai, mais parfois c'est trop déroutant. Une superposition d'états peut également être considérée comme le fait qu'à chaque instant un objet quantique a certaines probabilités de s'effondrer dans chacun de ses niveaux limites, et au total ces probabilités sont naturellement égales à 1 . De plus, lorsque nous considérons le qubit, nous nous attarderons sur ce point plus en détail.
Pour les pièces, cela peut être imaginé visuellement - en fonction de la vitesse initiale, de l'angle du lancer, de l'état de l'environnement dans lequel la pièce vole, à chaque instant, la probabilité d'obtenir un «aigle» ou une «queue» est différente. Et, comme mentionné précédemment, l'état d'une telle pièce volante peut être imaginé comme «se trouve dans tous ses états limites en même temps, mais avec une probabilité différente de leur mise en œuvre».
Tout objet pour lequel les propriétés ci-dessus sont satisfaites et que nous pouvons créer et gérer peut être utilisé comme support de stockage dans un ordinateur quantique.
Un peu plus loin, nous parlerons de l'état actuel des choses avec l'implémentation physique des qubits en tant qu'objets quantiques, et de ce que les scientifiques utilisent maintenant à ce titre.
Ainsi, la troisième propriété dit que les objets quantiques peuvent être enchevêtrés pour créer des systèmes quantiques. Qu'est-ce qu'un système quantique?
Un système quantique est un système d'objets quantiques intriqués ayant les propriétés suivantes:
- Un système quantique est dans une superposition de tous les états possibles des objets qui le composent
- Il est impossible de connaître l'état du système jusqu'au moment de la mesure
- Au moment de la mesure, le système met en œuvre l'une des variantes possibles de ses états limites
(et un peu en avance)
Corollaire des programmes quantiques :
- Un programme quantique a un état donné du système à l'entrée, une superposition à l'intérieur, une superposition à la sortie
- À la sortie du programme après la mesure, nous avons une implémentation probabiliste de l'un des états finaux possibles du système (plus les erreurs possibles)
- Tout programme quantique a une architecture de cheminée (entrée -> sortie. Il n'y a pas de cycles, vous ne pouvez pas voir l'état du système au milieu du processus.)
Comparaison d'un ordinateur quantique et d'un ordinateur conventionnel
(au contenu)
Comparons maintenant un ordinateur conventionnel avec un ordinateur quantique.
Niveau logique
Sur un ordinateur ordinaire, c'est un peu. Un bit déterministe bien connu de bout en bout . Il peut prendre des valeurs égales à 0 ou 1. Il remplit le rôle d'une unité logique pour un ordinateur ordinaire, mais est totalement inadapté pour décrire l'état d'un objet quantique , qui, comme nous l'avons déjà dit, est dans la nature avec l' hypothèse de ses états limites .
Pour cela, un qubit a été inventé. Dans ses états limites, il réalise les états | 0> et | 1> similaires à 0 et 1, et en superposition il représente une distribution de probabilité sur ses états limites |0> et |1> :
a|0> + b|1>, , a^2+b^2=1
dans ce cas, a et b représentent les amplitudes des probabilités , et les carrés de leurs modules représentent les probabilités pour obtenir précisément ces valeurs des états limites |0> et |1>, si le qubit est effondré par mesure en ce moment.
Niveau physique
Au niveau technologique actuel de développement, l'implémentation physique d'un bit pour un ordinateur ordinaire est un transistor semi - conducteur , pour un quantum, comme nous l'avons dit, tout objet quantique . Dans la section suivante, nous parlerons de ce qui est maintenant utilisé comme porteurs physiques de qubits.
Support de stockage
Pour un ordinateur ordinaire, il s'agit d'un courant électrique - niveaux de tension, présence ou absence de courant, etc., pour un ordinateur quantique - l' état même d'un objet quantique (direction de polarisation, spin, etc.), qui peut être dans un état de superposition.
Les opérations
Pour implémenter des circuits logiques sur un ordinateur ordinaire, nous utilisons tous des opérations logiques bien connues; pour les opérations sur qubits, nous avons dû trouver un système d'opérations complètement différent appelé portes quantiques . Les portes sont à un seul qubit et à deux qubits, selon le nombre de qubits convertis.
Exemples de portes quantiques:
Il y a le concept d'un ensemble universel de portes , qui sont suffisantes pour effectuer n'importe quel calcul quantique. Par exemple, un ensemble universel comprend une soupape Hadamard, une soupape de déphasage, une soupape CNOT et une soupape π⁄8. Avec leur aide, vous pouvez effectuer n'importe quel calcul quantique sur un ensemble arbitraire de qubits.
Dans cet article, nous ne nous attarderons pas en détail sur le système des portes quantiques; plus en détail à leur sujet et les opérations logiques sur les qubits peuvent être lues, par exemple, ici . La principale chose à retenir:
- Les opérations sur les objets quantiques nécessitent la création de nouveaux opérateurs logiques (portes quantiques)
- Les vannes quantiques sont à un seul qubit et à deux qubits
- Il existe des ensembles universels de portes avec lesquelles vous pouvez effectuer n'importe quel calcul quantique
Interconnexion
Un transistor nous est complètement inutile, pour faire des calculs, nous devons connecter plusieurs transistors les uns aux autres, c'est-à-dire créer une puce semi-conductrice à partir de millions de transistors, sur laquelle nous construisons déjà des circuits logiques, des ALU et, finalement, obtenons un processeur moderne dans sa forme classique.
Un qubit nous est également complètement inutile (enfin, ne serait-ce qu'en termes académiques),
pour faire des calculs, nous avons besoin d'un système de qubits (objets quantiques)
qui, comme nous l'avons déjà dit, est créé par l'intrication de qubits entre eux de sorte que les changements dans leurs états se produisent de concert.
Des algorithmes
Les algorithmes standard que l'humanité a accumulés jusqu'à présent ne conviennent absolument pas à la mise en œuvre sur un ordinateur quantique. Oui, en général, et ce n'est pas nécessaire. Les ordinateurs quantiques basés sur la logique de porte sur qubits nécessitent la création d'algorithmes complètement différents, des algorithmes quantiques. Parmi les algorithmes quantiques les plus connus, trois peuvent être distingués:
Principe
Et la différence la plus importante est le principe du travail. Pour un ordinateur standard, il s'agit d'un principe numérique strictement déterminé , basé sur le fait que si nous définissons un état initial du système et le transmettons à un algorithme donné, le résultat des calculs sera le même quel que soit le nombre de fois où nous exécutons ce calcul. En fait, ce comportement est exactement ce que nous attendons de l'ordinateur.
Un ordinateur quantique fonctionne sur un principe analogique et probabiliste . Le résultat d'un algorithme donné à un état initial donné est un échantillon de la distribution de probabilité des implémentations finales de l'algorithme plus les erreurs possibles.
Cette nature probabiliste de l'informatique quantique est due à l'essence très probabiliste du monde quantique. "Dieu ne joue pas aux dés avec l'univers ", a déclaré le vieil Einstein, mais toutes les expériences et observations jusqu'à présent (dans le paradigme scientifique actuel) confirment le contraire.
Implémentations physiques des qubits
(au contenu)
Comme nous l'avons déjà dit, un qubit peut être représenté par un objet quantique, c'est-à-dire un tel objet physique qui met en œuvre les propriétés quantiques décrites ci-dessus. Autrement dit, tout objet physique dans lequel il y a deux états et ces deux états sont dans un état de superposition peut être utilisé pour construire un ordinateur quantique.
«Si nous pouvons mettre un atome à deux niveaux différents et les contrôler, alors voici un qubit pour vous. Si nous pouvons le faire avec un ion, qubit. C'est la même chose avec le courant. Si nous l'exécutons dans le sens horaire et antihoraire en même temps, voici un qubit. » (C)
Il y a un merveilleux commentaire sur l' article dans lequel la variété actuelle des réalisations physiques du qubit est examinée plus en détail, mais nous énumérons simplement les plus célèbres et les plus courantes:
De toute cette diversité, la première méthode de production de qubits à base de supraconducteurs est la plus élaborée. Google , IBM , Intel et d'autres acteurs majeurs l'utilisent pour construire leurs systèmes.
Eh bien, lisez également la revue des possibles réalisations physiques des qubits d' Andrew Daley, 2014 .
Les bases. Le principe de fonctionnement d'un ordinateur quantique
(au contenu)
Le matériel de cette section (tâche et images) est tiré de l'article «À propos du complexe. Comment fonctionne un ordinateur quantique . "
Imaginons donc que nous ayons la tâche suivante:
Il y a un groupe de trois personnes: (A) ndrey, (B) olodya et (C) l'hérésie . Il y a deux taxis (0 et 1) .
On sait également que:
- (A) ndrey, (B) olodya - amis
- (A) ndrey, (C) hérésie - ennemis
- (B) olodya et (C) hérésie - ennemis
Tâche: placer les gens en taxi pour que Max (amis) et Min (ennemis)
Score: L = (nombre d'amis) - (nombre d'ennemis) pour chaque option d'hébergement
IMPORTANT: Supposons qu'il n'y a pas d'heuristique, il n'y a pas de solution optimale. Dans ce cas, le problème n'est résolu que par une recherche exhaustive des options.
Solution sur un ordinateur ordinaire
Comment résoudre ce problème sur un (super) ordinateur (ou cluster) ordinaire - il est clair que nous devons trier toutes les options possibles dans une boucle . Si nous avons un système multiprocesseur, nous pouvons paralléliser le calcul des solutions sur plusieurs processeurs et collecter ensuite les résultats.
Nous avons 2 options d'hébergement possibles (taxi 0 et taxi 1) et 3 personnes. L'espace des solutions est 2 ^ 3 = 8 . Vous pouvez passer par 8 options même sur une calculatrice, ce n'est pas un problème. Et maintenant, nous allons compliquer la tâche - nous avons 20 personnes et deux bus, l'espace de solution est de 2 ^ 20 = 1 048 576. Rien de trop compliqué. Augmentons le nombre de personnes de 2,5 fois - prenez 50 personnes et deux trains, l'espace de décision est maintenant de 2 ^ 50 = 1,12 x 10 ^ 15 . Un (super) ordinateur ordinaire commence déjà à avoir de sérieux problèmes. Nous augmenterons le nombre de personnes de 2 fois, 100 personnes nous proposeront 1,2 x 10 ^ 30 options possibles.
Tout, dans un délai raisonnable, cette tâche ne peut pas être comptée.
Nous connectons un supercalculateur
L'ordinateur le plus puissant actuellement est le numéro 1 du Top500 , c'est Summit , avec une capacité de 122 Pflops . Supposons que pour le calcul d'une option, 100 opérations nous suffisent, puis pour résoudre le problème pour 100 personnes dont nous avons besoin:
(1,2 x 10 ^ 30100) / 122x10 ^ 15 / (60 60 24365 ) = 3 x 10 ^ 37 ans.
Comme nous le voyons, lorsque la dimension des données source augmente, l'espace de la solution croît selon une loi de puissance , dans le cas général pour N bits nous avons 2 ^ N solutions possibles qui, avec un N (100) relativement petit, nous donnent un espace illisible (au niveau technologique actuel) décisions.
Existe-t-il des alternatives? Comme vous l'avez peut-être deviné, oui, il y en a.
Mais avant de passer à comment et pourquoi les ordinateurs quantiques peuvent résoudre efficacement de tels problèmes, rappelons un peu ce qu'est une distribution de probabilité . Ne vous inquiétez pas, l'article de revue, il n'y aura pas de mathématiques dures ici, nous nous en sortirons avec un exemple classique avec un sac et des balles.
Un peu de combinatoire, de théorie des probabilités et d'un étrange expérimentateur
Prenez un sac et mettez -y 1000 boules blanches et 1000 boules noires . Nous allons mener une expérience - sortir le ballon, écrire la couleur, remettre le ballon dans le sac et mélanger les balles dans le sac.
Nous avons mené l'expérience 10 fois, retiré 10 boules noires . Peut-être? Tout à fait. Cet échantillon nous donne-t-il une idée raisonnable de la véritable distribution dans le sac? Evidemment non. Ce que vous devez faire est juste, répétez l'expérience un million de fois et calculez la fréquence de la chute des boules noires et blanches. Nous obtenons, par exemple, 49,95% de noir et 50,05% de blanc . Dans ce cas, la structure de distribution à partir de laquelle nous échantillonnons est déjà plus ou moins claire (nous prenons une boule).
La principale chose que vous devez comprendre est que l'expérience elle-même est de nature probabiliste , avec un échantillon (boule), nous ne reconnaissons pas la véritable structure de distribution, nous devons répéter l'expérience plusieurs fois et faire la moyenne des résultats.
Ajoutez 10 boules rouges et 10 vertes à notre sac (erreurs). Répétez l'expérience 10 fois. En tirées 5 rouges et 5 vertes . Peut-être? Oui Nous pouvons dire quelque chose sur la vraie distribution - Non. Ce qui doit être fait - eh bien, vous comprenez.
Pour comprendre la structure de la distribution de probabilité, il est nécessaire d'échantillonner à plusieurs reprises les résultats individuels de cette distribution et de faire la moyenne des résultats.
Nous relions la théorie à la pratique
Maintenant, au lieu de boules noires et blanches, prenons les boules de billard et mettons dans le sac 1000 boules avec le numéro 2, 1000 avec le numéro 7 et 10 boules avec d'autres numéros . Imaginez un expérimentateur formé à des étapes simples (obtenir une balle, noter le nombre, remettre la balle dans le sac, mélanger les balles dans le sac) et il le fait en 150 microsecondes. Eh bien, un tel expérimentateur sur les aides (pas la publicité sur les médicaments !!!). Puis, en 150 secondes, il pourra mener notre expérience 1 million de fois et nous fournir les résultats de la moyenne.
Ils ont assis l'expérimentateur, ont donné le sac, se sont détournés, ont attendu 150 secondes - ont reçu:
numéro 2 - 49,5%, numéro 7 - 49,5%, les chiffres restants dans le montant - 1%.
Oui, c'est vrai, notre sac est un ordinateur quantique avec un algorithme qui résout notre problème , et les balles sont des solutions possibles. Puisqu'il y a deux solutions correctes, un ordinateur quantique nous donnera également probablement l'une de ces solutions possibles, et 0,5% (10/2000) d'erreurs , dont nous parlerons plus tard.
Pour obtenir le résultat d'un ordinateur quantique, vous devez exécuter l'algorithme quantique à plusieurs reprises sur le même ensemble de données d'entrée et faire la moyenne du résultat.
Évolutivité d'un ordinateur quantique
Imaginons maintenant que pour un problème auquel 100 personnes participent (nous nous souvenons de cet espace de décision 2 ^ 100 ), il n'y a que deux solutions correctes. Ensuite, si nous prenons 100 qubits et écrivons un algorithme qui calcule notre fonction objectif (L, voir ci-dessus) sur ces qubits, alors nous obtenons un sac qui contient 1000 boules avec le numéro de la première bonne réponse, 1000 avec le numéro de la deuxième bonne réponse et 10 boules avec d'autres numéros. Et notre expérimentateur dans les mêmes 150 secondes nous donnera une estimation de la distribution probabiliste des bonnes réponses .
Le temps d'exécution de l'algorithme quantique (avec quelques hypothèses) peut être considéré comme constant O (1) par rapport à la dimension de l'espace de solution (2 ^ N).
Et c'est précisément cette propriété d'un ordinateur quantique - la constance du temps d'exécution par rapport à la complexité de l'espace de décision qui croît selon la loi de puissance est la clé.
Qubit et mondes parallèles
Comment cela se produit-il? Qu'est-ce qui permet à un ordinateur quantique d'effectuer des calculs si rapidement? Il s'agit de la nature quantique du qubit.
Regardez, nous avons dit qu'un qubit en tant qu'objet quantique réalise l'un de ses deux états lorsqu'il est observé , mais dans la "nature vivante", il est dans une superposition d'états , c'est-à-dire qu'il se trouve dans ses deux états limites en même temps (avec une certaine probabilité).
Prenez (A) Ndrey et imaginez son état (dans lequel le véhicule est 0 ou 1) comme un qubit. Ensuite, nous avons (dans un espace quantique) deux mondes parallèles , dans un (A) assis dans un taxi 0, dans un autre monde - dans un taxi 1. En même temps dans deux taxis , mais avec une certaine chance de le trouver dans chacun d'eux lors de l'observation.
Prenez (B) olod et imaginez également son état comme un qubit. Deux autres mondes parallèles surgissent. Mais alors que ces paires de mondes (A) et (B) n'interagissent en aucune façon. Que faut-il faire pour créer un système connecté ? C'est vrai, vous devez connecter (confondre) ces qubits. Nous prenons et confondons (A) avec (B) - nous obtenons un système quantique de deux qubits (A, B), qui implémente en lui-même quatre mondes parallèles interdépendants . Ajoutez (C) erge et obtenez un système de trois qubits (ABC), qui implémente huit mondes parallèles interdépendants .
L'essence de l'informatique quantique (la mise en œuvre d'une chaîne de portes quantiques sur un système de qubits couplés) est le fait que le calcul a lieu simultanément dans tous les mondes parallèles.
Et peu importe combien nous en avons, 2 ^ 3 ou 2 ^ 100, l' algorithme quantique sera exécuté en un temps fini sur tous ces mondes parallèles et nous donnera le résultat, qui est un échantillon de la distribution de probabilité des réponses de l'algorithme.
Pour une meilleure compréhension, nous pouvons imaginer qu'un ordinateur quantique à un niveau quantique démarre 2 ^ N processus de décision parallèles , chacun travaillant sur une option possible, puis recueille les résultats du travail - et nous donne la réponse sous la forme d'une superposition de la solution (distribution de probabilité des réponses), à partir de que nous échantillonnons une fois à chaque fois (dans chaque expérience).
Rappelez-vous le temps nécessaire à notre expérimentateur (150 μs) pour mener l'expérience, cela nous sera utile un peu plus loin lorsque nous parlerons des principaux problèmes des ordinateurs quantiques et du temps de décohérence.
Algorithmes quantiques
(au contenu)
Comme déjà mentionné, les algorithmes conventionnels basés sur la logique binaire ne sont pas applicables à un ordinateur quantique qui utilise la logique quantique (portes quantiques). Pour lui, il a dû en trouver de nouveaux qui exploitent pleinement le potentiel inhérent à la nature quantique de l'informatique.
Les algorithmes les plus connus aujourd'hui sont:
Contrairement aux ordinateurs classiques, les ordinateurs quantiques ne sont pas universels.
Jusqu'à présent, seul un petit nombre d'algorithmes quantiques ont été trouvés. (C)
Merci à oxoron pour le lien avec Quantum Algorithm Zoo , l'endroit où, selon l'auteur ( Stephen Jordan ), les meilleurs représentants du monde algorithmique quantique ont été rassemblés et continuent de se rassembler.
Dans cet article, nous n'analyserons pas les algorithmes quantiques en détail, il existe de nombreux excellents matériaux sur le Web pour tout niveau de complexité, mais vous devez toujours passer brièvement en revue les trois plus célèbres.
Algorithme de rivage.
(au contenu)
L'algorithme quantique le plus célèbre est l'algorithme Shor (inventé en 1994 par le mathématicien anglais Peter Shor ), qui vise à résoudre le problème de la décomposition des nombres en facteurs premiers (le problème de la factorisation, le logarithme discret).
Cet algorithme est cité en exemple lorsqu'ils écrivent que vos systèmes bancaires et vos mots de passe seront bientôt piratés. Considérant que la longueur des clés utilisées aujourd'hui n'est pas inférieure à 2048 bits, le temps de la casquette n'est pas encore venu.
À ce jour, les résultats sont plus que modestes. Les meilleurs résultats de factorisation utilisant l'algorithme Shore sont les nombres 15 et 21 , ce qui est bien inférieur à 2048 bits. Pour les résultats restants du tableau, un algorithme de calcul différent a été utilisé, mais même le meilleur résultat selon cet algorithme (291311) est loin d'être une application réelle.
Vous pouvez en savoir plus sur l'algorithme Shore, par exemple, ici . À propos de la mise en œuvre pratique - ici .
L'une des estimations actuelles de la complexité et de la puissance nécessaires pour factoriser un nombre de 2048 bits est un ordinateur avec 20 millions de qubits . Nous dormons paisiblement.
Algorithme de Grover
(au contenu)
L'algorithme de Grover est un algorithme quantique pour résoudre le problème de recherche, c'est-à-dire trouver une solution à l'équation F(X) = 1 , où F est une fonction booléenne de n variables. Il a été proposé par le mathématicien américain Lov Grover en 1996 .
L'algorithme de Grover peut être utilisé pour trouver la moyenne et la moyenne arithmétique d'une série de nombres. De plus, il peut être utilisé pour résoudre des problèmes NP-complets en recherchant de manière exhaustive parmi les nombreuses solutions possibles. Cela peut conduire à une augmentation significative de la vitesse par rapport aux algorithmes classiques, mais sans fournir une « solution polynomiale » en général . (C)
Vous pouvez en savoir plus ici ou ici . Il y a aussi une bonne explication de l'algorithme sur l'exemple des boîtes et du ballon, mais, malheureusement, pour des raisons indépendantes de ma volonté, ce site ne m'ouvre pas depuis la Russie. Si votre site est également bloqué, voici un bref aperçu:
Algorithme de Grover. Imaginez que vous avez N morceaux de boîtes fermées numérotées. Ils sont tous vides sauf celui dans lequel se trouve la balle. Votre tâche: connaître le numéro de la boîte dans laquelle se trouve la balle (ce nombre inconnu est souvent désigné par la lettre w).
Comment résoudre ce problème? , , . , ? N/2. , 100 , 100 , , .
. , , (Oracle). — « 732», « 732 ». , , « , »
, , , : N SQRT(N) !
.
-
( )
— ( — ) — [ ]( https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9 %D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC), 1992 , , . _
— , F(x1, x2, … xn) ( 0, 1 ) ( 0, 1). , , . ()
. :
( — ) , . , . : «» «» – , «», «» — . , , – . ()
( )
, . ( ) :
“ ”, .
:
( )
N+1 .
, , ( ) . , , — .
, (-273.14 ) - , () .
, , .
.
, . — IBM IBM Q System One Google Sycamore . , (2) 200 .
Sycamore, — 1 200 , — 130 . 150 . ? .
?
, 150 N — .
:
150 . — .
...
( )
, , 100% , - . , . :
, , , . , , . , , , .
— () , , , . — “ ?” — 5050, .
, ( ) - . . N 1 .
— . , 100 , 80 , 20.
— , . .
. , — IBM IBM Q System One Google Sycamore :
— . 1-Fidelity. , 2- .
2016 NQIT .
( )
, . () , , .
1- , , 12-, , , . , , , , .
, , , “ ” “” . .
:
, , . , , . - , .
:
( )
— . 150 :
, 0.5 , :
We measure a qubit coherence time in excess of 0.5 s, and with magnetic shielding we expect this to improve to be longer than 1000 s
, , .
, , , .
, , , 1 4 1 6.
( )
, :
, , ( ) , . ( ), , .
D-Wave
( )
2000- D-Wave 2000Q. : D-Wave Systems
Google 53- , D-Wave, , . , 53 , 2048 ? ...
( ):
D-Wave ( ), , .
, , , (, ), Scott Aaronson . , ,
D-Wave. , 2014 IBM , D-Wave . , 2015 Google NASA , , , . Google , , .
, D-Wave, . , . , — . , D-Wave ASIC .
( )
. , :
- , 232 264 (8-16 )
- N 2^N , .. 2^(3+N) 32- 2^(4+N) 64- .
- N 2^N x 2^N
:
()
, Summit ( Top-1 Top-500 ) 2.8 .
— 49 ( Sunway Taihu Light )
.
. :
— 49 - 39 "" ( ) 2^63 — 4 4
50+ . - Google 53- .
.
( )
:
́ ́ — , .
, , , , , . .
, “ ”. , 50+ , , , . .
, . , Google, Sycamore .
Google
( )
54- Sycamore
, 2019 Google Nature « ». 54- «Sycamore».
Sycamore 54- , 53-. , , 54- , . , 53- .
, .
IBM , Google . , 2,5 , , . .
, , Scott Aaronson . Scott's Supreme Quantum Supremacy FAQ! , . FAQ, , , .
Google? , :
, , , . : (.. 1- 2- — — , 20, 2D n=50-60 ). , 0, {0,1}, n- () . , , .
:
Google 53- , .
— Google , , , , , . , 2048- .
Résumé
( )
— , .
(-) :
:
:
:
( ), , - , .
— , , . .
Conclusion
( )
, , , , D-Wave Google .
(, , ..) , , , , .. , .
, - .
() Kruegger
( )
@Oxoron , “ ”
@a5b - “ ” , , .
, .
( )
[The National Academies Press]