Análisis

Ahora analizamos el algoritmo de Grover para entender cómo funciona. Comenzamos con lo que podría describirse como un análisis simbólico, en el que calculamos cómo la operación de Grover $G$ actúa sobre ciertos estados, y luego conectamos este análisis simbólico con una imagen geométrica que ayuda a visualizar el funcionamiento del algoritmo.

Soluciones y no soluciones

Comencemos definiendo dos conjuntos de cadenas.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

El conjunto $A_1$ contiene todas las soluciones de nuestro problema de búsqueda, mientras que $A_0$ contiene las cadenas que no son soluciones (a las que nos referiremos como no soluciones cuando sea conveniente). Estos dos conjuntos satisfacen $A_0 \cap A_1 = \varnothing$ y $A_0 \cup A_1 = \Sigma^n$, es decir, esto es una bipartición de $\Sigma^n$.

A continuación, definimos dos vectores unitarios que representan superposiciones uniformes sobre los conjuntos de soluciones y no soluciones.

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

Formalmente, cada uno de estos vectores solo está definido si el conjunto correspondiente no está vacío, pero a continuación nos enfocamos en el caso en que ni $A_0$ ni $A_1$ están vacíos. Los casos $A_0 = \varnothing$ y $A_1 = \varnothing$ pueden tratarse fácilmente por separado, lo cual haremos más adelante.

Como nota al margen: la notación utilizada aquí es común — siempre que tenemos un conjunto finito y no vacío $S$, podemos escribir $\vert S\rangle$ para denotar el vector de estado cuántico distribuido uniformemente sobre los elementos de $S$.

Definamos además $\vert u \rangle$ como el estado cuántico uniforme sobre todas las cadenas de $n$ bits:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Observa que

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

También tenemos que $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$, por lo que $\vert u\rangle$ representa el estado del registro $\mathsf{Q}$ después de la inicialización en el paso 1 del algoritmo de Grover.

Esto implica que el estado de $\mathsf{Q}$ inmediatamente antes de las iteraciones de $G$ en el paso 2 se encuentra en el espacio vectorial bidimensional generado por $\vert A_0\rangle$ y $\vert A_1\rangle$, y que los coeficientes de estos vectores son números reales. Como veremos, estas propiedades del estado — que es una combinación lineal real de $\vert A_0\rangle$ y $\vert A_1\rangle$ — se preservarán después de cualquier número de iteraciones de la operación $G$ en el paso 2.

Una observación sobre la operación de Grover

Ahora nos dirigimos a la operación de Grover:

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

comenzando con una observación interesante al respecto.

Imaginemos brevemente que reemplazamos la función $f$ por la composición de $f$ con la función NOT — o dicho de otra manera, por la función que obtenemos al invertir el bit de salida de $f$. Llamamos a esta nueva función $g$ y podemos expresarla simbólicamente de varias formas alternativas.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Observa que

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

para cada cadena $x\in\Sigma^n$ y, por lo tanto,

$$Z_g = - Z_f.$$

Esto significa que si reemplazáramos la función $f$ por la función $g$, el algoritmo de Grover no funcionaría de manera diferente — porque los estados que obtenemos del algoritmo en ambos casos son necesariamente equivalentes salvo una fase global.

¡Esto no es un problema! Intuitivamente hablando, al algoritmo no le importa qué cadenas son soluciones y cuáles no — solo necesita poder distinguir las soluciones de las no soluciones para funcionar correctamente.

Acción de la operación de Grover

Consideremos ahora la acción de $G$ sobre los vectores de estado cuántico $\vert A_0\rangle$ y $\vert A_1\rangle$.

Primero, observamos que la operación $Z_f$ tiene una acción muy simple sobre $\vert A_0\rangle$ y $\vert A_1\rangle$.

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

Segundo, tenemos la operación $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. La operación $Z_{\mathrm{OR}}$ se define como

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

nuevamente para cada cadena $x\in\Sigma^n$, y una forma alternativa conveniente de expresar esta operación es:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

Una forma sencilla de verificar que esta expresión coincide con la definición de $Z_{\mathrm{OR}}$ consiste en evaluar su acción sobre estados de la base estándar.

La operación $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ puede entonces escribirse como:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

donde usamos la misma notación $\vert u \rangle$ que antes para la superposición uniforme sobre todas las cadenas de $n$ bits.

Y ahora tenemos lo que necesitamos para calcular la acción de $G$ sobre $\vert A_0\rangle$ y $\vert A_1\rangle$. Primero calculamos la acción de $G$ sobre $\vert A_0\rangle$.

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

Y segundo, calculamos la acción de $G$ sobre $\vert A_1\rangle$.

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

En ambos casos usamos la ecuación

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

junto con las expresiones que se derivan de ella

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

En resumen, tenemos

En resumen, tenemos

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Como ya hemos señalado, el estado de $\mathsf{Q}$ justo antes del paso 2 se encuentra en el espacio bidimensional abarcado por $\vert A_0\rangle$ y $\vert A_1\rangle$, y acabamos de establecer que $G$ mapea cualquier vector en este espacio a otro vector en el mismo espacio. Esto significa que, para propósitos del análisis, podemos enfocar nuestra atención exclusivamente en este subespacio.

Para entender mejor qué está sucediendo dentro de este espacio bidimensional, expresemos la acción de $G$ en este espacio como una matriz,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

cuya primera y segunda filas/columnas corresponden a $\vert A_0\rangle$ y $\vert A_1\rangle$, respectivamente. Hasta ahora en esta serie, siempre hemos conectado las filas y columnas de las matrices con los estados clásicos de un sistema, pero las matrices también pueden usarse para describir las acciones de aplicaciones lineales sobre diferentes bases, como en este caso.

Aunque no es en absoluto obvio a primera vista, la matriz $M$ es lo que obtenemos al elevar al cuadrado una matriz de apariencia más simple.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

La matriz

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

es una matriz de rotación, que alternativamente podemos expresar como

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

for

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr).$$

Este ángulo $\theta$ va a desempeñar un papel muy importante en el análisis que sigue, así que vale la pena resaltar su importancia aquí al verlo por primera vez.

A la luz de esta expresión de esta matriz, observamos que

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

Esto ocurre porque rotar por el ángulo $\theta$ dos veces es equivalente a rotar por el ángulo $2\theta$. Otra forma de ver esto es utilizar la expresión alternativa

$$\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),$$

junto con las fórmulas del ángulo doble de la trigonometría:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

En resumen, el estado del registro $\mathsf{Q}$ al comienzo del paso 2 es

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

y el efecto de aplicar $G$ a este estado es rotarlo por un ángulo $2\theta$ dentro del espacio abarcado por $\vert A_0\rangle$ y $\vert A_1\rangle$. Entonces, por ejemplo, tenemos

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

y en general

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle.$$

Imagen geométrica

Conectemos ahora el análisis que acabamos de realizar con una imagen geométrica. La idea es que la operación $G$ es el producto de dos reflexiones: $Z_f$ y $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. Y el efecto neto de dos reflexiones es una rotación.

Comencemos con $Z_f$. Como ya observamos anteriormente,

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

En el espacio vectorial bidimensional generado por $\vert A_0\rangle$ y $\vert A_1\rangle$, esto es una reflexión respecto a la recta paralela a $\vert A_0\rangle$, que llamaremos $L_1$. Aquí hay una figura que ilustra la acción de esta reflexión sobre un vector unitario hipotético $\vert\psi\rangle$, que se asume como una combinación lineal real de $\vert A_0\rangle$ y $\vert A_1\rangle$.

Segundo, tenemos la operación $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$, que ya sabemos que puede escribirse como

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Esto también es una reflexión, esta vez respecto a la recta $L_2$ paralela al vector $\vert u\rangle$. Aquí hay una figura que muestra la acción de esta reflexión sobre un vector unitario $\vert\psi\rangle$.

Cuando componemos estas dos reflexiones, obtenemos una rotación — por el doble del ángulo entre las rectas de reflexión — como muestra esta figura.

Esto explica en términos geométricos por qué el efecto de la operación de Grover es rotar combinaciones lineales de $\vert A_0\rangle$ y $\vert A_1\rangle$ por un ángulo de $2\theta$.