Elección del número de iteraciones

Hemos establecido que el vector de estado del registro $\mathsf{Q}$ en el algoritmo de Grover permanece en el subespacio bidimensional generado por $\vert A_0\rangle$ y $\vert A_1\rangle$ una vez realizado el paso de inicialización.

El objetivo es encontrar un elemento $x\in A_1$, y este objetivo se logra cuando obtenemos el estado $\vert A_1\rangle$ — porque al medir este estado, obtenemos garantizadamente un resultado de medición $x\in A_1$. Como el estado de $\mathsf{Q}$ después de $t$ iteraciones en el paso 2 es

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

debemos elegir $t$ de modo que

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

sea lo más cercano posible a $1$ en valor absoluto, para maximizar la probabilidad de obtener $x\in A_1$ en la medición. Para cualquier ángulo $\theta \in (0,2\pi)$, el valor $\sin((2t + 1)\theta)$ oscila a medida que $t$ aumenta, pero no es necesariamente periódico — no hay garantía de que obtengamos el mismo valor dos veces.

Naturalmente, además de una alta probabilidad de obtener un elemento $x\in A_1$ de la medición, también queremos elegir $t$ tan pequeño como sea posible, ya que $t$ aplicaciones de la operación $G$ requieren $t$ consultas a la función $f$. Dado que buscamos que $\sin( (2t + 1) \theta)$ sea cercano a $1$ en valor absoluto, un enfoque natural es elegir $t$ de modo que

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

Resolviendo para $t$ obtenemos

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Como $t$ debe ser un entero, no siempre podemos alcanzar exactamente este valor — pero podemos tomar el entero más cercano a este valor, que es

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

Este es el número recomendado de iteraciones para el algoritmo de Grover. A lo largo del análisis, veremos que la cercanía de este entero al valor objetivo afecta el rendimiento del algoritmo.

(Como nota al margen: cuando el valor objetivo $\pi/(4\theta) - 1/2$ cae exactamente a mitad de camino entre dos enteros, esta expresión para $t$ da el redondeo hacia arriba. Alternativamente, se podría redondear hacia abajo, lo cual tiene sentido ya que significa una consulta menos — pero esto es secundario y no tiene importancia para los propósitos de la lección.)

Si recordamos que el valor del ángulo $\theta$ viene dado por la fórmula

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

vemos que el número recomendado de iteraciones $t$ depende del número de cadenas en $A_1$. Esto presenta un desafío cuando no sabemos cuántas soluciones tenemos, como discutiremos más adelante.

Búsqueda única

Concentrémonos primero en la situación en la que hay exactamente una cadena $x$ con $f(x)=1$. Dicho de otro modo, consideramos una instancia del problema de búsqueda única. En este caso tenemos

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

lo cual puede aproximarse convenientemente como

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

cuando $N$ se hace grande. Sustituyendo $\theta = 1/\sqrt{N}$ en la expresión

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

obtenemos

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Como $t$ no es solo el número de ejecuciones de la operación $G$, sino también el número de consultas a la función $f$ que requiere el algoritmo, estamos en camino hacia un algoritmo que requiere $O(\sqrt{N})$ consultas.

Examinemos ahora qué tan bien funciona la elección recomendada de $t$. La probabilidad de que la medición final produzca la solución única puede expresarse explícitamente como

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

El primer argumento, $N$, se refiere al número de elementos sobre los que estamos buscando, y el segundo argumento, aquí $1$, al número de soluciones. Un poco más adelante usaremos la misma notación de manera más general cuando haya múltiples soluciones.

Aquí hay una tabla de probabilidades de éxito para valores crecientes de $N = 2^n$.

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Observa que estas probabilidades no aumentan estrictamente de forma monótona. En particular, hay una anomalía interesante en $N=4$, donde obtenemos una solución con certeza. Sin embargo, puede demostrarse en general que

$$p(N,1) \geq 1 - \frac{1}{N}$$

para todo $N$, de modo que la probabilidad de éxito tiende a $1$ en el límite de $N$ grande, como los valores anteriores parecen confirmar. ¡Esto es bueno!

Pero observa que incluso una cota débil como $p(N,1) \geq 1/2$ demuestra la utilidad del algoritmo de Grover. Para cualquier resultado de medición $x$ que obtengamos al ejecutar el procedimiento, siempre podemos verificar con una sola consulta a $f$ si $f(x) = 1$. Y si con una probabilidad de como máximo $1/2$ no obtenemos la cadena única $x$ con $f(x) = 1$ al ejecutar el procedimiento una vez, entonces después de $m$ ejecuciones independientes no habremos obtenido esta cadena única $x$ con una probabilidad de como máximo $2^{-m}$. Es decir, con $O(m \sqrt{N})$ consultas a $f$ obtenemos la solución única $x$ con una probabilidad de al menos $1 - 2^{-m}$. La mejor cota $p(N,1) \geq 1 - 1/N$ muestra que la probabilidad de encontrar $x\in A_1$ con este método es en realidad al menos $1 - N^{-m}$.

Múltiples soluciones

Con el número de elementos en $A_1$ también varía el ángulo $\theta$, lo cual puede afectar considerablemente la probabilidad de éxito del algoritmo. Por brevedad, escribimos $s = \vert A_1 \vert$ para el número de soluciones, y como antes asumimos que $s\geq 1$.

Como ejemplo motivador, imaginemos que tenemos $s = 4$ soluciones en lugar de una sola, como consideramos arriba. Esto significa que

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

lo cual es aproximadamente el doble del ángulo en el caso $\vert A_1 \vert = 1$, cuando $N$ es grande. Supongamos que no supiéramos nada mejor y eligiéramos el mismo valor de $t$ que en el caso de solución única:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

El impacto sería catastrófico, como muestra la siguiente tabla de probabilidades.

$$\begin{array}{ll} N & \text{Probabilidad de éxito}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Esta vez la probabilidad de éxito tiende a $0$ cuando $N$ tiende a infinito. Esto se debe a que estamos rotando el doble de rápido que con una solución única, por lo que pasamos de largo el objetivo $\vert A_1\rangle$ y terminamos cerca de $-\vert A_0\rangle$.

Si en cambio usamos la elección recomendada de $t$, que es

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

para

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

el rendimiento mejora. Más precisamente, esta elección de $t$ conduce al éxito con alta probabilidad.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Generalizando, puede demostrarse que

$$p(N,s) \geq 1 - \frac{s}{N}$$

donde usamos la notación sugerida arriba: $p(N,s)$ denota la probabilidad de que el algoritmo de Grover, ejecutado durante $t$ iteraciones, descubra una solución cuando hay un total de $s$ soluciones entre $N$ posibilidades.

Esta cota inferior de $1 - s/N$ para la probabilidad de éxito es algo peculiar, ya que más soluciones implican una peor cota inferior — pero asumiendo que $s$ es significativamente menor que $N$, concluimos igualmente que la probabilidad de éxito es razonablemente alta. Como antes, el mero hecho de que $p(N,s)$ sea razonablemente grande implica la utilidad del algoritmo.

También se cumple que

$$p(N,s) \geq \frac{s}{N}.$$

Esta cota inferior describe la probabilidad de que una cadena $x\in\Sigma^n$ elegida uniformemente al azar sea una solución — por lo que el algoritmo de Grover siempre funciona al menos tan bien como la adivinación aleatoria. (De hecho, el algoritmo de Grover con $t=0$ es exactamente la adivinación aleatoria.)

Consideremos ahora el número de iteraciones (y por tanto el número de consultas)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

para

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

Para todo $\alpha \in [0,1]$ se tiene $\sin^{-1}(\alpha)\geq \alpha$, y por lo tanto

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Esto implica que

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Esto corresponde a un ahorro en el número de consultas cuando $s$ crece. En particular, el número de consultas necesarias es

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Número desconocido de soluciones

Si el número de soluciones $s = \vert A_1 \vert$ es desconocido, se requiere un enfoque diferente, ya que en esta situación no tenemos conocimiento de $s$ para informar nuestra elección de $t$. De hecho, hay varios enfoques posibles.

Un enfoque sencillo es elegir $t$ uniformemente al azar de

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

Tal elección de $t$ siempre encuentra una solución (si existe) con una probabilidad de más del 40%, aunque esto no es obvio y requiere un análisis que no se incluye aquí. Sin embargo, tiene sentido, especialmente si consideramos la imagen geométrica: rotar el estado de $\mathsf{Q}$ un número aleatorio de veces no es muy diferente de elegir un vector unitario aleatorio en el espacio generado por $\vert A_0\rangle$ y $\vert A_1\rangle$, para el cual es probable que el coeficiente de $\vert A_1\rangle$ sea razonablemente grande. Repitiendo este procedimiento y verificando el resultado de la misma manera descrita anteriormente, la probabilidad de encontrar una solución puede acercarse mucho a $1$.

Existe un método más refinado que encuentra una solución, si existe alguna, con $O(\sqrt{N/s})$ consultas, incluso cuando el número de soluciones $s$ no es conocido, y que requiere $O(\sqrt{N})$ consultas para determinar que no hay soluciones cuando $s=0$.

La idea básica consiste en elegir $t$ iterativamente de manera uniforme al azar del conjunto $\{1,\ldots,T\}$, para valores crecientes de $T$. En particular, podemos comenzar con $T = 1$ y aumentarlo exponencialmente, deteniendo siempre el proceso tan pronto como se encuentre una solución, y limitando $T$ para no desperdiciar consultas cuando no hay solución. El procedimiento aprovecha el hecho de que se necesitan menos consultas cuando existen más soluciones. Sin embargo, se requiere cuidado para equilibrar la tasa de crecimiento de $T$ con la probabilidad de éxito de cada iteración. ($T \leftarrow \lceil \frac{5}{4}T\rceil$ funciona, por ejemplo, como muestra un análisis. Sin embargo, duplicar $T$ no funciona — es un aumento demasiado rápido.)

Los casos triviales

En todo el análisis anterior hemos asumido que el número de soluciones no es cero. De hecho, al referirnos a los vectores

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

hemos asumido implícitamente que tanto $A_0$ como $A_1$ no están vacíos. Aquí consideraremos brevemente qué sucede cuando uno de estos conjuntos está vacío.

Antes de entrar en el análisis, señalemos lo obvio: Si cada cadena $x\in\Sigma^n$ es una solución, veremos una solución al medir; y si no hay soluciones, no veremos ninguna. En cierto sentido, no hace falta profundizar más que eso.

Sin embargo, podemos verificar rápidamente las matemáticas para estos casos triviales. La situación en la que uno de $A_0$ y $A_1$ está vacío ocurre cuando $f$ es constante; $A_1$ está vacío cuando $f(x) = 0$ para todo $x\in\Sigma^n$, y $A_0$ está vacío cuando $f(x) = 1$ para todo $x\in\Sigma^n$. Esto significa que

$$Z_f \vert u\rangle = \pm \vert u\rangle$$

y por lo tanto

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Independientemente del número de iteraciones $t$ que realicemos en estos casos, las mediciones siempre producirán una cadena $x\in\Sigma^n$ elegida uniformemente al azar.