Algoritmo de Grover
Primero haré Grover ya que es más simple. Comencemos con algunos antecedentes sobre lo que hace:
El algoritmo de Grover resuelve el problema de búsqueda . Un ejemplo concreto sería resolver la factorización; para factorizar un número entero n, buscando un par (a, b) con la propiedad que ab = n. (Esto no es tan rápido como usar el algoritmo de Shor para factorizar, pero sigue siendo un ejemplo conveniente).
- ¿Es teóricamente posible almacenar qubits al nivel de partículas subatómicas?
- ¿Cuál es una buena explicación del tipo de tono de ascensor (30-60 segundos) de la computación cuántica y los beneficios de crear dicho dispositivo?
- ¿Cuánta mecánica cuántica debes aprender para poder construir una computadora cuántica (D-Wave)?
- ¿Puedes reducir la física cuántica a una oración?
- ¿Cómo es la Universidad de Waterloo para estudios de posgrado en computación cuántica, siendo una de las pocas universidades con programas de posgrado explícitos?
Sin embargo, Grover’s es mucho más general. Podemos abstraerlo de la siguiente manera. Supongamos que tenemos N objetos para buscar, que etiquetaremos con los números 1, …, N, y una forma de verificar de manera eficiente si algún elemento dado es el elemento que estamos buscando. Es decir, tenemos una función f tal que f (i) siempre devuelve si i es “la respuesta correcta”. Con una computadora clásica, tenemos que verificar todos los N objetos individualmente para encontrar el que estamos buscando.
para i en [1..N]:
si f (i):
regreso yo
No podemos hacer nada mejor que esto sin explotar alguna estructura especial de f.
El algoritmo de Grover puede resolver este problema con solo [matemáticas] O (\ sqrt {N}) [/ matemáticas] “llamadas cuánticas” a f. Esto ha demostrado ser óptimo, de hecho.
Aquí está la idea básica. En el modelo de computación cuántica, podemos preparar un estado que es la superposición sobre todos los valores 1, …, N. Este estado se escribiría como
[matemáticas] \ vert x \ rangle = \ frac {1} {\ sqrt {N}} \ left (\ vert 1 \ rangle + \ dotsb + \ vert N \ rangle \ right) [/ math]
La [matemática] \ vert x \ rangle [/ matemática] se llama notación ket y es solo la forma en que escribimos estados cuánticos. La [matemática] 1 / \ sqrt {N} [/ matemática] significa que si tuviéramos que medir el estado, obtendríamos cualquiera de 1, …, N, cada uno con probabilidad [matemática] 1 / N [/ matemática ] Es tentador pensar en este estado como “está en todos los estados a la vez”. Sin embargo, esa no es una buena manera de verlo. No está en estado [matemática] \ vert 1 \ rangle [/ matemática] o [matemática] \ vert 2 \ rangle [/ matemática], etc. en absoluto. Es el estado [matemáticas] \ vert x \ rangle [/ matemáticas]. Cuando lo mides, se derrumba a uno de esos estados “puros”. La mejor manera de pensarlo como un vector N-dimensional, es decir, solo una secuencia de N números:
[matemáticas] (1 / \ sqrt {N}, \ cdots, 1 / \ sqrt {N}) [/ matemáticas].
Este estado por sí solo no es muy útil hasta que realmente hagamos algo con él. Realmente necesitamos hacer uso de f si queremos obtener algo útil.
Idealmente, tendríamos el estado puro [matemática] \ vert i \ rangle [/ matemática], donde i es la respuesta correcta, la mide y obtiene i. Entonces estaríamos listos. Desafortunadamente, la aplicación de f no nos permite saltar inmediatamente a este estado. Aquí hay una visualización de dónde estamos y dónde queremos estar, una porción bidimensional del gran espacio N-dimensional de estados cuánticos:
Estamos en [matemáticas] \ vert x \ rangle [/ matemáticas], pero queremos estar en [matemáticas] \ vert i \ rangle [/ matemáticas]. Desafortunadamente, [math] \ vert x \ rangle [/ math] está muy lejos de [math] \ vert i \ rangle [/ math]; son casi perpendiculares
Bien, ahora usemos nuestra función f. Sin ser demasiado técnico sobre lo que es realmente una “llamada cuántica” a f, solo diré que le permite negar la coordenada i , es decir, reflejar [matemáticas] \ vert x \ rangle [/ matemáticas] sobre la horizontal eje a un nuevo vector, [matemáticas] \ vert x ‘\ rangle [/ matemáticas].
A continuación, puede reflejar [matemáticas] \ vert x ‘\ rangle [/ matemáticas] acerca de [matemáticas] \ vert x [/ matemáticas] a [matemáticas] \ vert x’ ‘\ rangle [/ matemáticas]. Esta es una operación similar a la primera reflexión, aunque no requiere el uso de f.
entonces, ¿qué hicimos? ¡Rotamos [matemáticas] \ vert x \ rangle [/ matemáticas] más cerca de [matemáticas] \ vert i \ rangle [/ matemáticas]! De hecho, cada vez que hacemos esta operación, giraremos nuestro vector en un ángulo [matemático] \ theta [/ matemático] más cercano a [matemático] \ vert i \ rangle [/ matemático]. Entonces, si hacemos esto iterativamente, nuestro estado se acercará más y más a [math] \ vert i \ rangle [/ math]. Es posible que nunca lleguemos a [math] \ vert i \ rangle [/ math] exactamente , pero después de los pasos [math] O (\ sqrt {N}) [/ math], nos acercaremos lo suficiente para que cuando medimos, ‘ Mediremos el estado [matemáticas] \ vert i \ rangle [/ matemáticas] con buena probabilidad.
Algoritmo de Shor
El algoritmo de Shor es mucho más difícil de explicar en términos simples, especialmente porque los detalles de la pregunta me prohíben decir “Transformación cuántica de Fourier”, ya que es esencial aquí, pero lo intentaré.
Probablemente todos conozcan el algoritmo de Shor como un algoritmo para factorizar un número entero n. Tenga en cuenta que Shor’s proporciona un algoritmo de tiempo polinómico, mientras que el uso del algoritmo de Grover para la factorización todavía daría un algoritmo de tiempo exponencial. A Shor le va mejor porque explota una estructura especial de teoría de números.
Ahora, el algoritmo de Shor en realidad resuelve algo un poco más general que solo factorizar: resuelve el problema de búsqueda de períodos . Esto a su vez se usa como una subrutina para factorizar. Usar el hallazgo de períodos para factorizar solo involucra alguna teoría de números elemental. Me saltearé eso, ya que si conoces la teoría de números, puedes leerla en wikipedia.
Este problema de búsqueda de período es: dada una secuencia repetitiva, como
1, 10, 3, 7, 1, 10, 3, 7, 1, 10, 3, 7, 1, 10, 3, 7, 1, 10, 3, 7, …
encuentre el período (en el ejemplo, 4). Asumimos que tenemos acceso a alguna función [matemática] f (i) [/ matemática] que devuelve el elemento i-ésimo de la secuencia.
Como arriba, podemos hacer que el estado sea uniforme
[matemáticas] \ frac {1} {\ sqrt {N}} \ left (\ vert 1 \ rangle + \ dotsb + \ vert N \ rangle \ right) [/ math]
Ahora aplicamos f a este estado, almacenando el resultado en otro registro cuántico. En la notación ket, el resultado se escribiría:
[matemáticas] \ frac {1} {\ sqrt {N}} \ left (\ vert 1 \ rangle \ vert f (1) \ rangle + \ dotsb + \ vert N \ rangle \ vert f (N) \ rangle \ right )[/mates]
Básicamente, lo que esto significa es que si lo medimos, obtendremos un par al azar (i, f (i)), por ejemplo, uno de (1, 1), (2, 10), (3, 3), (4, 7), etc. utilizando el ejemplo anterior. Medirlo directamente no es muy útil. Entonces, en cambio, midamos el segundo registro, el que contiene f (i). Esto devolverá algún valor específico de f (i).
¡Sin embargo, el primer registro seguirá estando en alguna superposición! Estará en una superposición de todo i con el mismo valor de f (i): valores [matemática] a, a + r, a + 2r, … [/ matemática] para alguna a, donde r es el período de f.
[matemáticas] \ frac {1} {M} \ izquierda (\ vert a \ rangle + \ vert a + r \ rangle + \ vert a + 2r \ rangle + \ dotsb \ right) [/ math].
(No te preocupes por el valor de M.)
Este es un estado muy bueno para tener! La función específica f ahora está completamente fuera de la imagen, pero este estado todavía codifica el valor r. Todavía no es obvio cómo podríamos obtener el valor r, ya que cuando medimos este estado, obtendremos un valor aleatorio y perderemos nuestro estado.
El resto se vuelve técnico, pero la idea es usar, sí, la Transformada Cuántica de Fourier para estudiar este estado. Creo que voy a cortar mi explicación aquí; De nuevo, si quieres ver cómo funciona la Transformación Cuántica de Fourier y estás dispuesto a hacer algunos cálculos, puedes leer más en profundidad.
