Ordinateur quantique

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'à différents états simultanément (ce qui se compare à un ordinateur normal qui ne peut être dans un de ces 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 et Ou et ). 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 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, , 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 . 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 , Où, par exemple, = (0,0,1,0,0,0,0,0). La base de calcul pour un seul qubit (deux dimensions) est = (1,0), = (0,1), mais une autre base commune est la base de Hadamard et .

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 . 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:

1. La seule façon de le résoudre est de deviner les réponses à plusieurs reprises et de les vérifier,
2. Il ya des réponses n possibles à vérifier,
3. Chaque réponse possible prend la même quantité de temps pour vérifier, et
4. 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 soit environ 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:

1. Superconductor à base ordinateurs quantiques (y compris SQUID Les ordinateurs quantiques)
2. Ion piégé ordinateur quantique
3. Les réseaux optiques
4. Ordinateur quantique topologique
5. Quantum point sur surface (par exemple, le Perte de-DiVincenzo ordinateur quantique)
6. Résonance magnétique nucléaire sur des molécules en solution (RMN liquide)
7. RMN du solide Ordinateurs quantiques Kane
8. Les électrons sur l'hélium ordinateurs quantiques
9. L'électrodynamique quantique en cavité (CQED)
10. Aimant moléculaire
11. Base de fullerène- ESR ordinateur quantique
12. Ordinateurs quantiques à base optique (- Optique quantique)
13. Ordinateur quantique à base de diamant
14. Condensat de Bose-Einstein à base ordinateur quantique
15. Cordes ordinateurs quantiques avec l'entraînement de trous positifs en utilisant un piège électrostatique - ordinateur quantique Transistor-
16. Base Spin-ordinateur quantique
17. 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.