Algoritmos cuánticos y la estructura necesaria

En post forma parte de una serie de posts que describen los algoritmos cuánticos, su diferencia con los clásicos y qué estructura deben tener los problemas para que estos algoritmos puedan conseguir una mejora exponencial.

ALGORITMOS CUÁNTICOS Y DIFERENCIA CON LOS CLÁSICOS

Un algoritmo es una serie finita de instrucciones realizadas para resolver un problema específico. La complejidad computacional estudia el consumo asintótico de recursos necesarios (tiempo o espacio) en función de la entrada (número de bits de la entrada).

Un algoritmo clásico es un algoritmo en el que la serie de instrucciones realizadas y la salida sólo dependen de la entrada o cualquier variable auxiliar introducida. En este sentido, para la misma entrada y variables auxiliares, produciría siempre la misma salida.

Un algoritmo aleatorio es un algoritmo clásico que emplea alguna fuente de aleatoriedad como parte de sus instrucciones. Por ejemplo, se pueden usar bits aleatorios como entrada auxiliar para que el algoritmo se comporte mejor en el caso medio sobre todas las posibles entradas aleatorias.

Un algoritmo cuántico es un algoritmo realizado en un computador cuántico en el cual los estados representan una superposición de estados físicos, el algoritmo realiza transformaciones lineales y unitarias de los estados que permiten una interferencia constructiva o destructiva entre los estados físicos y el resultado del algoritmo es una nueva superposición de los estados físicos, asignando más probabilidad al estado que representa la solución del problema.

Por ejemplo, tenemos el problema representado por la función si y sólo si , en el que hay que encontrar . Un algoritmo clásico debería evaluar la función en todo el dominio de la entrada en el peor de los casos para encontrar la entrada correcta.

El algoritmo cuántico de Grover consigue una mejora cuadrática, necesitando sólo hacer evaluaciones de la función. Esto es posible porque en cada evaluación, el algoritmo cuántico es capaz de acceder a la función en todo el dominio y detectar el valor de . No basta sólo con el paralelismo que permite acceder a todo el dominio en una sola evaluación, ya que cuando midamos el sistema colapsará a cualquier estado con la misma probabilidad. Por eso es necesario aplicar una serie de transformaciones lineales para que el estado final se corresponda con la solución con una probabilidad alta.

EL EFECTO KICKBACK COMO ELEMENTO BÁSICO DE LOS ALGORITMOS CUÁNTICOS

VENTAJA CUÁNTICA Y ESTRUCTURA DE LOS PROBLEMAS

Algunos algoritmos como el de Deutsch a menudo se denominan problemas de promesa, en los que el espacio de la solución tendrá alguna estructura y usando cuidadosamente la superposición, el entrelazamiento y la interferencia podemos extraer información sobre esa estructura.

La razón por la que estos problemas obtienen una mejora exponencial sobre todos los algoritmos clásicos conocidos es que calculamos cada punto utilizando el paralelismo cuántico, mientras que clásicamente uno tiene que calcular cada punto en el espacio de solución para obtener un conocimiento completo sobre esta estructura.

Sin embargo, hay problemas en los que queremos encontrar el x que da f(x) con la propiedad deseada, como el problema de búsqueda. En este tipo de problema no hay una restricción previa. Hasta ahora, los algoritmos cuánticos solo pueden proporcionar mejoras cuadráticas a tales problemas basados ​​en consultas.

Entonces, para que haya una ventaja cuántica exponencial se tienen que dar los siguientes requisitos:

• El problema debe tener cierta estructura que pueda ser accedida por el algoritmo cuántico usando la superposición, el entrelazado y la interferencia. Por ejemplo, el algoritmo de Shor para factorizar un número entero aprovecha la estructura periódica del problema.
• Un algoritmo clásico no puede acceder fácilmente a dicha estructura y por lo tanto no puede resolver el problema en tiempo polinómico.