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 en 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 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 . [3]
Boceto informal
¿Es suficiente una computadora cuántica universal para simular de manera eficiente un sistema físico arbitrario?
Una forma de entender la máquina de Turing cuántica (QTM) es que generaliza la máquina de Turing clásica (TM) de la misma manera que el autómata finito cuántico (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. [4]
Es decir, una máquina de Turing clásica se describe mediante una tupla de 7 .
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 .
- Los símbolos del alfabeto de cinta son igualmente reemplazados por un espacio de Hilbert (generalmente un espacio de Hilbert diferente al conjunto de estados).
- El símbolo en blanco corresponde al vector cero.
- Los símbolos de entrada y salida generalmente se toman como un conjunto discreto, como en el sistema clásico; por tanto, ni la entrada ni la salida de una máquina cuántica necesitan ser un sistema cuántico en sí.
- La función de transición es una generalización de un monoide de transición , y se entiende que es una colección de matrices unitarias que son automorfismos del espacio de Hilbert.
- El estado inicial puede ser un estado mixto o un estado puro .
- El conjunto de estados finales o de aceptación es un subespacio del espacio de Hilbert.
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, la frecuencia con la que se realiza una medición ; ver, por ejemplo, la diferencia entre una medida-una vez 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 [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 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. [7]
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 . [8]
Ver también
- Simulador cuántico § Resolución de problemas de física
Referencias
- ^ Andrew Yao (1993). Complejidad del circuito cuántico . 34º Simposio Anual sobre Fundamentos de la Informática. págs. 352–361.
- ^ Abel Molina; John Watrous (2018). "Revisando la simulación de máquinas cuánticas de Turing por circuitos cuánticos". arXiv : 1808.01701 [ cs.CC ].
- ^ Fortnow, Lance (2003). "Vista de un teórico de la complejidad de la computación cuántica". Informática Teórica . 292 (3): 597–610. arXiv : quant-ph / 0003035 . doi : 10.1016 / S0304-3975 (01) 00377-2 .
- ^ a b Deutsch, David (julio de 1985). "Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal" (PDF) . Proceedings of the Royal Society A . 400 (1818): 97-117. Código Bibliográfico : 1985RSPSA.400 ... 97D . CiteSeerX 10.1.1.41.2382 . doi : 10.1098 / rspa.1985.0070 . Archivado desde el original (PDF) el 23 de noviembre de 2008.
- ^ Benioff, Paul (1980). "La computadora como un sistema físico: un modelo microscópico cuántico hamiltoniano de computadoras representado por las máquinas de Turing". Revista de física estadística . 22 (5): 563–591. Código Bibliográfico : 1980JSP .... 22..563B . doi : 10.1007 / bf01011339 .
- ^ Benioff, P. (1982). "Modelos hamiltonianos de mecánica cuántica de máquinas de turing". Revista de física estadística . 29 (3): 515–546. Código bibliográfico : 1982JSP .... 29..515B . doi : 10.1007 / BF01342185 .
- ^ Simon Perdrix; Philippe Jorrand (4 de abril de 2007). "Computación cuántica controlada clásicamente". Matemáticas. Struct. En Comp. Ciencia . 16 (4): 601–620. arXiv : quant-ph / 0407008 . doi : 10.1017 / S096012950600538X . además Simon Perdrix y Philippe Jorrand (2006). "Computación cuántica controlada clásicamente" (PDF) . Matemáticas. Struct. En Comp. Ciencia . 16 (4): 601–620. CiteSeerX 10.1.1.252.1823 . doi : 10.1017 / S096012950600538X .
- ^ Aaronson, Scott (2005). "Computación cuántica, postselección y polinomio probabilístico-tiempo". Proceedings of the Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph / 0412187 . Código bibliográfico : 2005RSPSA.461.3473A . doi : 10.1098 / rspa.2005.1546 .Preimpresión disponible en [1]
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 of London. 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