La mise en œuvre physique de l'algorithme de recuit quantique

Question

De cette question sur les différences entre le recuit quantique et le recuit simulé, nous avons trouvé (dans commets à répondre) que la mise en œuvre physique de recuit quantique est exists (ordinateurs quantiques D-Wave).

Quelqu'un peut-il expliquer cet algorithme en termes de portes quantiques et les algorithmes quantiques, ou en termes physiques (une partie de l'algorithme qui dépend du matériel quantique)?

Est-ce que quelqu'un a des idées à ce sujet? S'il vous plaît dites-moi, si vous connaissez des liens liés à cette question.

Answer 1

De [FT11] (italique ajouté):

recuit Quantum (QA) est classique algorithme aléatoire ... suggéré par le comportement des systèmes quantiques.

Ainsi, il n'y a pas de partie AQ qui nécessairement « dépend du matériel quantique. »

Dans le recuit classique (CA), un analogue terme température est la source des perturbations aléatoires qui permettent à l'algorithme d'explorer l'espace de solution d'un problème. En AQ, le terme de température est remplacé par un analogue terme force de champ à effet tunnel quantique . On peut supposer que, dans une mise en œuvre quantique de l'AQ, les étapes impliquant tunnel quantique seraient effectuées directement dans le matériel.

comparaison A des deux techniques sont disponibles , et l'explication de D-Wave ici .

EDIT: à partir de documentation fonctionnement du processeur de D-Wave (italique ajouté): Qu'il y ait un problème d'optimisation de la forme

$ E (\ VEC {s}) = - \ sum \ limits_ih_is_i + \ sum \ limits_ {i, j> i} {K_ ij} s_is_j $

où $ -1 \ leq h_i $, $ K_ {} ij \ leq + 1 $ et $ S_I = \ PM1 $. Il existe une solution $ \ vec {s} _ {gs} $ qui réduit l'objectif $ E $. Plan du problème sur un verre de spin quantique Ising (QSG) hamiltonien

$ \ frac {\ mathcal {H} _ {QSG} (t)} {E_0 (t)} = - \ sum \ limits_ih_i \ sigma_z ^ {(i)} + \ sum \ limits_ {i, j> i} {K_ ij} \ sigma_z ^ {(i)} \ sigma_z ^ {(j)} - \ Gamma (t) \ sum \ limits_i \ sigma_x ^ {(i)} $

Utilisez un système physique pour trouver le $ | \ vec {{S_ gs}} \ rangle $ en évoluant $ \ Gamma (t) $ tel que

$ \ Gamma (0) \ ll h_i, K_ {ij} $

$ \ Gamma (t_f) \ gg h_i, K_ {ij} $

Answer 2

L'approche de l'informatique quantique que vous faites référence à quelque chose appelé le modèle adiabatique. Il est en fait basé sur l'évolution temporelle continue des systèmes quantiques, plutôt que sur les modèles en temps discrétisation (à savoir pas de barrière). Il se trouve qu'il est possible de rapprocher l'évolution du temps continu avec un ensemble discret de portes, et donc l'algorithme peut être mis en œuvre dans un modèle universel de calcul quantique.

Pour comprendre l'algorithme et comment cela fonctionne, vous devez savoir de la physique. A hamiltonien, $ H $, est une observable qui correspond à l'énergie totale du système. Toute état propre, $ \ psi $, de $ H $ correspond à une configuration du système pour lequel il y a une énergie définie, $ E $, égale à la valeur propre correspondant de $ H $.

La dynamique d'un système quantique sont déterminées par son hamiltonien, et pour un hamiltonien fixe, l'évolution est donnée par $ \ psi (t) = e ^. {- IHT / \ HBAR} \ psi (0) $

L'algorithme adiabatiques est basé sur le théorème adiabatique, qui grosso modo, déclare que si vous commencez à l'état fondamental (le plus bas niveau d'énergie du système) de quelque hamiltonien $ H_0 $ et changer lentement l'hamiltonien en fonction de temps, alors vous continuerez à rester dans l'état du sol (ou plutôt très proche) de l'hamiltonien instantanée, à condition que la vitesse à laquelle les changements hamiltonien est suffisamment lente. Comment ralentir cela doit être dépend de l'écart minimum entre l'état du sol et le prochain niveau le plus bas de l'énergie, et varie d'un hamiltonien à l'autre.

L'algorithme adiabatiques est simplement de commencer dans l'état fondamental de quelques simples hamiltonien, $ H_0 $, pour lequel l'état du sol est facile à préparer, et lentement interpoler entre elle et une cible hamiltonien, H_1 $ $, qui encode en son état fondamental de la solution au problème que vous essayez de résoudre. Ainsi, le temps variable hamiltonien peut ressembler à quelque chose comme $ H (t) = (1-T / T) H_0 + (t / T) H_1 $, où $ T $ est le temps total pour l'évolution adiabatique. Tant que $ T $ est suffisamment grande, les garanties de théorème adiabatique que l'état résultant au moment de $ T $ sera très proche de l'état fondamental de H_1 $ $.

Il convient de noter que l'interpolation linéaire ci-dessus est certainement pas le choix que possible, et à la recherche en effet de meilleurs chemins entre $ H_0 $ et H_1 $ est un domaine de recherche actif, puisque le chemin détermine la valeur minimale qui peut être prise par $ T $. Néanmoins, l'devrait vous donner un avant-goût au-dessus de la façon dont fonctionne l'algorithme.

Answer 3

Ceci est une réponse que j'ai donné à la question de ce que l'informatique quantique en adiabatiques termes simples sur Quora. Juste pour vous mettre en garde, il est un peu simpliste et bavard. Voici le lien: https: //www.quora.com/Quantum-Computation/How-does-adiabatic-quantum-computation-work-in-laymans-terms/answer/Hadayat-Seddiqi

quantique adiabatique calcul (AQC, désormais) est un paradigme fondamentalement différent du circuit quantique ou d'un modèle de grille que la plupart des chercheurs travaillent. Je pardonnerai les détails de ce dernier et vous référer à des questions telles que:

https://www.quora.com/Quantum-Computation/How-does -quantum computing travail

Mais je ferai remarquer qu'il a été mathématiquement démontré que le modèle adiabatique et le modèle de porte sont équivalentes, de sorte qu'il est possible de trouver un algorithme équivalent qui peut être exécuté sur un type de machine pour l'autre, bien qu'il y ait aucune garantie sur l'efficacité. C'est important de noter. Quelqu'un peut trouver la version adiabatique de l'algorithme de Shor, mais il est probable que ce ne sera pas battu même des méthodes de calcul classiques.

Dans le modèle adiabatiques, vous avez quelques choses importantes qui vont, et ils sont décrits ci-dessous:

-encode votre problème (en termes d'un problème SAT Boolean) -Préparer état initial de qubits (programmer votre problème) Procédé -Annealing (change lentement initial à l'état final) -Mesurer le système pour obtenir votre réponse

En regardant cette façon, le calcul de l'aide d'un AQC semble très simple.

Encoding le problème Au début, vous aurez besoin de traduire votre problème en un que l'AQC peut gérer. En général, ce sera sous la forme d'un problème sat. Cela aura une forme spécifique en termes de notation mathématique, mais l'idée principale derrière c'est que vous aurez un problème d'optimisation que vous devez trouver le minimum ou maximum. Il y aura aussi beaucoup de contraintes. Pensez en termes d'un graphique. Vous avez une collection de noeuds dans une grille, et ils sont tous connectés au premier abord. Ce graphique est analogue au « programme » dans un AQC, où l'état initial de qubits sont reliées d'une certaine manière.

État initial Pour tout QC, vous avez besoin d'un état initial. Dans le calcul classique, ils sont des bits, en informatique quantique ils sont qubits. Je vous renvoie à nouveau à la question plus large de la façon dont fonctionne QC ci-dessus pour comprendre comment qubits et QC dans le travail général.

Dans AQC, les qubits ont une certaine connectivité. Par exemple, si vos qubits sont la direction du champ magnétique (soit vers le haut ou vers le bas selon que le courant passe dans le sens horaire ou antihoraire autour, mais à cause de la jonction Josephson il sera superposition des deux) dans la boucle d'un dispositif de les interférences quantique supraconducteur (SQUID), alors vous avez des fils supraconducteurs reliant ces SQUID. Ces fils peuvent être « éteints » au besoin pour coder le problème initial sur l'appareil.

C'est ce qu'un rf-SQUID avec une apparence de jonction Josephson comme:

Voici un autre diagramme du blog de D-Wave. Le montre la figure à droite de la connectivité dans leur propre machine.

Quelque chose d'important à noter ici est que le système de D-Wave est pas entièrement connecté, que vous pouvez voir que les noeuds 1,2,3 et 4 ne sont pas reliés entre eux. Cela signifie que leur machine est un sous-ensemble d'un AQC théorique plus puissant, mais en raison de contraintes expérimentales qu'ils ont fait avec l'architecture affichées.

Processus Recuit Maintenant, c'est là que le calcul se fait. Je suis venu avec ce que je pense est une analogie correcte, donc voir si cela fait sens pour vous.

Imaginez que vous mettez un bloc de glace dans une tasse, et vous augmentez la chaleur pour faire fondre. Votre but est de faire la glace fondre le plus lentement possible, de sorte que lorsque vous avez votre tasse d'eau, vous avez absolument zéro vibrations ou vagues. Vous pouvez imaginer que, par une méthode de chauffage super que si le cube de glace devait tourner instantanément dans l'eau, il y aurait des vagues aller partout, car l'eau serait de se précipiter sur les parois de la coupe. Ce que vous voulez faire est de chauffer lentement pour que cela ne se passe, pas même dans le moindre. Votre tolérance est, disons, 99%. Si votre cube de glace est un AQC, les vibrations dans l'état final (l'eau) sont « » excitations, qui essentiellement des erreurs moyennes et, par conséquent, vous donnant de mauvaises réponses. Ils peuvent être proches, mais ils ne seraient pas optimales.

Vous avez donc ce système de qubits connectés sous forme SQUID est que vous préparez ce système avec un champ magnétique qui va d'une certaine façon. Vous vous tournez lentement votre état initial tout en tournant lentement sur votre état final. Donc, fondamentalement, vous allez dans un état mixte d'énergie initiale et finale, mais à la fin il y aura des parties essentiellement initiales pas du problème laissé dans l'état et vous êtes à gauche que l'état final. Une autre façon est de commencer par les deux États sur, mais ont l'état initial soit beaucoup, beaucoup plus forte que la dernière partie de l'état, puis tournez lentement le très grand état initial. Si vous trouvez cette confusion, jetez un oeil à cette équation

H représente hamiltonien, qui est juste un nom pour une matrice qui définit l'état de l'énergie totale du système. Les trois termes, vous remarquerez, peuvent être regroupés en deux termes vraiment. Le grand Z et X font référence aux matrices de spin. Donc, en termes de cette équation, votre état initial est régi par le dernier terme, et votre état final est régie par les deux premiers termes. Les matrices de spin montrent le passage de l'état de base X à l'état Z-base. Lorsque vous préparez votre système initial de qubits, on les met tous dans l'état de spin X puis hybrident à l'état Z-spin. Imaginez que h et J sont beaucoup, beaucoup plus petit que K initialement. Lorsque vous hybrident, vous tournez lentement K de sorte que lorsque vous avez terminé, vous êtes seulement à gauche avec tout ce qui est dans les deux premiers termes. Voici comment le processus de recuit fonctionne. Vous pouvez penser à un complot qui ressemble à un X symétrique; une croix de la X représente les coefficients K diminuant de façon linéaire, et l'autre aile est croissant linéairement h et coefficients J.

Maintenant, pour recuire correctement de sorte que vous obtenez la bonne réponse, vous devez être sûr que vous donnez assez de temps pour régler les sans excitations. L'équation ci-dessus est dépendante du temps, ou plus précisément, le h, les termes J, et K sont fonction du temps. Maintenant, le théorème adiabatique vous dira que si vous exécutez pour t = infini, vous ne serez pas atteindre une précision de 100%. Pourtant, nous pouvons approcher. Même 90% ne sont pas si mauvais, étant donné que vous êtes sûr d'atteindre rapidement une solution peu optimale.

En ce qui concerne la mécanique quantique et de mathématiques, votre vecteur d'état doit toujours être le plus propre de l'hamiltonien. Un état propre, en algèbre linéaire, serait équivalente à un vecteur propre d'une certaine matrice. Si vous êtes familier avec la mécanique quantique, vous saurez que les particules ne peuvent être dans des états d'énergie discrets. L'énergie de ce système serait le hamiltonien, qui est une matrice, et le plus bas niveau d'énergie est donnée par la plus faible de ce vecteur propre hamiltonien. Si vous voulez connaître le niveau d'énergie réelle, ce serait le plus faible valeur propre qui va avec ce qui précède vecteur propre / eigenstate. Maintenant, quand vous êtes recuit, vous voulez toujoursdans l'état fondamental. Ceci est la raison pour laquelle vous devez déplacer lentement, parce que si vous vous déplacez trop rapidement vous communiquer de l'énergie dans le système, ce qui provoque des sauts et des excitations à des niveaux d'énergie plus élevés. Ce n'est pas bon parce que ce où vos erreurs viennent.

État final Une fois que vous avez passé à travers le processus de recuit, vous vous demanderez quelques choses. Comment puis-je savoir que j'ai obtenu la bonne réponse? Combien de temps devrais-je avoir donné mon programme à exécuter? Est-il possible de faire un peu sur la volée correction d'erreur?

Eh bien, vous devrez faire des tests sur votre problème de savoir si vous avez la bonne réponse. En règle générale, si vous résolvez un problème NP-complet, vous pouvez vérifier si votre solution est correcte assez rapidement. Pourtant, vous voulez lancer le calcul plusieurs fois jusqu'à ce que vous mettez cet algorithme particulier pour une utilisation dans tous les cas sérieux. Il y a des mesures pour cela aussi, cependant, et ils doivent le faire avec le suivi de l'énergie réelle de l'hamiltonien, trouvant son état fondamental vecteur propre, puis la comparer avec ce que votre état de qubit est en réalité. Le produit intérieur des deux va vous montrer votre erreur. Notez que cela ne peut se faire théoriquement, que vous ne seriez pas en mesure de suivre votre état quantique sans observer (et donc le changer).

Sur la correction d'erreur de vol est également possible dans une simulation d'un AQC. Permettez-moi de revenir ici. Il y a une idée que vous pouvez écrire un logiciel numérique de sorte que vous pouvez simuler le processus de recuit et de venir avec un temps système pour votre algorithme particulier. Comme il est une simulation, vous avez accès à votre vecteur d'état à tout moment et vous pouvez mesurer l'erreur prédite en fonction des mathématiques. Vous pouvez faire à la volée correction d'erreurs en regardant les mesures d'erreur et de correction, puis ajuster en conséquence vos recuits pas de temps. Jetez un oeil à ce graphique:

est ce qu'on appelle le eigenspectrum d'une simulation 1 qubits. En gros, il vous montre les énergies à travers le temps de recuit pour 1 qubit. Regardez l'axe des x au fil du temps. La courbe du bas est l'état fondamental, et la courbe supérieure est le premier état excité. Remarquez comment à un moment donné, vous obtenez que les deux courbes sont très proches. Ce point est crucial, car plus cette « lacune » de l'énergie est, plus il est probable que l'état du système sautera à cet état d'énergie plus élevée au lieu de séjour à l'état fondamental. Il est clair que cela est un moment où vous voulez déplacer très lentement. A l'inverse, lorsque l'écart d'énergie est très grande, vous pouvez vous déplacer assez rapidement sans se soucier si vous allez passer à un état plus élevé, car il est assez peu probable. Vous pouvez venir avec un temps système cela signifie que vous aller très vite jusqu'à ce que n = 0,5 point et commencer à aller beaucoup plus lentement jusqu'à ce que vous avez franchi le seuil de petit écart.

Quoi qu'il en soit, de sorte que est essentiellement cela. AQC n'a pas été autour depuis longtemps, afin que les gens sont encore à déterminer beaucoup de choses à ce sujet, comme la façon de caractériser cet écart énergétique et la façon dont ils sont liés à votre temps de recuit. Il a beaucoup d'applications potentielles, dont je fais note dans ma réponse à la question que je lié en haut de cette réponse.

Answer 4

saisira cette question essentiellement « décrire / clarifier l'approche de Dwave systèmes pour ordinateurs recuit quantum et QM calcul ". une annonce de base de leur approche initiale dans leur ordinateur Orion se trouve dans [1] et est apparemment aussi la conception utilisé dans les versions ultérieures.

une autre façon de voir est leur idée est de trouver un problème NP complet qui est étroitement liée à l'état dynamique physique naturel et de l'énergie évolution d'un système de qubits mécanique quantique. dans ce cas, il est modèle Ising (s) , un modèle mathématique de ferromagnétisme en mécanique statistique. il a été théoriquement prouvé que la recherche de solutions au modèle d'Ising est NP complet (y compris la version 2d mis en œuvre dans les ordinateurs DWave). [2] mais notez un lien apparemment avec plus de détails fait référence dans [1] est actuellement manquante sur leur site. [3]

Alors l'idée est que tout problème NP complet peut être converti au problème du modèle d'Ising 2-d. mais que les conversions entre la note la plupart des problèmes pratiques impliqueraient beaucoup Qbits et la limite actuelle de 128 Dwave est Qbits (Dwave1 « Ranier »). ils ont annoncé une version 512 qbit « Vésuve » qui na pas encore été publié. DWave a récemment annoncé une vente à Lockheed Martin de la machine Dwave1 et développement. [4] a été publié un document scientifique détaillé dans la nature [5].

[1] Quantum Computing Demo Annonce 2007 Dr Georde Rose, systèmes Dwave

[2] Le modèle d'Ising est NP-complet Barry A . Cipra

[3] "modèle à deux dimensions Ising dans un champ magnétique" a 404

[4] A Strange Computer Promises Grande Vitesse

[5] recuit Quantum avec de fabrication Johnson et al