Máquina cuántica de Turing

Modelo de computación cuántica

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. ^{[1] [2] : 2}

Las máquinas cuánticas de Turing 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. Así lo demostró Lance Fortnow . ^[3]

boceto informal

Problema no resuelto 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 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 MT clásica son reemplazados por estados puros o mixtos en un espacio de Hilbert ; la función de transición se reemplaza 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 la 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 un sistema cuántico en sí mismo. ${\displaystyle \Sigma }$
• La función de transición es una generalización de un monoide de transición y se entiende como un conjunto 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 simplemente un esbozo de una máquina cuántica de Turing, más que su definición formal, ya que deja vagos varios detalles importantes: por ejemplo, con qué frecuencia se realiza una medición ; consulte, por ejemplo, la diferencia entre una QFA de medida única y de muchas medidas. 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 ^{[5] [6]} que describían por primera vez un modelo mecánico cuántico de 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 (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 mediciones cuánticas sin resultados clásicos. ^[7]

Scott Aaronson definió una máquina cuántica de Turing 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]

Ver también

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

Referencias

1. Andrés Yao (1993). Complejidad del circuito cuántico . 34º Simposio Anual sobre Fundamentos de la Informática. págs. 352–361.
2. AbelMolina; John Watrous (2018). "Revisando la simulación de máquinas cuánticas de Turing mediante circuitos cuánticos". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería . 475 (2226). arXiv : 1808.01701 . doi :10.1098/rspa.2018.0767. PMC 6598068 . PMID  31293355. 
3. Por ahora, Lance (2003). "La visión de la computación cuántica de un teórico de la complejidad". Informática 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). "La 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. Código Bib : 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 sistema físico: un modelo hamiltoniano microscópico de mecánica cuántica de computadoras representado por las máquinas de Turing". Revista de Física Estadística . 22 (5): 563–591. Código Bib : 1980JSP....22..563B. doi :10.1007/bf01011339. S2CID  122949592.
6. Benioff, P. (1982). "Modelos hamiltonianos mecánicos cuánticos de máquinas de Turing". Revista de Física Estadística . 29 (3): 515–546. Código Bib : 1982JSP....29..515B. doi :10.1007/BF01342185. S2CID  14956017.
7. Simón Perdrix; Philippe Jorrand (4 de abril de 2007). "Computación cuántica controlada clásicamente". Matemáticas. Estructura. En Comp. Ciencia . 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) . Matemáticas. Estructura. En comp. Ciencia . 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 Bib : 2005RSPSA.461.3473A. doi :10.1098/rspa.2005.1546. S2CID  1770389.Preimpresión disponible en [1].

Otras lecturas

• Molina, Abel; Watrous, John (2018). "Revisando la simulación de máquinas cuánticas de Turing mediante circuitos cuánticos". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de 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 del caos SAT". arXiv : quant-ph/0405191 .
• Alemán, 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. Código Bib : 1985RSPSA.400...97D. CiteSeerX  10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. JSTOR  2397601. S2CID  1438116.

enlaces externos

• La computadora cuántica – historia