Computación cuántica y máquinas de Turing: ¿Las máquinas de Turing siguen siendo una medida precisa?

En clase la semana pasada, mi profesor comentó y dijo que las máquinas de Turing se usan como una medida / modelo estándar de lo que es computable y son una base útil de discusión para ese tema. También dijo que se ha demostrado que todas las variantes de las máquinas de Turing son computacionalmente equivalentes, leídas, tan poderosas, como las demás. W

Comenté y dije ayer que, con respecto al poder de computación, noté que algunas máquinas de Turing pueden tomar una cantidad increíblemente grande de tiempo para calcular algo muy simple, mientras que una máquina de Turing con más cintas puede calcular algo en una complejidad asintótica más baja con respecto al número de pasos necesarios.

Ella dijo que con respecto al discurso de clase, el tiempo de ejecución de un algoritmo particular en una máquina de Turing no cambia la definición de computabilidad, o el poder con el que medimos la computabilidad. "Nos preocupa lo que es computable, no lo que es eficientemente computable en este momento". Por lo tanto, no importa si las máquinas de Turing tienen más y más cintas, y cada vez más cintas implican que puede calcular en pasos menores. Bien, entiendo que realmente nos estamos enfocando en lo que ES computable, no en la velocidad a la que podemos calcularlo.

Algo sobre eso simplemente me molesta, porque hasta este punto, los algoritmos con una complejidad espacial y de tiempo asintótica anormalmente grande realmente definen los límites de lo que es, quizás debería decir, prácticamente computable.

Entonces, tengo un par de preguntas:

1. Supongamos que tenemos un modelo para una máquina de turing cuántica , esto debe ser equivalente a una máquina de turing "normal", ¿verdad?

Entonces, la respuesta a esa pregunta creo que realmente va hacia mi razón para escribir esta publicación. ¿La tecnología de computación cuántica es adecuada para las definiciones clásicas de lo que es computable a través de una máquina de Turing?

2. ¿Es algo que está por encima de mi cabeza y debo eliminar esta publicación? No quiero ser precoz, simplemente no vi una pregunta similar a la mía.

Estás mezclando la teoría de la computabilidad (también conocida como teoría de la recursión ) y la teoría de la complejidad (o la complejidad computacional ). La teoría de la computabilidad es un vasto tema matemático que estudia las ramificaciones del concepto de computación . No trata con la complejidad de la computación. Como menciona su profesor, todos los modelos de computación (completos de Turing) son los mismos desde el punto de vista de la teoría de la computabilidad. La teoría de la computabilidad, si bien es un tema matemático interesante, no es un buen modelo para la computación del mundo real por esta razón, como usted menciona.

$T(n)$$S(n)$$T(n)^c$$S(n)^c$$n$$c$$O(1)$$O(n\log n)$$\Omega(n^2)$o moverse incluso para ordenar enteros. Por lo tanto, en el área de algoritmos , otros modelos, como la máquina RAM, reemplazan a las máquinas Turing.

Finalmente, las computadoras cuánticas se pueden modelar de varias maneras diferentes, como la máquina cuántica de Turing. Todo lo que es computable usando computadoras cuánticas también es computable usando computadoras clásicas, por lo que desde el punto de vista de la teoría de la computabilidad, las máquinas cuánticas de Turing son solo otro modelo equivalente. Sin embargo, las máquinas cuánticas de Turing se conjeturan ampliamente que no son polinomialmente equivalentes a las máquinas clásicas de Turing: por ejemplo, la factorización y el logaritmo discreto son "fáciles" para las máquinas cuánticas de Turing (que se pueden resolver en tiempo polinómico), mientras que se conjetura que son "duras". para las máquinas clásicas de Turing (no se puede resolver en tiempo polinómico; aunque algunas personas piensan que la factorización de enteros podría resolverse en tiempo polinómico). Entonces, desde el punto de vista de la teoría de la complejidad, diferente de las máquinas clásicas de Turing.