Dans une machine de quantification quantique, comment la décision de se déplacer le long de la bande mémoire est-elle prise?

14

Soit, pour une machine de Quantum Turing (QTM), l'ensemble d'états soit , et l'alphabet des symboles = { 0 , 1 } , qui apparaissent à la tête de bande. Ensuite, selon ma compréhension, à tout moment donné pendant le calcul du QTM, le qubit qui apparaît à sa tête contiendra un vecteur arbitraire V = a | 1 + b | 0 . Aussi, si | q 0, | q 1, . . . QQ={0,1}V=a|1+b|0|q0,|q1,...Q, alors le vecteur d'état à cette instance sera également un vecteur arbitraire .Vq=b0|q0+b1|q1+...

Maintenant, une fois le cycle d'instructions terminé, les vecteurs et V q décideront si le QTM se déplacera à gauche ou à droite le long de la bande Qubit. Ma question est- puisque l'espace de Hilbert formé par Q est un ensemble infini indénombrable et { Gauche, Droite } est un ensemble discret, la correspondance entre eux sera difficile à créer.VVqQ{Left,Right}

Alors, comment la décision de se déplacer à gauche ou à droite est-elle prise? Le QTM se déplace-t-il à la fois à gauche et à droite en même temps, ce qui signifie que l'ensemble forme également un espace Hilbert différent, et donc le mouvement du QTM devient quelque chose comme un | Gauche + b | Droit .{Left,Right}a|Left+b|Right

Ou, tout comme une machine de Turing classique, le QTM se déplace à gauche ou à droite, mais pas les deux en même temps?

Prem kumar
la source
Voyez si cela aide Comment QTM calcule
Pirate X
@PirateX J'ai lu ce post, mais je ne comprends pas si l'état interne du QTM est une entité classique ou Quantum. Peut-il aller en superposition de différents états internes? De plus, un QTM peut-il déplacer à la fois la gauche et la droite le long de sa bande mémoire en même temps? Q
Prem kumar

Réponses:

7

Si nous avons un QTM avec un jeu d'états et un alphabet de bande Σ = { 0 , 1 } , nous ne pouvons pas dire que le qubit analysé par la tête de bande "contient" un vecteur a | 0 + b | 1 ou que l'état (interne) est un vecteur avec les états de base correspondant à Q . Les qubits sur la bande peuvent être corrélés entre eux et avec l'état interne, ainsi qu'avec la position de la tête de bande.QΣ={0,1}a|0+b|1Q

Par analogie, nous ne décririons pas l'état global d'une machine de Turing probabiliste en spécifiant indépendamment une distribution pour l'état interne et pour chacun des carrés de bande. Nous devons plutôt tout décrire ensemble afin de représenter correctement les corrélations entre les différentes parties de la machine. Par exemple, les bits stockés dans deux carrés de bande distants peuvent être parfaitement corrélés, à la fois 0 avec la probabilité 1/2 et les deux 1 avec la probabilité 1/2.

Donc, dans le cas quantique, et en supposant que nous parlons d'états purs de machines de Turing quantiques avec des évolutions unitaires (par opposition à un modèle plus général basé sur des états mixtes), l'état global est représenté par un vecteur dont les entrées sont indexées par configurations (c.-à-d. descriptions classiques de l'état interne, de l'emplacement de la tête de bande et du contenu de chaque carré de bande) de la machine de Turing. Il convient de noter que nous supposons généralement qu'il y a un symbole vide spécial dans l'alphabet de la bande (qui pourrait être 0 si nous voulons que nos carrés de bande stockent des qubits) et que nous commençons les calculs avec au plus un nombre fini de carrés non blancs, de sorte que l'ensemble de toutes les configurations accessibles est dénombrable. Cela signifie que l'état sera représenté par un vecteur unitaire dans un espace de Hilbert séparable.

(q,σ)

Q={0,1}Σ={0,1}(et nous prendrons 0 pour être le symbole vide). Nous commençons dans l'état 0 en balayant un carré qui stocke 1, et tous les autres carrés stockent 0. Je n'écrirai pas explicitement la fonction de transition, mais je décrirai simplement le comportement en mots. À chaque déplacement, le contenu du carré de bande numérisé est interprété comme un bit de contrôle pour une opération Hadamard sur l'état interne. Une fois le Hadamard contrôlé effectué, la tête se déplace vers la gauche si le (nouvel) état est 0 et se déplace vers la droite si le (nouvel) état est 1. (Dans cet exemple, nous ne modifions jamais réellement le contenu de la bande.) Après une étape , le QTM sera dans une superposition également pondérée entre être dans l'état 0 avec le carré de balayage de tête de bande -1, et être dans l'état 1 avec le carré de balayage de tête de bande +1. Lors de tous les mouvements ultérieurs, le Hadamard contrôlé ne fait rien car chaque carré à part le carré 0 contient le symbole 0. La tête de bande continuera donc à se déplacer simultanément à gauche et à droite, comme une particule se déplaçant vers la gauche et vers la droite en superposition.

Si vous le vouliez, vous pourriez bien sûr définir une variante du modèle de machine de Turing quantique pour laquelle l'emplacement et le mouvement de la tête de bande sont déterministes, ce qui ne ruinerait pas l'universalité de calcul du modèle, mais la définition "classique" de Turing quantique. machines n'impose pas cette restriction.

John Watrous
la source
1
@Premkumar: En tant que note de bas de page pour cette réponse --- si vous cherchez une référence faisant autorité pour ce compte rendu des QTM, un bon endroit à considérer serait le travail fondateur "Théorie de la complexité quantique" de Bernstein et Vazirani (Proc. 25th Annual ACM STOC (pp.1411–1473), 1997 [lien PDF gratuit sur citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.7852 ]. Presque toutes les remarques de John ci-dessus sont essentiellement une extension de la définition 3.2 dans cet article, et une partie de la discussion dans la même section.
Niel de Beaudrap
@Niel: Je ne sais pas si vous pouvez modifier un commentaire, mais comme vous le savez sans doute, la version de conférence du document de Bernstein et Vazirani est apparue en 1993, et non en 1997. La version de 1997 est parue dans SIAM Journal of Computing (en un numéro spécial vraiment monumental sur l'informatique quantique).
John Watrous
C'est vrai, et même le lien PDF gratuit décrit l'année 1993; J'ai l'impression d'avoir croisé des fils. (Les commentaires peuvent être modifiés jusqu'à 10 minutes.)
Niel de Beaudrap
@NieldeBeaudrap Petite correction: jusqu'à 5 minutes :) (pour les utilisateurs normaux). Les mods peuvent modifier les commentaires à tout moment.
Sanchayan Dutta
4

La machine quantique de Turing peut se déplacer dans une superposition de déplacement à gauche et à droite. Ceci est différent de la machine Turing classique qui ne peut se déplacer que vers la gauche ou la droite.

pyramides
la source