Máquina cuántica de Turing

Modelo de computación cuántica

Una máquina de Turing cuántica ( QTM ) o computadora cuántica universal es una máquina abstracta que se utiliza 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 de Turing cuántica particular. Sin embargo, el circuito cuántico computacionalmente equivalente es un modelo más común. ^{[1] [2] : 2}

Las máquinas de Turing cuánticas pueden relacionarse 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 proporcione la matriz de probabilidad cuántica que representa la máquina cuántica. Esto fue demostrado por Lance Fortnow . ^[3]

Boceto informal

Problema sin resolver en física :

¿Es suficiente una computadora cuántica universal para simular eficientemente un sistema físico arbitrario?

(más problemas sin resolver en física)

Una forma de entender la máquina de Turing cuántica (TMC) es que generaliza la máquina de Turing clásica (TM) de la misma manera que el autómata finito cuántico (AFC) generaliza el autómata finito determinista (AFD). En esencia, los estados internos de una TM clásica son reemplazados 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. ^[4]

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 los resultados de los cálculos 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 es un elemento del espacio de Hilbert. ${\displaystyle b\in \Gamma }$
• Los símbolos de entrada y salida suelen tomarse 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 en sí mismas un sistema cuántico. ${\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 \to \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 un mero esbozo de una máquina de Turing cuántica, en lugar de su definición formal, ya que deja vagos varios detalles importantes: por ejemplo, con qué frecuencia se realiza una medición ; véase, por ejemplo, la diferencia entre una QFA de medición única y una de medición múltiple. Esta cuestión de la 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 ^{[5] [6]} que describieron 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 . ^[4]

Iriyama, Ohya y Volovich han desarrollado un modelo de máquina de Turing cuántica lineal (MCU), que es una generalización de una MCU clásica que tiene estados mixtos y que permite funciones de transición irreversibles, lo que permite la representación de mediciones cuánticas sin resultados clásicos. ^[7]

Scott Aaronson definió una máquina de Turing cuántica con postselección y demostró que la clase de tiempo polinomial en dicha máquina ( PostBQP ) es igual a la clase de complejidad clásica PP . ^[8]

Véase también

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

Referencias

1. Andrew Yao (1993). Complejidad de circuitos cuánticos . 34.º Simposio anual sobre fundamentos de la informática. pp. 352–361.
2. Abel Molina; John Watrous (2018). "Revisitando la simulación de máquinas de Turing cuánticas mediante circuitos cuánticos". Actas de la Royal Society A: Ciencias matemáticas, físicas e ingeniería . 475 (2226). arXiv : 1808.01701 . doi : 10.1098 /rspa.2018.0767. PMC 6598068. PMID  31293355. 
3. Fortnow, Lance (2003). "La visión de la computación cuántica desde un teórico de la complejidad". Ciencias de la computación teórica . 292 (3): 597–610. arXiv : quant-ph/0003035 . doi :10.1016/S0304-3975(01)00377-2. S2CID  18657540.
4. Deutsch, David (julio de 1985). "Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal" (PDF) . Actas de la Royal Society A. 400 ( 1818): 97–117. Bibcode :1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. S2CID  1438116. Archivado desde el original (PDF) el 23 de noviembre de 2008. 
5. Benioff, Paul (1980). "La computadora como un sistema físico: Un modelo hamiltoniano mecánico cuántico microscópico de computadoras representado por máquinas de Turing". Journal of Statistical Physics . 22 (5): 563–591. Bibcode :1980JSP....22..563B. doi :10.1007/bf01011339. S2CID  122949592.
6. Benioff, P. (1982). "Modelos hamiltonianos de la mecánica cuántica de las máquinas de Turing". Journal of Statistical Physics . 29 (3): 515–546. Bibcode :1982JSP....29..515B. doi :10.1007/BF01342185. S2CID  14956017.
7. Simon Perdrix; Philippe Jorrand (4 de abril de 2007). "Computación cuántica controlada clásicamente". Matemáticas. Estructura. En Comp. Science . 16 (4): 601–620. arXiv : quant-ph/0407008 . doi :10.1017/S096012950600538X. S2CID  16142327.También: Simon Perdrix y Philippe Jorrand (2006). "Computación cuántica controlada clásicamente" (PDF) . Math. Struct. En Comp. Science . 16 (4): 601–620. arXiv : quant-ph/0407008 . CiteSeerX 10.1.1.252.1823 . doi :10.1017/S096012950600538X. S2CID  16142327. 
8. Aaronson, Scott (2005). "Computación cuántica, postselección y tiempo polinomial probabilístico". Actas de la Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph/0412187 . Código Bibliográfico :2005RSPSA.461.3473A. doi :10.1098/rspa.2005.1546. S2CID  1770389.Preimpresión disponible en [1].

Lectura adicional

• Molina, Abel; Watrous, John (2018). "Revisitando la simulación de máquinas de Turing cuánticas mediante circuitos cuánticos". Actas de la Royal Society A: Ciencias matemáticas, físicas e ingeniería . 475 (2226). arXiv : 1808.01701 . doi :10.1098/rspa.2018.0767. PMC  6598068 . PMID  31293355.
• Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Máquina de Turing cuántica generalizada y su aplicación al algoritmo de 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 matemáticas y físicas . 400 (1818): 97–117. Bibcode :1985RSPSA.400...97D. CiteSeerX  10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. JSTOR  2397601. S2CID  1438116.

Enlaces externos

• El ordenador cuántico – historia