¿Cómo definir las máquinas cuánticas de Turing?

52

En computación cuántica, ¿cuál es el modelo equivalente de una máquina de Turing? Para mí está bastante claro cómo los circuitos cuánticos pueden construirse a partir de puertas cuánticas, pero ¿cómo podemos definir una máquina cuántica de Turing (QTM) que realmente pueda beneficiarse de los efectos cuánticos, es decir, funcionar en sistemas de alta dimensión?

Sonó.
fuente
99
Esta nota de Berkeley da una respuesta. www.eecs.berkeley.edu/~vazirani/f97qcom/lec19.ps
Mohammad Al-Turkistany
1
En realidad, el modelo de circuitos cuánticos y la máquina de medición cuántica son equivalentes, lo que ha sido probado por ACYao.
Strin

Respuestas:

30

( nota : la descripción completa es un poco compleja y tiene varias sutilezas que preferí ignorar. Las siguientes son solo las ideas de alto nivel para el modelo QTM)

Al definir una máquina Quantum Turing (QTM), a uno le gustaría tener un modelo simple, similar a la TM clásica (es decir, una máquina de estado finito más una cinta infinita), pero permitir al nuevo modelo la ventaja de la mecánica cuántica.

De manera similar al modelo clásico, QTM tiene:

  1. - un conjunto finito de estados. Deje q 0 ser un estado inicial.Q={q0,q1,..}q0
  2. , Γ = { γ 0 , . . } - conjunto de entrada / alfabeto de trabajoΣ={σ0,σ1,...}Γ={γ0,..}
  3. una cinta infinita y una sola "cabeza".

C=(q,T,i)qQTΓi

HQ×Σ×ZC=(q,T,i)

|C=|q|T|i.
Γ

|ψ(0)=|q0|T0|1T0ΓxΣ

U

|ψ(i+1)=U|ψ(i)

n|ψ(n)=Un|ψ(0)Uq,T,i|U|q,T,ii=i±1TTi

qf

Lo interesante a notar es que cada "paso" del estado del QTM es una superposición de posibles configuraciones, lo que le da al QTM la ventaja "cuántica".


La respuesta se basa en Masanao Ozawa, Sobre el problema de las máquinas cuánticas de Turing . Ver también David Deutsch, la teoría cuántica, el principio de Church-Turing y la computadora cuántica universal .

Sonó.
fuente
77
No estoy seguro de que la definición original de David Deutsch haga que todo sea correcto ... esta fue la primera vez que alguien intentó definirlo, y se necesitaron algunas mejoras para descubrir la definición matemáticamente precisa correcta.
Peter Shor
7

Como indican las notas, la forma de definir un QTM es definir la función de transición como una transformación unitaria de estado y letra. Entonces, en cada paso, imagina multiplicar el vector (estado, letra) por una transformación para obtener un nuevo (estado, letra). No es particularmente conveniente, pero se puede definir.

Suresh
fuente