Máquina cuántica de Turing - Quantum Turing machine

Una máquina cuántica de Turing ( QTM ) o computadora cuántica universal es una máquina abstracta utilizada para modelar los efectos de una computadora cuántica . Proporciona un modelo simple que captura todo el poder de la computación cuántica, es decir, cualquier algoritmo cuántico puede expresarse formalmente como una máquina cuántica de Turing particular. Sin embargo, el circuito cuántico computacionalmente equivalente es un modelo más común.

Las máquinas cuánticas de Turing se pueden relacionar con las máquinas de Turing clásicas y probabilísticas en un marco basado en matrices de transición . Es decir, se puede especificar una matriz cuyo producto con la matriz que representa una máquina clásica o probabilística proporciona la matriz de probabilidad cuántica que representa la máquina cuántica. Esto fue demostrado por Lance Fortnow .

Boceto informal

Problema no resuelto en física : ¿Es suficiente una computadora cuántica universal para simular de manera eficiente un sistema físico arbitrario? (más problemas sin resolver en física)

Una forma de entender la máquina cuántica de Turing (QTM) es que generaliza la máquina de Turing clásica (TM) de la misma manera que el autómata cuántico finito (QFA) generaliza el autómata finito determinista (DFA). En esencia, los estados internos de una TM clásica se reemplazan por estados puros o mixtos en un espacio de Hilbert; la función de transición es reemplazada por una colección de matrices unitarias que mapean el espacio de Hilbert a sí mismo.

Es decir, una máquina de Turing clásica se describe mediante una tupla de 7 . ${\ Displaystyle M = \ langle Q, \ Gamma, b, \ Sigma, \ delta, q_ {0}, F \ rangle}$

Para una máquina de Turing cuántica de tres cintas (una cinta que contiene la entrada, una segunda cinta que contiene resultados de cálculo intermedios y una tercera cinta que contiene la salida):

• El conjunto de estados se reemplaza por un espacio de Hilbert . ${\ displaystyle Q}$
• Los símbolos del alfabeto de cinta también se reemplazan por un espacio de Hilbert (generalmente un espacio de Hilbert diferente al conjunto de estados). ${\ Displaystyle \ Gamma}$
• El símbolo en blanco corresponde al vector cero. ${\ Displaystyle b \ in \ Gamma}$
• Los símbolos de entrada y salida generalmente se toman como un conjunto discreto, como en el sistema clásico; por lo tanto, ni la entrada ni la salida de una máquina cuántica necesitan ser un sistema cuántico en sí. ${\ Displaystyle \ Sigma}$
• La función de transición es una generalización de un monoide de transición y se entiende como una colección de matrices unitarias que son automorfismos del espacio de Hilbert . ${\ Displaystyle \ delta: \ Sigma \ times Q \ otimes \ Gamma \ rightarrow \ Sigma \ times Q \ otimes \ Gamma \ times \ {L, R \}}$${\ displaystyle Q}$
• El estado inicial puede ser un estado mixto o un estado puro . ${\ Displaystyle q_ {0} \ in Q}$
• El conjunto de estados finales o de aceptación es un subespacio del espacio de Hilbert . ${\ displaystyle F}$${\ displaystyle Q}$

Lo anterior es simplemente un bosquejo de una máquina cuántica de Turing, más que su definición formal, ya que deja vagos varios detalles importantes: por ejemplo, la frecuencia con la que se realiza una medición ; ver, por ejemplo, la diferencia entre una medida-una y una medida-muchos QFA. Esta cuestión de medición afecta la forma en que se definen las escrituras en la cinta de salida.

Historia

En 1980 y 1982, el físico Paul Benioff publicó artículos que describían por primera vez un modelo mecánico cuántico de las máquinas de Turing . Un artículo de 1985 escrito por el físico de la Universidad de Oxford David Deutsch desarrolló aún más la idea de las computadoras cuánticas al sugerir que las puertas cuánticas podrían funcionar de manera similar a las puertas lógicas binarias de la computación digital tradicional .

Iriyama, Ohya y Volovich han desarrollado un modelo de una máquina de Turing cuántica lineal (LQTM). Esta es una generalización de un QTM clásico que tiene estados mixtos y que permite funciones de transición irreversibles. Estos permiten la representación de medidas cuánticas sin resultados clásicos.

Un cuántica máquina de Turing con la post- fue definida por Scott Aaronson , que mostró que la clase de tiempo polinómico en tal máquina un ( PostBQP ) es igual a la clase de complejidad clásica PP .

Ver también

• Simulador cuántico § Resolución de problemas de física

Referencias

Otras lecturas

• Molina, Abel; Watrous, John (2018). "Revisando la simulación de máquinas cuánticas de Turing por circuitos cuánticos". arXiv : 1808.01701 [ cs.CC ].
• Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Máquina de Turing cuántica generalizada y su aplicación al algoritmo del caos SAT". arXiv : quant-ph / 0405191 .
• Deutsch, D. (1985). "Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal". Actas de la Royal Society de Londres. Serie A, Ciencias Físicas y Matemáticas . 400 (1818): 97-117. Código Bibliográfico : 1985RSPSA.400 ... 97D . CiteSeerX   10.1.1.41.2382 . doi : 10.1098 / rspa.1985.0070 . JSTOR   2397601 .

enlaces externos

• La computadora cuántica - historia