1. ¿QUE ES?
1.1. La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se basa en el uso de cúbits en lugar de bits, y da lugar a nuevas puertas lógicas que hacen posibles nuevos algoritmos. Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica, lo que ha dado lugar a una gran expectación, ya que algunos problemas intratables pasan a ser tratables. Mientras que un computador clásico equivale a una máquina de Turing,1 un computador cuántico equivale a una máquina de Turing cuántica.
2. ORIGEN DE LA COMPUTACION CUANTICA
2.1. La idea de computación cuántica surge en 1981, cuando Paul Benioff expuso su teoría para aprovechar las leyes cuánticas en el entorno de la computación. En vez de trabajar a nivel de voltajes eléctricos, se trabaja a nivel de cuanto. En la computación digital, un bit solo puede tomar dos valores: 0 o 1. En cambio, en la computación cuántica, intervienen las leyes de la mecánica cuántica, y la partícula puede estar en superposición coherente: puede ser 0, 1 y puede ser 0 y 1 a la vez (dos estados ortogonales de una partícula subatómica). Eso permite que se puedan realizar varias operaciones a la vez, según el número de cúbits. El número de cúbits indica la cantidad de bits que pueden estar en superposición. Con los bits convencionales, si se tenía un registro de tres bits, había ocho valores posibles y el registro solo podía tomar uno de esos valores. En cambio, si se tenía un vector de tres cúbits, la partícula puede tomar ocho valores distintos a la vez gracias a la superposición cuántica. Así, un vector de tres cúbits permitiría un total de ocho operaciones paralelas. Como cabe esperar, el número de operaciones es exponencial con respecto al número de cúbits.
3. MODELOS
3.1. Computadora cuántica de Benioff
3.1.1. La computadora cuántica de Benioff es una idea de que la cinta de la máquina de Turing podría ser reemplazada por una secuencia de sistemas cuánticos simples de dos-estados creada por Paul Benioff. Esto proporcionó una manera primitiva de codificar una secuencia de dígitos binarios. De manera similar, el cabezal de la máquina de Turing fue reemplazado por una interacción cuántica mecánica que podía leer o resetear el valor del estado del espín. Las reglas fueron reemplazadas por una ecuación de Schrödinger diseñada de forma que una configuración inicial de espines evolucionara a un conjunto final de espines que se pudieran descodificar en bits resultado del cálculo en cuestión.
3.2. Computadora cuántica de Feynman
3.2.1. El modelo de Feynman es una versión cuántica de un circuito lógico combinacional. Se describe la computación a realizar a nivel de circuito, construyéndolo con puertas cuánticas reversibles. En general, podemos entender el circuito como k puertas lógicas actuando sobre m qubits. La transformación conseguida por el circuito puede ser escrita como Ak·Ak-1·...·Ai, donde Ai es un operador que describe la acción de la puerta i-ésima.Para realizar la composición de matrices Ai hacemos lo siguiente: Sean los |n| átomos del registro. Añadimos un conjunto nuevo de |k+1| átomos que configuran lo que vamos a llamar el contador de posiciones del programa. Denotamos como <qi> al operador de aniquilación de la posición |i| y como <q*i> al operador de creación de la posición |i|, de tal forma que ambos operan desde |i = 0| hasta |i = k|. Necesitamos ahora un electrón cambiando continuamente de una posición a otra. Así, si en un instante dado una posición está vacía el estado de esa posición es |0>, y si en un estado dado una posición está ocupada el estado de esa posición es |1>. Con este planteamiento Feynman propone como Hamiltoniano: H = SUMA (i=0 -> k-1) <q*i+1> <qi> Ai+1 + Complejo Conjugado
3.3. Computadora cuántica de Deutsch
3.3.1. La primera máquina de Turing cuántica verdadera fue descubierta por David Deutsch. Su modelo se diferencia del de la Benioff en que mantiene el registro de memoria cuántico (la cinta) en superposición de estados computacionales. El operador U de evolución temporal tiene que ser local, envolviendo sólo interacciones entre qubits adyacentes, e independiente del tiempo. Esto asegura que, en cada paso computacional, sólo interactúan qubits adyacentes y la computación tiene un tiempo de finalización bien definido. Para lograrlo es necesario un hamiltoniano dependiente del tiempo.