Análisis

Ahora analizaremos el algoritmo de Grover para entender cómo funciona. Empezaremos con lo que podría describirse como un análisis simbólico, en el que calculamos cómo actúa la operación Grover $G$ sobre determinados estados, y luego vincularemos este análisis simbólico a una imagen geométrica útil para visualizar cómo funciona el algoritmo.

---

Soluciones y no soluciones

Empecemos por definir 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 a nuestro problema de búsqueda, mientras que $A_0$ contiene las cadenas que no son soluciones (a las que podemos referirnos 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 que se trata de una bipartición de $\Sigma^n.$

A continuación definiremos 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 sólo está definido cuando su conjunto correspondiente no es vacío, pero a partir de ahora nos centraremos en el caso de que ni $A_0$ ni $A_1$ estén vacíos. Los casos que $A_0 = \varnothing$ y $A_1 = \varnothing$ son fáciles de tratar por separado, y lo haremos más adelante.

Como apunte, la notación que se utiliza aquí es común: siempre que tengamos un conjunto finito y no vacío $S,$ podemos escribir $\vert S\rangle$ para denotar el vector de estado cuántico que es uniforme sobre los elementos de $S.$

Definamos también $\vert u \rangle$ como un estado cuántico uniforme sobre todas las cadenas de $n$ -bit:

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

Observe 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,$ así 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 justo antes de que se produzcan las iteraciones de $G$ en el paso 2, el estado de $\mathsf{Q}$ está contenido en el espacio vectorial bidimensional abarcado por $\vert A_0\rangle$ y $\vert A_1\rangle,$ y además los coeficientes de estos vectores son números reales. Como veremos, el estado de $\mathsf{Q}$ siempre tendrá estas propiedades -lo que significa que el estado es una combinación lineal real de $\vert A_0\rangle$ y $\vert A_1\rangle$ - después de cualquier número de iteraciones de la operación $G$ en el paso 2.

---

Una observación sobre la operación Grover

Ahora vamos a centrar nuestra atención en la operación Grover

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

comenzando con una interesante observación al respecto.

Imaginemos por un momento que sustituimos la función $f$ por la composición de $f$ con la función NOT -o, en otras palabras, la función que obtenemos volteando el bit de salida de $f.$ Llamaremos a esta nueva función $g,$ y podemos expresarla mediante símbolos 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}$$

Observe que

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

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

$$Z_g = - Z_f.$$

Esto significa que si sustituyéramos la función $f$ por la función $g,$ el algoritmo de Grover no funcionaría de forma diferente - porque los estados que obtenemos del algoritmo en los dos casos son necesariamente equivalentes hasta una fase global.

¡Esto no es un problema! Intuitivamente, al algoritmo no le importa qué cadenas son soluciones y cuáles no, sólo necesita poder distinguir entre soluciones y no soluciones para funcionar correctamente.

---

Acción de la operación Grover

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

En primer lugar, observemos 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}$$

En segundo lugar, 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}$$

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

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

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

Por tanto, la operación $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ puede escribirse así:

$$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},$$

utilizando la misma notación, $\vert u \rangle,$ que utilizamos anteriormente para la superposición uniforme sobre todas las cadenas de $n$ -bit.

Y ahora tenemos lo que necesitamos para calcular la acción de $G$ sobre $\vert A_0\rangle$ y $\vert A_1\rangle.$ Primero calculemos 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, calculemos 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 utilizamos 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

$$\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}}$$

que siguen.

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 está contenido en el espacio bidimensional abarcado por $\vert A_0\rangle$ y $\vert A_1\rangle,$ y acabamos de establecer que $G$ mapea cualquier vector de este espacio a otro vector del mismo espacio. Esto significa que, en aras del análisis, podemos centrar nuestra atención exclusivamente en este subespacio.

Para comprender mejor lo que ocurre en este espacio bidimensional, expresemos la acción de $G$ sobre 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},$$

cuyas primera y segunda filas/columnas corresponden a $\vert A_0\rangle$ y $\vert A_1\rangle,$ respectivamente. Hasta ahora en esta serie, siempre hemos relacionado las filas y columnas de las matrices con los estados clásicos de un sistema, pero las matrices también se pueden utilizar para describir las acciones de los mapeos lineales sobre diferentes bases como tenemos aquí.

Aunque no resulte evidente a primera vista, la matriz $M$ es la que obtenemos elevando al cuadrado una matriz de aspecto más sencillo.

$$\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 podemos expresar alternativamente 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}$$

para

$$\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, por lo que merece la pena subrayar su importancia aquí, ya que lo vemos por primera vez.

A la luz de la 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 se debe a que girar dos veces el ángulo $\theta$ equivale a girar el ángulo $2\theta.$ Otra forma de ver esto es hacer uso de la expresión alternativa

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

junto con las fórmulas de á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 inicio 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 un ángulo $2\theta$ dentro del espacio abarcado por $\vert A_0\rangle$ y $\vert A_1\rangle.$ Así, 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

Ahora vamos a conectar el análisis que acabamos de hacer 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 realizar dos reflexiones es realizar una rotación.

Empecemos por $Z_f.$ Como ya hemos observado anteriormente, tenemos

$$\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}$$

Dentro del espacio vectorial bidimensional abarcado por $\vert A_0\rangle$ y $\vert A_1\rangle,$ se trata de una reflexión sobre la recta paralela a $\vert A_0\rangle,$ que llamaremos $L_1.$ He aquí una figura que ilustra la acción de esta reflexión sobre un hipotético vector unitario $\vert\psi\rangle,$ que suponemos es una combinación lineal real de $\vert A_0\rangle$ y $\vert A_1\rangle.$

En segundo lugar tenemos la operación $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ que ya hemos visto que se puede escribir como

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

Se trata también de una reflexión, esta vez sobre la recta $L_2$ paralela al vector $\vert u\rangle.$ He aquí una figura que representa 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 líneas de reflexión - como ilustra esta figura.

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