En una máquina Quantum Turing, ¿cómo se toma la decisión de moverse por la cinta de memoria?

14

Sea, para una máquina Quantum Turing (QTM), el conjunto de estados sea , y el alfabeto de símbolos sea , que aparecen en el cabezal de la cinta. Entonces, según tengo entendido, en cualquier momento mientras el QTM está calculando, el qubit que aparece en su cabeza tendrá un vector arbitrario . Además, si , entonces el vector de estado en ese caso también será un vector arbitrario .= { 0 , 1 } V = a | 1 + b | 0 | q 0, | q 1, . . . Q V q = b 0 | q 0+ b 1 | q 1+ . . .Q={0,1}V=a|1+b|0|q0,|q1,...QVq=b0|q0+b1|q1+...

Ahora, una vez que se completa el ciclo de instrucciones, los vectores y decidirán si el QTM se moverá hacia la izquierda o hacia la derecha a lo largo de la cinta Qubit. Mi pregunta es: dado que el espacio de Hilbert formado por Q \ otimes \ sum es un conjunto infinito incontable y \ {\ text {Left, Right} \} es un conjunto discreto, la asignación entre ellos será difícil de crear.V q Q { Izquierda, Derecha }VVqQ{Left,Right}

Entonces, ¿cómo se toma la decisión de moverse hacia la izquierda o hacia la derecha? ¿El QTM se mueve tanto a la izquierda como a la derecha al mismo tiempo, lo que significa que el conjunto {Left,Right} también forma un espacio Hilbert diferente, y por lo tanto el movimiento del QTM se convierte en algo así como a|Left+b|Right .

¿O, al igual que una máquina clásica de Turing, la QTM se mueve hacia la izquierda o hacia la derecha, pero no ambas al mismo tiempo?

Prem kumar
fuente
Vea si esto ayuda Cómo calcula QTM
Pirate X
@PirateX He leído esa publicación, pero no entiendo si el estado interno de QTM es una entidad clásica o cuántica. ¿Puede ir en superposición de diferentes estados internos? Además, ¿puede un QTM moverse tanto a la izquierda como a la derecha a lo largo de su cinta de memoria al mismo tiempo? Q
Prem kumar

Respuestas:

7

Si tenemos un QTM con el conjunto de estados y un alfabeto de cinta , no podemos decir que el qubit escaneado por el cabezal de la cinta "contiene" un vector o que el estado (interno) es un vector con estados de la base que corresponden a . Los qubits de la cinta pueden correlacionarse entre sí y con el estado interno, así como con la posición del cabezal de la cinta.QΣ={0,1}a|0+b|1Q

Como analogía, no describiríamos el estado global de una máquina Turing probabilística al especificar independientemente una distribución para el estado interno y para cada uno de los cuadrados de la cinta. Más bien, tenemos que describir todo juntos para representar correctamente las correlaciones entre las diferentes partes de la máquina. Por ejemplo, los bits almacenados en dos cuadrados de cinta distantes podrían estar perfectamente correlacionados, ambos 0 con probabilidad 1/2 y ambos 1 con probabilidad 1/2.

Entonces, en el caso cuántico, y suponiendo que estamos hablando de estados puros de máquinas cuánticas de Turing con evoluciones unitarias (en oposición a un modelo más general basado en estados mixtos), el estado global está representado por un vector cuyas entradas están indexadas por configuraciones (es decir, descripciones clásicas del estado interno, la ubicación del cabezal de la cinta y el contenido de cada cuadrado de la cinta) de la máquina Turing. Cabe señalar que generalmente asumimos que hay un símbolo especial en blanco en el alfabeto de la cinta (que podría ser 0 si queremos que nuestros cuadrados de cinta almacenen qubits) y que comenzamos los cálculos con como máximo muchos cuadrados que no están en blanco, para que el conjunto de todas las configuraciones accesibles sea contable. Esto significa que el estado estará representado por un vector unitario en un espacio separable de Hilbert.

Finalmente, y tal vez esta es la respuesta real a la pregunta interpretada literalmente, el movimiento del cabezal de la cinta está determinado por la función de transición, que asignará una "amplitud" a cada acción posible (nuevo estado, nuevo símbolo y movimiento del cabezal de la cinta). ) para cada par clásico representa el estado actual y el símbolo escaneado actualmente. Nada obliga al cabezal de la cinta a moverse de manera determinista: se puede asignar una amplitud distinta de cero a dos o más acciones que incluyen movimientos del cabezal de la cinta hacia la izquierda y hacia la derecha, por lo que es posible que un cabezal de cinta QTM se mueva hacia la izquierda y hacia la derecha superposición.(q,σ)

Por ejemplo, puede imaginar una QTM con yQ={0,1}Σ={0,1}(y tomaremos 0 para ser el símbolo en blanco). Comenzamos en el estado 0 escaneando un cuadrado que almacena 1, y todos los otros cuadrados almacenan 0. No escribiré explícitamente la función de transición, sino que solo describiré el comportamiento en palabras. En cada movimiento, el contenido del cuadrado de la cinta escaneada se interpreta como un bit de control para una operación de Hadamard en el estado interno. Después de que se realiza el Hadamard controlado, la cabeza se mueve hacia la izquierda si el estado (nuevo) es 0 y se mueve hacia la derecha si el estado (nuevo) es 1. (En este ejemplo, nunca cambiamos realmente el contenido de la cinta). Después de un paso , el QTM estará en una superposición igualmente ponderada entre estar en el estado 0 con el cuadrado de escaneo del cabezal de la cinta -1 y estar en el estado 1 con el cuadrado de escaneo del cabezal de la cinta +1. En todos los movimientos posteriores, el Hadamard controlado no hace nada porque cada casilla, aparte de la casilla 0, contiene el símbolo 0. Por lo tanto, el cabezal de la cinta continuará moviéndose simultáneamente tanto a la izquierda como a la derecha, como una partícula que viaja hacia la izquierda y hacia la derecha en superposición.

Si quisiera, podría, por supuesto, definir una variante del modelo de máquina cuántica de Turing para la cual la ubicación y el movimiento del cabezal de la cinta es determinista, y esto no arruinaría la universalidad computacional del modelo, sino la definición "clásica" de Turing cuántico Las máquinas no imponen esta restricción.

John Watrous
fuente
1
@Premkumar: Como nota de pie de página a esta respuesta --- si está buscando una referencia autorizada para esta cuenta de QTM, un buen lugar para considerar sería el trabajo seminal "Teoría de la complejidad cuántica" de Bernstein y Vazirani (25a edición anual del Proc. ACM STOC (pp.1411–1473), 1997 [enlace PDF gratuito en citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.7852 ]. Casi todos los comentarios de John anteriores son esencialmente una expansión de la Definición 3.2 en ese artículo, y parte de la discusión en la misma Sección.
Niel de Beaudrap
@Niel: No estoy seguro si puedes editar un comentario, pero como estoy seguro de que sabes, la versión de la conferencia del documento de Bernstein y Vazirani apareció en 1993, no en 1997. La versión de la revista de 1997 apareció en SIAM Journal of Computing (en un número especial verdaderamente monumental sobre computación cuántica).
John Watrous el
Es cierto, e incluso el enlace PDF gratuito describe el año 1993; Parece que he cruzado algunos cables. (Los comentarios pueden editarse hasta por 10 minutos.)
Niel de Beaudrap
@NieldeBeaudrap Pequeña corrección: hasta 5 minutos :) (para usuarios normales). Las modificaciones pueden editar comentarios, en cualquier momento.
Sanchayan Dutta
4

La máquina cuántica de Turing puede moverse hacia una superposición de movimiento hacia la izquierda y hacia la derecha. Esto es diferente de la máquina clásica de Turing que solo puede moverse hacia la izquierda o hacia la derecha.

pirámides
fuente