¿Puede una máquina de Turing simular una computadora cuántica?

Sé que una máquina de Turing ¹ puede simular teóricamente "cualquier cosa", pero no sé si podría simular algo tan fundamentalmente diferente como una computadora basada en la cuántica. ¿Hay algún intento de hacer esto, o alguien ha demostrado que sea posible / no posible?

Busqué en Google, pero no soy un experto en este tema, así que no estoy seguro de dónde buscar. Encontré el artículo de Wikipedia sobre la máquina cuántica de Turing , pero no estoy seguro de en qué se diferencia exactamente de una TM clásica. También encontré el artículo Universal Quantum Turing Machine de Deutsch , de W. Fouché et al., Pero es bastante difícil de entender para mí.

_{1. En caso de que no esté claro, por máquina de Turing me refiero al concepto teórico, no a una máquina física (es decir, una implementación del concepto teórico).}

Sí , una computadora cuántica podría ser simulada por una máquina Turing , aunque esto no debería implicar que las computadoras cuánticas del mundo real no podrían disfrutar de una ventaja cuántica , es decir, una ventaja de implementación significativa sobre las computadoras clásicas del mundo real.

Como regla general, si un humano pudiera describir o imaginar manualmente cómo debería funcionar algo, esa imaginación se puede implementar en una máquina Turing. Las computadoras cuánticas entran en esta categoría.

En la actualidad, una gran motivación para la computación cuántica es que los qubits pueden existir en superposiciones , esencialmente permite el cálculo masivamente paralelo. Luego está el recocido cuántico y otros pequeños trucos que son básicamente tácticas de computación analógica .

Pero, esos beneficios son sobre la eficiencia. En algunos casos, esa eficiencia está más allá de lo astronómico, permitiendo cosas que no habrían sido prácticas en el hardware clásico. Esto hace que la computación cuántica tenga aplicaciones importantes en criptografía y demás.

Sin embargo, la computación cuántica no está motivada actualmente por un deseo de cosas que básicamente no podíamos hacer antes. Si una computadora cuántica puede realizar una operación, entonces una máquina clásica de Turing podría realizar una simulación de una computadora cuántica que realiza esa operación.

La aleatoriedad no es un problema. Supongo que dos grandes razones:

1. La aleatoriedad se puede capturar con mayor precisión mediante el uso de matemáticas de distribución de todos modos.

2. La aleatoriedad no es una " cosa " real para empezar; Es simplemente ignorancia. Y siempre podemos producir ignorancia.

Para simular el colapso de la función de onda necesitaría una fuente de aleatoriedad. Entonces necesitarías una máquina probabilística de Turing .

Para completar lo que otros han dicho: hasta donde sabemos, una máquina de Turing (clásica) no puede realmente simular correlaciones cuánticas . Esto se afirma explícitamente en la sección Propiedades de la computadora cuántica universal en el artículo seminal de la teoría cuántica de David Deutsch , el principio de Church-Turing y la computadora cuántica universal (Proceedings of the Royal Society of London A 400, pp. 97-117 (1985). )).

Los detalles dependerán de la implementación o de sus definiciones exactas para la máquina de Turing, de la computadora cuántica, y especialmente de simulación (si es lo suficientemente generoso con lo que significa simulación , cualquier cosa puede simular cualquier cosa). En términos generales, es posible diseñar una computadora cuántica que, cuando se opera repetidamente comenzando exactamente desde el mismo estado inicial (o bits de entrada), en cada operación genera bits de salida aleatorios que presentan ciertas correlaciones cuánticas entre sí.

Que yo sepa, una máquina de Turing no puede hacer eso.