Ordinateur quantique

Sujets connexes: mat??riel informatique et de l'infrastructure

Saviez-vous ...

SOS croit que l'??ducation donne une meilleure chance dans la vie des enfants dans le monde en d??veloppement aussi. Parrainer un enfant de faire une r??elle diff??rence.

Le Sph??re de Bloch est une repr??sentation d'un qubit, le bloc de construction fondamental des ordinateurs quantiques.

Un ordinateur quantique est un dispositif de calcul qui fait appel directement distinctement m??canique quantique ph??nom??nes, tels que et superposition enchev??trement, d'effectuer des op??rations sur les donn??es. Dans un ordinateur classique (ou traditionnel), l'information est stock??e sous la forme bits; dans un ordinateur quantique, il est stock?? en tant que qubits (qu antum ts digi naires bi). Le principe de base de calcul quantique est que les propri??t??s quantiques peuvent ??tre utilis??s pour repr??senter et la structure des donn??es, et que les m??canismes quantiques peuvent ??tre con??us et construits pour effectuer op??rations avec ces donn??es.

Bien que l'informatique quantique est encore ?? ses balbutiements, des exp??riences ont ??t?? men??es dans lesquelles les op??rations de calcul quantiques ont ??t?? ex??cut??s sur un tr??s petit nombre de qubits. Tant la recherche th??orique et pratique continue avec int??r??t, et de nombreux organismes gouvernementaux nationaux et de financement militaire soutenir la recherche sur l'informatique quantique pour d??velopper des ordinateurs quantiques pour des fins civiles et de s??curit?? nationale, tels que cryptanalyse.

Si les ordinateurs quantiques ?? grande ??chelle peuvent ??tre construits, ils seront en mesure de r??soudre certains probl??mes beaucoup plus rapidement que ne importe quel de nos ordinateurs classiques actuelles (par exemple L'algorithme de Shor). Les ordinateurs quantiques sont diff??rents des autres ordinateurs tels que ordinateurs d'ADN et les ordinateurs traditionnels bas??s sur transistors. Certaines architectures informatiques tels que ordinateurs optiques peuvent utiliser superposition classique des ondes ??lectromagn??tiques. Sans certains moyens m??caniques tels que sp??cifiquement quantiques enchev??trement, il est suppos?? qu'un avantage exponentielle au cours ordinateurs classiques ne est pas possible.

Base

Un ordinateur classique dispose d'une m??moire compos??e de bits, o?? chaque bit d??tient un navigateur ou un z??ro. Un ordinateur quantique maintient une s??quence de qubits. Un seul qubit peut contenir un, z??ro, ou, surtout, un superposition quantique de ces; en outre, une paire de qubits peut ??tre dans une superposition quantique de quatre ??tats et trois qubits dans une superposition de 8. En g??n??ral, un ordinateur quantique ?? n qubits peut ??tre jusqu'?? $2 ^ n$ diff??rents ??tats simultan??ment (ce qui se compare ?? un ordinateur normal qui ne peut ??tre dans un de ces $2 ^ n$ indique ?? un moment donn??). Un ordinateur quantique fonctionne en manipulant ces qubits avec une s??quence fixe de portes logiques quantiques. La s??quence des portes ?? appliquer est appel?? un algorithme quantique.

Un exemple de mise en oeuvre de qubits pour un ordinateur quantique pourrait commencer par l'utilisation de particules ?? deux tourner ??tats: ??haut?? et ??bas?? (g??n??ralement ??crite $| {\ Uparrow} \ rangle$ et $| {\ Downarrow} \ rangle$ Ou $| 0 \ rangle$ et $| 1 \ rangle$ ). Mais en fait, tout syst??me poss??dant une Une quantit?? observable qui est conserv??e sous ??volution dans le temps de telle sorte qu'une et comporte au moins deux cons??cutifs discrets et espac??s suffisamment valeurs propres , est un candidat appropri?? pour la mise en oeuvre d'un qubit. Ceci est vrai parce que un tel syst??me peut ??tre mis en correspondance avec une efficacit?? spin-moiti?? syst??me.

Bits contre Qubits

Qubits sont constitu??s de particules contr??l??es et les moyens de contr??le (par exemple des dispositifs qui pi??ger les particules et de les passer d'un ??tat ?? un autre).

Consid??rons d'abord un ordinateur classique qui fonctionne sur trois bits inscrivez-vous. L'??tat de l'ordinateur ?? tout moment est une distribution de probabilit?? sur la $2 ^ 3 = 8$ diff??rentes cha??nes trois bits 000, 001, ..., 111-ainsi qu'il est d??crit par huit nombres non n??gatifs (a, b, c, d, e, f, g, h) jusqu'?? une -Ajout.

L'??tat d'un ordinateur quantique trois qubits est d??crit par un vecteur similaire huit dimensions (a, b, c, d, e, f, g, h), appel??e fonction d'onde. Cependant, au lieu d'ajouter ?? un, la somme des carr??s des magnitudes de coefficients, $| A | ^ 2 + | b | ^ 2 + ... + | h | ^ 2$ , Doit ??tre ??gal ?? un. De plus, les coefficients sont des nombres complexes qui ne doivent pas ??tre une valeur positive. Le fait que les coefficients peuvent ??tre n??gatifs aussi bien que positifs permet aux fins d'annulation, ou interf??rences, entre les diff??rents chemins de calcul, et est une diff??rence essentielle entre l'informatique quantique et probabiliste informatique classique.

Si vous mesurez les trois qubits, alors vous pourrez observer une cha??ne de trois bits. La probabilit?? de mesurer une cha??ne sera ??gal ?? l'ampleur carr?? des coefficients de cette cha??ne. Ainsi, une mesure de l'??tat quantique avec des coefficients (a, b, ..., h) donne la distribution de probabilit?? classique $(| A | ^ 2, | b | ^ 2, ..., | h | ^ 2)$ . Nous disons que l'??tat quantique "se effondre" ?? un ??tat classique.

Notez qu'un vecteur huit dimensions peut ??tre sp??cifi??e de diff??rentes fa??ons, en fonction de ce que base que vous choisissez pour l'espace. La base de cha??nes de trois bits 000, 001, ..., 111 est connu comme base de calcul, et est souvent commode, mais d'autres bases de unit?? de longueur, vecteurs orthogonaux peuvent ??galement ??tre utilis??s. Ket notation est souvent utilis??e pour rendre explicite le choix de la base. Par exemple, l'??tat (a, b, c, d, e, f, g, h) dans la base de calcul peut se ??crire $un \, | 000 \ rangle + b \, | 001 \ rangle + c \, | 010 \ rangle + d \, | 011 \ rangle + e \, | 100 \ rangle + f \, | 101 \ rangle + g \ , | 110 \ rangle + h \, | 111 \ rangle$ , O??, par exemple, $| 010 \ rangle$ = (0,0,1,0,0,0,0,0). La base de calcul pour un seul qubit (deux dimensions) est $| 0 \ rangle$ = (1,0), $| 1 \ rangle$ = (0,1), mais une autre base commune est la base de Hadamard $| + \ Rangle = \ left (\ frac {1} {\ sqrt {2}}, \ frac {1} {\ sqrt {2}} \ right)$ et $| - \ Rangle = \ left (\ frac {1} {\ sqrt {2}}, - \ frac {1} {\ sqrt {2}} \ right)$ .

Notez que bien que l'enregistrement d'un ??tat classique de n bits, une distribution de probabilit?? de dimension ⁿ 2, n??cessite un nombre exponentiel de nombres r??els, nous pouvons pratiquement toujours penser le syst??me comme ??tant exactement un des n bits cordes-nous don juste " sais lequel. Quantiquement, ce ne est plus le cas, et tous les deux coefficients ⁿ complexes doivent ??tre gard?? la trace de voir comment le syst??me quantique ??volue. Par exemple, un ordinateur quantique 300 qubit poss??de un ??tat d??crit par 2 ³⁰⁰ (environ 10 ⁹⁰⁾ nombres complexes, plus que le nombre d'atomes dans l' univers observable .

Op??ration

Alors que l'??tat de trois bits classique et un ??tat de trois qubit quantique sont ?? la fois huit dimensions vecteurs, ils sont manipul??s tr??s diff??remment pour le calcul classique ou quantique, respectivement. Pour l'informatique dans les deux cas, le syst??me doit ??tre initialis??, par exemple dans la cha??ne tout-z??ros, ce est ?? dire, (1,0,0,0,0,0,0,0) ou $| 000 \ rangle$ . Dans le calcul al??atoire classique, le syst??me ??volue en fonction de l'application de matrices stochastiques, qui pr??servent que les probabilit??s se ajoutent ?? une (ce est ?? dire, de pr??server la L1 norme). Dans le calcul quantique, d'autre part, sont autoris??s op??rations matrices unitaires, qui sont efficacement rotations (ils conservent que la somme des carr??s ajouter jusqu'?? une, la Euclidienne ou norme L2). (Exactement ce unitaries peuvent ??tre appliqu??s d??pendent de la physique du dispositif quantique.) Par cons??quent, puisque les rotations peuvent ??tre annul??es par la rotation vers l'arri??re, des calculs quantiques sont r??versible. (Techniquement, les op??rations quantique peut ??tre des combinaisons probabilistes de unitaries, afin calcul quantique a vraiment g??n??raliser le calcul classique. Voir circuit quantique pour une formulation plus pr??cise.)

Enfin, ?? la fin de l'algorithme, le r??sultat doit ??tre lu ??teint. Dans le cas d'un ordinateur classique, nous ??chantillon de la distribution de probabilit?? sur le registre de trois bits pour obtenir une certaine cha??ne de trois bits, 000 quantiquement dire, nous mesurer l'??tat de trois qubit, ce qui ??quivaut ?? l'effondrement de l'??tat quantique vers le bas pour une distribution classique (avec les coefficients dans l'??tat classique ??tant les grandeurs au carr?? des coefficients pour l'??tat quantique, comme d??crit ci-dessus), suivi par un ??chantillonnage de cette distribution . Notez que cela d??truit l'??tat quantique d'origine. De nombreux algorithmes seront seulement donner la r??ponse correcte avec une certaine probabilit??, cependant en initialisant ?? plusieurs reprises, la course et la mesure de l'ordinateur quantique, la probabilit?? d'obtenir la r??ponse correcte peut ??tre augment??e. Par exemple, l'ex??cution de l'algorithme de Shor factorisation quatre fois donnera la bonne r??ponse avec une tr??s forte probabilit??.

Pour plus de d??tails sur les s??quences d'op??rations utilis??es pour diff??rents algorithmes, voir ordinateur quantique universel, L'algorithme de Shor, Algorithme de Grover, Algorithme Deutsch-Jozsa, transform??e de Fourier quantique, porte quantique, algorithme quantique adiabatique et correction d'erreur quantique.

Potentiel

Factorisation entier est consid??r?? comme math??matiquement impossible avec un ordinateur ordinaire pour les grands entiers qui sont le produit de seulement quelques nombres premiers (par exemple, les produits de deux nombres premiers de 300 chiffres). Par comparaison, un ordinateur quantique pourrait r??soudre efficacement ce probl??me en utilisant L'algorithme de Shor pour trouver ses facteurs. Cette capacit?? permettrait ?? un ordinateur quantique ?? "casser" la plupart des cryptographiques syst??mes en usage aujourd'hui, dans le sens o?? il y aurait une temps polynomial (en nombre de bits de l'entier) algorithme pour r??soudre le probl??me. En particulier, la plupart de la populaire chiffres cl??s publiques sont bas??es sur la difficult?? d'entiers d'affacturage (ou connexes probl??me du logarithme discret qui peut ??galement ??tre r??solu par l'algorithme de Shor), y compris les formes de RSA. Ils sont utilis??s pour prot??ger des pages Web s??curis??es, e-mail crypt??, et de nombreux autres types de donn??es. Briser ce serait avoir des ramifications importantes pour la vie priv??e et de la s??curit?? ??lectronique. La seule fa??on d'accro??tre la s??curit?? d'un algorithme comme RSA serait d'augmenter la taille de cl?? et nous esp??rons que l'adversaire n'a pas les ressources pour construire et utiliser un ordinateur assez puissant quantique.

Un moyen de sortir de ce dilemme serait d'utiliser une sorte de la cryptographie quantique. Il ya aussi quelques syst??mes de signature num??rique que l'on croit ?? la protection contre les ordinateurs quantiques. Voir, par exemple Signatures Lamport.

Cet avantage spectaculaire des ordinateurs quantiques n'a ??t?? d??couvert pour la factorisation et discrets logarithmes jusqu'ici. Cependant, il ne existe aucune preuve que l'avantage est r??el: un algorithme classique aussi rapide peut encore ??tre d??couvert. Il ya un autre probl??me o?? les ordinateurs quantiques ont une, mais significative (quadratique) avantage plus petit. Ce est la recherche de base de donn??es quantique, et peut ??tre r??solu par Algorithme de Grover. Dans ce cas, l'avantage est prouvable. Ceci ??tablit hors de tout doute que (id??ales) ordinateurs quantiques sont sup??rieurs aux ordinateurs classiques pendant au moins un probl??me.

Consid??rons un probl??me qui a ces quatre propri??t??s:

La seule fa??on de le r??soudre est de deviner les r??ponses ?? plusieurs reprises et de les v??rifier,
Il ya des r??ponses n possibles ?? v??rifier,
Chaque r??ponse possible prend la m??me quantit?? de temps pour v??rifier, et
Il n'y a pas des indices sur les r??ponses pourraient ??tre mieux: g??n??rer au hasard des possibilit??s est aussi bon que de les v??rifier dans un ordre sp??cial.

Un exemple de ceci est un Password Cracker qui tente de deviner le mot de passe pour un fichier crypt?? (en supposant que le mot de passe a une longueur maximale possible).

Pour les probl??mes avec les quatre propri??t??s, le temps d'un ordinateur quantique pour r??soudre ce sera proportionnelle ?? la racine carr??e de n (il faudrait une moyenne de (n + 1) / 2 conjectures pour trouver la r??ponse ?? l'aide d'un ordinateur classique.) Cela peut ??tre une tr??s grande acc??l??ration, la r??duction de certains probl??mes des ann??es ?? quelques secondes. Il peut ??tre utilis?? pour attaquer algorithmes de chiffrement sym??triques telles que Triple DES et AES en tentant de deviner la cl?? secr??te. Peu importe si l'un de ces probl??mes peuvent ??tre montr?? pour avoir un avantage sur un ordinateur quantique, ils seront n??anmoins toujours avoir l'avantage d'??tre un excellent outil pour ??tudier les interactions m??caniques quantiques, qui elle-m??me est une valeur ??norme ?? la communaut?? scientifique.

Algorithme de Grover peut ??galement ??tre utilis?? pour obtenir une acc??l??ration quadratique [sur une Recherche exhaustive] pour une classe de probl??mes connus que NP-complet.

Probl??mes

Il ya un certain nombre de difficult??s pratiques dans la construction d'un ordinateur quantique, et ?? ce jour les ordinateurs quantiques ne ont r??solu des probl??mes triviaux. David DiVincenzo, d'IBM, a ??num??r?? les exigences suivantes pour un ordinateur quantique pratique:

adaptent physiquement ?? augmenter le nombre de qubits
qubits peuvent ??tre initialis??es ?? des valeurs arbitraires
portes quantiques plus vite que temps de d??coh??rence
universelle porte jeu
qubits peuvent ??tre lus facilement

Pour r??sumer les probl??mes du point de vue d'un ing??nieur, il faut r??soudre le d??fi de construire un syst??me qui est isol?? de tout, sauf le m??canisme de mesure et la manipulation. De plus, il faut ??tre en mesure de d??sactiver le couplage des qubits de la mesure afin de ne pas perdre sa coh??rence des qubits tout en effectuant des op??rations sur eux.

D??coh??rence quantique

Un probl??me majeur est de garder les composants de l'ordinateur dans un ??tat coh??rent, que la moindre interaction avec le monde ext??rieur serait de rendre le syst??me perdre sa coh??rence. Cet effet provoque le caract??re unitaire (et plus sp??cifiquement, la inversibilit??) des ??tapes de calcul quantique ?? ??tre viol??. temps de d??coh??rence pour les syst??mes de candidats, en particulier le temps de relaxation transversale T ₂ (terminologie utilis??e dans RMN et La technologie IRM, aussi appel?? le temps de d??phasage), typiquement varient entre nanosecondes et secondes ?? basse temp??rature. La question des approches optiques sont plus difficiles que ces d??lais sont des ordres de grandeur plus faible et une approche souvent cit?? pour surmonter il utilise une approche optique de mise en forme d'impulsion. Les taux d'erreur sont g??n??ralement proportionnelle au rapport du temps de fonctionnement en temps de d??coh??rence, d'o?? toute op??ration doit ??tre termin??e beaucoup plus rapidement que le temps de d??coh??rence.

Si le taux d'erreurs est assez petit, il est consid??r?? comme possible d'utiliser une correction d'erreur quantique, qui corrige les erreurs dues ?? d??coh??sion, ce qui permet ainsi le temps de calcul total ?? ??tre plus long que le temps de d??coh??sion. Un chiffre souvent cit?? (mais plut??t arbitraire) pour le taux d'erreur requis dans chaque porte est de 10 ^-4. Cela implique que chaque porte doit ??tre en mesure d'accomplir sa t??che 10000 fois plus rapide que le temps de d??coh??rence du syst??me.

Remplir cette condition d'??volutivit?? est possible pour un large ??ventail de syst??mes. Cependant, l'utilisation d'une correction d'erreur se accompagne du co??t d'un nombre consid??rablement accru de qubits requises. Le nombre n??cessaire de prendre en compte des nombres entiers en utilisant l'algorithme de Shor est encore polyn??me, et consid??r?? comme entre L et L ^2, o?? L est le nombre de bits dans le num??ro ?? ??tre pris en compte; algorithmes de correction d'erreur seraient gonfler ce chiffre par un facteur suppl??mentaire de L. Pour un nombre de 1000 bits, ce qui implique une n??cessit?? environ 10 ⁴ qubits sans correction d'erreurs. Avec la correction d'erreur, le chiffre se ??l??verait ?? environ 10 ⁷ qubits. Notez que le temps de calcul est d'environ $L ^ 2$ soit environ $10 ^ 7$ et ceux des ??tapes 1 M Hz, environ 10 secondes.

Une approche tr??s diff??rente du probl??me stabilit?? d??coh??rence est de cr??er un ordinateur quantique topologique avec anyons, des quasi-particules utilis??es en tant que fils et se appuyant sur Tresse pour former portes logiques stables.

Les candidats

Il ya un certain nombre de candidats de l'informatique quantique, parmi ceux:

Superconductor ?? base ordinateurs quantiques (y compris SQUID Les ordinateurs quantiques)
Ion pi??g?? ordinateur quantique
Les r??seaux optiques
Ordinateur quantique topologique
Quantum point sur surface (par exemple, le Perte de-DiVincenzo ordinateur quantique)
R??sonance magn??tique nucl??aire sur des mol??cules en solution (RMN liquide)
RMN du solide Ordinateurs quantiques Kane
Les ??lectrons sur l'h??lium ordinateurs quantiques
L'??lectrodynamique quantique en cavit?? (CQED)
Aimant mol??culaire
Base de fuller??ne- ESR ordinateur quantique
Ordinateurs quantiques ?? base optique (- Optique quantique)
Ordinateur quantique ?? base de diamant
Condensat de Bose-Einstein ?? base ordinateur quantique
Cordes ordinateurs quantiques avec l'entra??nement de trous positifs en utilisant un pi??ge ??lectrostatique - ordinateur quantique Transistor-
Base Spin-ordinateur quantique
Calcul quantique adiabatique

Le grand nombre de candidats montre explicitement que le sujet, en d??pit des progr??s rapides, est encore ?? ses balbutiements. Mais en m??me temps, il existe ??galement une grande flexibilit??.

En 2005, des chercheurs de la Universit?? du Michigan a construit une puce semi-conductrice qui a fonctionn?? comme un Ion Trap. De tels dispositifs, produits par la norme techniques de lithographie, peuvent ouvrir la voie ?? ??volutive des outils de l'informatique quantique. Une version am??lior??e a ??t?? faite en 2006.

L'informatique quantique dans la th??orie de la complexit?? algorithmique

La relation soup??onn?? d'BQP ?? d'autres espaces de probl??mes.

Cette section recense ce qui est actuellement connu math??matiquement ?? propos de la puissance des ordinateurs quantiques. Il d??crit les r??sultats connus de th??orie de la complexit?? de calcul et la th??orie de calcul traitant avec des ordinateurs quantiques.

La classe de probl??mes qui peuvent ??tre efficacement r??solu par les ordinateurs quantiques est appel?? BQP, pour "erreur born??e, quantique, temps polynomial". Les ordinateurs quantiques ne fonctionnent algorithmes probabilistes, afin BQP sur les ordinateurs quantiques est la contrepartie de BPP sur les ordinateurs classiques. Il est d??fini comme l'ensemble des probl??mes solubles avec un algorithme polynomial, dont la probabilit?? d'erreur est born??e loin de quart. Un ordinateur quantique est dit de ??r??soudre?? un probl??me si, pour chaque instance, sa r??ponse sera juste avec une forte probabilit??. Si cette solution fonctionne en temps polynomial, alors ce probl??me est dans BQP.

BQP est contenue dans la classe de complexit?? #P (Ou plus pr??cis??ment dans la classe associ??e de d??cision probl??mes ^#P P), qui est une sous-classe de PSPACE.

BQP est soup??onn?? d'??tre disjointe de NP-complet et un sur-ensemble strict de P, mais ce ne est pas connue. Les deux factorisation entier et logarithme discret sont en BQP. Ces deux probl??mes sont des probl??mes NP soup??onn??s d'??tre ?? l'ext??rieur BPP, et donc en dehors P. Les deux sont soup??onn??s de ne pas ??tre NP-complet. Il ya une id??e fausse tr??s r??pandue que les ordinateurs quantiques peuvent r??soudre des probl??mes NP-complets en temps polynomiale. Ce ne est pas connue pour ??tre vrai, et est g??n??ralement soup??onn??s d'??tre faux.

portes quantiques peuvent ??tre consid??r??s comme transformations lin??aires. Daniel S. Abrams et Seth Lloyd ont montr?? que si des transformations non lin??aires sont autoris??s, alors les probl??mes NP-complets pourraient ??tre r??solus en temps polynomial. Il pourrait m??me le faire pour Probl??mes # P-complets. Ils ne croient pas qu'une telle machine est possible.

Bien que les ordinateurs quantiques peuvent ??tre plus rapides que les ordinateurs classiques, ceux d??crits ci-dessus ne peuvent pas r??soudre tous les probl??mes que les ordinateurs classiques ne peuvent pas r??soudre, assez de temps et de la m??moire donn??e (quoique peut-??tre un montant qui ne pourrait jamais ??tre pratiquement exerc??e). Un Machine de Turing peut simuler ces ordinateurs quantiques, si un tel ordinateur quantique pourrait jamais r??soudre un probl??me ind??cidable comme le probl??me de l'arr??t. L'existence d'ordinateurs quantiques "standard" ne r??fute pas la Th??se de Church-Turing.

R??cup??r?? ?? partir de " http://en.wikipedia.org/w/index.php?title=Quantum_computer&oldid=227805628 "