¿Las computadoras cuánticas son máquinas de Turing?

Por favor, tengan paciencia conmigo mientras vuelvo sobre algunos antecedentes (que casi seguramente ya saben):

Hay muchos trabajos, que involucran N objetos (N grupos de datos) para los que podemos diseñar algoritmos en computadoras convencionales, y cuyos tiempos de ejecución son del orden de algunos polinomios: [matemáticas] T_ {exec} = O (N ^ { k}) [/ math] donde k es un número pequeño.

No sin razón, cuanto mayor es el valor de N, mayor es el tiempo de ejecución, pero crece lo suficientemente suave como para que, si las computadoras de hoy no son lo suficientemente rápidas para ejecutar el algoritmo en el conjunto de datos elegido (de tamaño N), entonces tal vez todo lo que hay que hacer es esperar las computadoras de mañana.

El ejemplo clásico es ordenar una lista de N enteros en orden ascendente, lo que puede tomar [math] T_ {exec} = O (N ^ {2}) [/ math] para un algoritmo escrito de manera bastante simple, pero puede obtener esto abajo a [matemáticas] T_ {exec} = O (N.ln (N)) [/ matemáticas] si es inteligente.

El problema es que hay muchos algoritmos que no son polinómicos, sino que crecen combinatoriamente. Elegir ejemplos de mosaicos de varias formas para revestir una pared, o diseñar el horario de enseñanza de una semana para la universidad, o la coincidencia de patrones, o intentar factorizar números enteros grandes, o el problema del vendedor ambulante son ejemplos. El tiempo de ejecución de estos también aumenta a medida que aumenta el valor de N, pero de una manera mucho más agresiva. [matemática] T_ {exec} = O (N!) [/ ​​matemática], que, según la aproximación de Stirling, es [matemática] T_ {exec} = O (N ^ {N + 1/2} .e ^ {- N })[/mates]

Estos son los que frustran las computadoras convencionales simplemente por la forma en que sus tiempos de ejecución se vuelven astronómicos.

Las computadoras cuánticas prometen darnos una manera de abordar estos problemas con algoritmos que reducen a ser polinomiales. Todavía tardan más en ejecutarse, cuanto mayor es el valor de N, pero vuelven de una manera mucho menos agresiva.

Entonces, en conclusión, las computadoras cuánticas no prometen hacer nada que las computadoras convencionales no puedan hacer, solo para poder hacerlo dentro del horario de almuerzo del usuario humano, en lugar de más tiempo que el tiempo de vida del universo conocido. .

Gran pregunta Las máquinas de Turing son tan simples, tal vez pueda obtener una mejor comprensión de la programación de computadoras cuánticas al profundizar en la estructura de la máquina Quantum T. ¡INCORRECTO!

Después de ir a mis fuentes favoritas, volví al pionero David Deutsch por su perspicacia. http://www.jstor.org/stable/2397601 Incluso allí, los paywalls ocultaron mucho de lo que podría ser útil.
Después de pasar por alto una gran cantidad de jerga cuántica que expresa conceptos de ciencia computacional, parece que una versión cuántica de Turing usaría el espacio de Hilbert para la representación de sus estados y las reglas de transición de estado. Concluyo que si bien requeriría un tiempo de funcionamiento masivamente más largo que una máquina clásica podría emular; En principio, una máquina clásica de Turing para producir los mismos resultados. Del documento de Deutsch:

Se argumenta que subyacente a la hipótesis de Church-Turing hay una afirmación física implícita. Aquí, esta afirmación se presenta explícitamente como un principio físico: “todo sistema físico finitamente realizable puede ser perfectamente simulado por una máquina de cómputo modelo universal que funciona por medios finitos”. La física clásica y la máquina universal de Turing, porque la primera es continua y la segunda discreta, no obedecen el principio, al menos en la forma fuerte anterior.

y

Las máquinas de computación que se asemejan a la computadora cuántica universal podrían, en principio, construirse y tendrían muchas propiedades notables que ninguna máquina de Turing puede reproducir. Estos no incluyen el cálculo de funciones no recursivas, pero sí incluyen el `paralelismo cuántico ‘, un método por el cual ciertas tareas probabilísticas pueden realizarse más rápidamente por una computadora cuántica universal que por cualquier restricción clásica de la misma.

http://www.jstor.org/stable/2397601 Quantum Theory, the Church-Turing Principle y Universal Quantum Computer de Deutsch.

La visión de un teórico de la complejidad de la computación cuántica proporciona una explicación casi comprensible de lo que se sabe acerca de los problemas computacionales cuánticos de manera eficiente que él llama molestamente BQP sin definir ese término.

Una computadora cuántica puede modelarse como una máquina cuántica de Turing. Básicamente es una máquina de Turing donde los estados en los que puede estar la máquina son estados cuánticos, es decir, vectores en un espacio de Hilbert. De esta manera, la máquina puede estar en una superposición de estados.

Consulte el artículo de Wikipedia para obtener más información.

Depende de lo que quieras decir con “las reglas básicas que Turing imaginó”.

[math] \ text {\ sf BQP} [/ math] está contenido en [math] \ text {\ sf EXP} [/ math] y, en general, [math] \ text {\ sf BQ \ mathbf X} [ / math] está contenido en [math] \ text {\ sf \ mathbf X ^ {EXP}} [/ math]. Por lo tanto, una computadora cuántica no puede calcular nada que una computadora clásica (o una implementación de Turing Machine) no podría.

Por otro lado, no se sabe si [math] \ text {\ sf BQP} = \ text {\ sf P} [/ math], lo que significaría que “cualquier cosa que una computadora cuántica pueda calcular en un polinomio número de pasos, una computadora clásica también podría “. Se cree que esto es cierto, pero estamos lejos de ser una prueba.

Una característica de los TM es que (según la tesis de Church-Turing), son capaces de calcular cualquier cosa que se pueda calcular, que QC no cambia, pero otra es que pueden calcular en tiempo polinómico cualquier cosa que se pueda calcular en polinomio tiempo – qué control de calidad podría

Sí. La base de la teoría cuántica todavía se escribe en ZFC en lógica de segundo orden, que se puede calcular en una máquina Turing.

ZFC es un sistema axiomático formal en lógica de segundo orden. La lógica de segundo orden es la lógica que permite la cuantificación sobre predicados, lo que le permite definir cosas buenas como números reales que permiten el cálculo y las ecuaciones diferenciales en las que se basa la mecánica cuántica.

Ahora, se pone un poco peludo cuando comienzas a considerar los infinitos. ¿Qué significa que un infinito es computable? Bueno, significa que si sigue un conjunto específico de reglas sintácticas sobre cómo se supone que debe comportarse este infinito, obtendrá el resultado que espera. En la mayoría de los casos, en física, el infinito es una declaración sobre nuestra ignorancia. Cuando vamos a calcular, generalmente usamos grandes cantidades finitas … como 10 (sí, eso es una broma de física). Es exactamente de la misma manera que podemos hablar sobre un círculo perfecto, aunque en realidad no existan círculos perfectos. Lo que sucede en realidad es que todos los infinitos se “cancelan” en algún sentido. Es por eso que, cuando un físico encuentra una teoría con un infinito que no se cancela, tienen una gran pista de que la teoría está equivocada.

Desafortunadamente, esa es la circunstancia actual en la que nos encontramos al considerar teóricamente las singularidades en los agujeros negros. Como Michio Kaku lo explica, de hecho, tenemos una infinidad de infinitos sumados. Entonces, básicamente, tenemos un pequeño problema con nuestra teoría actual. Tal vez algunos físicos jóvenes y brillantes del futuro eventualmente descubran cómo solucionarlo y vincular adecuadamente la QM y la Relatividad General.

No, las computadoras cuánticas y las máquinas de Turing son modelos significativamente diferentes. Una máquina de Turing implica una cinta que se divide en regiones que tienen diferentes símbolos en ellas. Un autómata finito se mueve a lo largo de esta cinta y lee y escribe símbolos de un alfabeto finito. Los modelos de computadoras cuánticas, como los circuitos cuánticos, permiten operaciones unitarias en la superposición de estados, así como mediciones probabilísticas de estos estados.

La tesis de Church-Turing discute el poder computacional de diferentes modelos de computación. La cita que da dice que una computadora cuántica puede resolver los mismos problemas que una máquina de Turing (y máquinas de mostrador, autómatas celulares, cálculo lambda y muchos otros). El hecho de que dos cosas sean computacionalmente equivalentes no significa que sean iguales o que puedan calcular las respuestas a las preguntas en la misma cantidad de tiempo.

En mi opinión, uno no debería preguntar si una computadora cuántica es una máquina de Turing. Claramente, este no es el caso, ya que las dos nociones son diferentes, así como sería un error decir que una expresión en el cálculo lambda sin tipo es una máquina de Turing.

La verdadera pregunta es la del poder computacional. Vea las diapositivas de una charla de Ashley Montanaro sobre este tema.

No, no lo creo. Si bien cualquier máquina completa de Turing puede emular una computadora cuántica, no creo que lo contrario sea cierto. Creo que las computadoras cuánticas, como se prevé actualmente, solo pueden resolver ciertas clases de problemas numéricos. Tendrían que tener un arnés no cuántico a su alrededor, esencialmente un procesador completo Turning por derecho propio, para realizar operaciones como el control de flujo.

El punto que el artículo está haciendo no es que las computadoras cuánticas estén completas en Turing, sino que no están haciendo algo místico que una computadora convencional no podría hacer, simplemente haciéndolo increíblemente mucho más rápido.

Creo que puedes construir una computadora cuántica que se adhiera a la tesis de la Iglesia Turing. Sin embargo, el campo de la computación cuántica es tan joven que quizás podría usarse para construir máquinas que no lo son.