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

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$$\sum=\{0,1\}$$V_\sum = a|1\rangle+b|0\rangle$$|q_0\rangle , |q_1\rangle, ... \in Q$$V_q=b_0|q_0\rangle + b_1 |q_1\rangle+ ...$

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 $V_\sum$$V_q$$Q \otimes \sum$$\{\text{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 $\{\text{Left,Right}\}$ también forma un espacio Hilbert diferente, y por lo tanto el movimiento del QTM se convierte en algo así como $a|\text{Left}\rangle+b|\text{Right}\rangle$ .

¿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?

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$$\Sigma = \{0,1\}$$a|0\rangle + b|1\rangle$$Q$

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,\sigma)$

Por ejemplo, puede imaginar una QTM con y$Q = \{0,1\}$$\Sigma = \{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.

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.