¿Cuáles son las diferencias entre el modelo de computación que usa una computadora cuántica y el modelo de Turing?

La máquina Quantum Turing es uno de los modelos para el cálculo cuántico, y es probablemente la forma más fácil de comprender las diferencias con la máquina Turing convencional. Como se hace típicamente en la computación cuántica, 0s y 1s son reemplazados por estados cuánticos de dos niveles, que colapsan a uno de esos niveles cuando se miden. La parte difícil de trabajar con estados cuánticos es que los estados multibit (que generalizan el 00111 convencional) no se pueden dividir en bits individuales cuando están enredados (lo cual es típico). Este es un efecto de “tiempo de ejecución” y no corresponde a ningún “cable” adicional que conecte los bits.

En una computadora cuántica, solo puede pasar por referencia porque la copia no está permitida (a menos que copie en un bloc de notas con inicialización 0). Puede modificar una variable o intercambiar dos valores, pero no puede simplemente escribir un valor arbitrario en una variable, a menos que sepa que la variable se inicializó en 0. Si dos variables físicamente diferentes están enredadas, cambiar una puede cambiar automáticamente la otra. Por ejemplo, si algo le sucede a una variable intermedia que usó hace un tiempo, esto puede corromper todo el cálculo.

El poder de la computación cuántica se puede rastrear hasta el efecto de la superposición cuántica : puede representar muchos estados convencionales a la vez (más o menos) y operar en todos ellos con una instrucción a la vez. El problema es que no puede leer todos los resultados, solo puede recopilar estadísticas (como la suma de los resultados). Esto es útil para algunos problemas. Digamos que en la factorización de números cuánticos puede tomar una superposición de todos los números de 1000 bits y hacer algunas operaciones aritméticas en ellos. Al final, puede producir aproximadamente 1000 bits de información (que es mucho más pequeña que una por número posible). Elegir sabiamente esos bits conduce a algoritmos útiles.

Hay dos sentidos en los que los informáticos hablan de que una computadora puede “hacer” algo. El primero describe las operaciones físicas que realiza una computadora: copie estos datos allí, sume estos números y así sucesivamente. En este sentido, Igor Markov tiene una buena visión general de qué es un QTM y qué operaciones puede realizar.

El segundo, en el sentido de la teoría de la computabilidad, describe los problemas que una computadora podría resolver, no en un solo paso, sino después de un número (finito) de operaciones más pequeñas. En este sentido, Quora User tiene razón en que un QTM puede resolver exactamente los mismos problemas que un TM clásico, ni más ni menos.

Una noción relacionada pregunta no solo si una computadora es capaz de resolver problemas, sino si es capaz de resolverlos (asintóticamente) rápidamente . Es en este sentido que se conocen algoritmos que se cree (¡pero no se prueban!) Para separar las capacidades de las computadoras cuánticas y las clásicas. En general, estas aceleraciones se derivan de la capacidad de realizar operaciones unitarias en superposiciones de estados preparadas adecuadamente. Desafortunadamente, solo puede extraer el resultado de tal “cómputo” enredando ciertos estados y obligando a cancelar las amplitudes de probabilidad, por lo que el cómputo resultante no se parece, como se cree a menudo, a “hacer muchos cómputos paralelos”. modelo conceptual de computación muy diferente.

Bien, eso se volvió muy técnico al final. Lo siento.

Una nota final, no técnica: tiene razón en que no se sabe si existe o no un algoritmo clásico de tiempo polinómico para la factorización, y esto no se puede enfatizar lo suficiente. Si bien nadie ha descubierto uno todavía, no se ha demostrado que su existencia sea imposible, y de hecho, no hay pruebas de que las computadoras cuánticas sean capaces de resolver cualquier problema más rápido que las clásicas.

Ahora, la comunidad de la teoría de la complejidad sospecha que lo son, pero nadie ha demostrado aún un problema en el que podamos demostrar que no hay un algoritmo clásico que sea tan rápido como nuestros mejores cuánticos, todo lo que sabemos. lejos es que es fácil hacer que las computadoras cuánticas vayan rápido.

Debería consultar la página wiki sobre algoritmos Quantum, que dice en parte:

Todos los problemas que pueden resolverse en una computadora cuántica pueden resolverse en una computadora clásica. En particular, los problemas que son indecidibles usando computadoras clásicas permanecen indecidibles usando computadoras cuánticas. Lo que hace que los algoritmos cuánticos sean interesantes es que podrían resolver algunos problemas más rápido que los algoritmos clásicos.