Page 187 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 187
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
La estructura de una máquina de Turing cuántica es muy similar a la de una máquina de Turing clá-
sica. Está compuesta por los tres elementos clásico.
• una cinta de memoria infinita en donde cada elemento es un qubit,
• un procesador finito y
• un cabezal.
El procesador contiene el juego de instrucciones que se aplica sobre el elemento de la cinta señalado
por el cabezal. El resultado dependerá del qubit de la cinta y del estado del procesador. El procesa-
dor ejecuta una instrucción por unidad de tiempo.
La cinta de memoria es similar a la de una máquina de Turing tradicional. La única diferencia es que
cada elemento de la cinta de la máquina cuántica es un qubit. El alfabeto de esta nueva máquina
está formado por el espacio de valores del qubit. La posición del cabezal se representa con una
variable entera (figura 8.3).
Figura 8.3. Una máquina de Turing cuántica
181
