Apr 12, 2024 | 6 min read

\( \newcommand{\bra}[1]{\langle #1|} \) \( \newcommand{\ket}[1]{|#1\rangle} \) \( \newcommand{\braket}[2]{\langle #1|#2\rangle} \) \( \newcommand{\i}{{\color{blue} i}} \) \( \newcommand{\Hil}{{\cal H}} \) \( \newcommand{\cg}[1]{{\rm C}#1} \) \( \newcommand{\lp}{\left(} \) \( \newcommand{\rp}{\right)} \) \( \newcommand{\lc}{\left[} \) \( \newcommand{\rc}{\right]} \) \( \newcommand{\lch}{\left\{} \) \( \newcommand{\rch}{\right\}} \) \( \newcommand{\Lp}{\Bigl(} \) \( \newcommand{\Rp}{\Bigr)} \) \( \newcommand{\Lc}{\Bigl[} \) \( \newcommand{\RC}{\Bigr]} \) \( \newcommand{\Lch}{\Bigl\{} \) \( \newcommand{\Rch}{\Bigr\}} \) \( \newcommand{\rqa}{\quad \Rightarrow \quad} \)

4. Número desconocido de soluciones

Como ya hemos comentado, para poder aplicar el algoritmo de Grover tal y como lo hemos visto hasta ahora, nos hace falta conocer el número de soluciones. Esto es debido a que debemos aplicar un número concreto de iteraciones para maximizar la probabilidad de las soluciones correctas. Si no aplicamos el número correcto de iteraciones, la probabilidad puede ser incluso nula. Como vemos en la Ec. (36), para saber el número de iteraciones tenemos que conocer el número de soluciones.

En esta sección vamos a ver un algoritmo para poder abordar el caso en el que no conocemos el número de soluciones y por ende, no sabemos cuantas iteraciones debemos aplicar. Este algoritmo no es más que una forma inteligente de aplicar el algoritmo de Grover. Lo bueno de este algoritmo es que nuevamente podemos encontrar una solución con un número de iteraciones \(\mathcal{O}( \sqrt{N/M} )\), aunque a priori no sabemos cuantas iteraciones son.

Nota

Uno de los pasos del algoritmo de Grover es una reflexión de las amplitudes respecto a la media. Esto implica que podemos tener los siguientes casos:

• \(M < N/2\): El algoritmo funciona normal.

• \(M = N/2\): El algoritmo no funciona

• \(M > N/2\): El algoritmo amplifica las soluciones incorrectas.

En esta sección vamos a seguir el artículo [2].

Algoritmo para el caso de \(M\) desconocido.

Al igual que comentamos en la sección anterior, tenemos \(M\) valores diferentes \(i\) que cumplen \(L_i=x\), solo que en este caso no conocemos \(M\). Denominemos \(\omega\) al conjunto de los \(M\) valores \(i\) que son solución, y denominemos \(\omega^\perp\) al conjunto de los \(N-M\) valores \(i\) que no son solución

(43)\[\begin{align} & \boxed{\omega = \lch i | L_{i} = x \rch } & \boxed{\omega^{\perp} = \lch i | L_{i} \neq x \rch}. \end{align}\]

Supondremos también que estamos en el caso en el que \(N = 2^n\) y que además partimos del estado de la Ec. (7), es decir, de una superposición uniforme.

Teorema:

El siguiente algoritmo encuentra una solución en un tiempo esperado \(\mathcal{O} ( \sqrt{N/M} )\) (si tomamos \(1 \leq M \leq 3N/4\))

1. Inicializamos \(r=1\) y \(\lambda = 6/5\). (En realidad, cualquier valor \(1 \leq \lambda \leq 4/3\) sirve).

2. Elegimos un valor aleatorio \(t\) con distribución uniforme tal que \(0 \leq t < r\).

3. Aplicamos \(t\) iteraciones del algoritmo de Grover empezando desde el estado inicial \(| \Psi_0 \rangle = \sum_i \frac{1}{\sqrt{N}} |i \rangle\).

4. Medimos, de forma que obtenemos uno de los estados \(|i \rangle\) del paso anterior.

5. Si \(L_i = x\), hemos encontrado una solución: Exit.

6. En caso contrario, tomemos \(r = \) min\((\lambda r, \sqrt{N})\) y volvemos al paso 2.

Demostración del Teorema

Conocimientos previos

Vamos a ver primero dos Lemmas que nos servirán para entender el algoritmo que se plantea en el Teorema.

Lema:

Para cualquier par de números \(\alpha\) y \(\beta\), y cualquier posible entero \(r\) tenemos

(44)\[\begin{equation} \sum_{j=0}^{r-1} \cos \lp \alpha + 2 \beta j \rp = \frac{\sin \lp r \beta \rp \cos (\alpha + (r-1) \beta)}{\sin \beta}. \end{equation}\]

En particular, si \(\alpha = \beta\),

(45)\[\begin{equation} \sum^{r-1}_{j=0} \cos \lp \lp 2 j + 1 \rp \alpha \rp = \frac{\sin \lp 2 r \alpha \rp}{2 \sin \alpha}. \end{equation}\]

Lema:

Sea \(M\) el número (desconocido) de soluciones de un problema tipo Grover con \(N\) elementos y sea \(\theta\) tal que \(\sin^2 \theta = M/N\). Sea \(r\) un entero positivo aleatorio. Sea \(t\) un entero aleatorio (con distribución uniforme) entre \(0\) y \(r-1\). Si observamos el registro después de \(t\) iteraciones del algoritmo de Grover empezando desde el estado \(|\Psi_0 \rangle = \sum_i \frac{1}{\sqrt{N}} | i \rangle\), la probabilidad de obtener la solución correcta es exactamente

(46)\[\begin{equation} P_r = \frac{1}{2} - \frac{\sin (4 r \theta)}{4 r \sin(2 \theta)}. \end{equation} \]

En particular, tenemos \(P_r \geq 1/4\) si \(r \geq 1/\sin ( 2 \theta)\).

Demostración/Prueba/…

Como ya sabemos, si tenemos \(M\) soluciones la probabilidad de que tras \(t\) iteraciones se mida el resultado correcto es \(M\) veces el valor del coeficiente \(k^2(t)\) (la amplitud al cuadrado del estado \(i \in \omega\) en la Ec. (37)). Teniendo en cuenta la Ec. (42) sabemos que la probabilidad es

\[\begin{equation*} P(t) = M k^2(t) = \sin^2 ((2t+1)\theta). \end{equation*}\]

De esto se sigue que la probabilidad promedio si tomamos un número de iteraciones \(t\) tal que \(0 \leq t < r\) es

\[\begin{equation*} P_r = \frac{1}{r} \sum^{r-1}_{t=0} P(t) = \frac{1}{r} \sum^{r-1}_{t=0} \sin^2 ((2t+1) \theta) = \frac{1}{2r} \sum^{r-1}_{t=0} \Lp 1-\cos ((2t+1) \theta) \Rp = \frac{1}{2} - \frac{\sin (4 r \theta)}{4 r \, \sin (2 \theta)}, \end{equation*}\]

donde en la última igualdad se ha usado el Lemma \ref{lemma_suma_cos}. Si estamos en el caso de \(r \geq 1/\sin (2\theta)\) tenemos

\[\begin{equation*} \frac{\sin (4 r \theta)}{4 r \, \sin (2 \theta)} \leq \frac{1}{4 r \, \sin (2 \theta)} \leq \frac{1}{4} \rqa P_r \geq \frac{1}{2} - \frac{1}{4}, \end{equation*}\]

donde la primera desigualdad se cumple siempre (independientemente del valor de \(r\)) pues viene de que la función seno está acotada entre \(-1\) y \(1\).

Nota

A veces al ver las formulaciones tan formales que se dan en los teoremas o lemmas, perdemos un poco el norte sobre lo que nos quieren transmitir. Veámoslos en palabras más llanas:

• El primer Lemma simplemente es una relación trigonométrica un poco exótica y nos sirve para demostrar el segundo Lemma.

• El segundo Lemma nos da la expresión de la probabilidad promedio que tenemos de medir el resultado correcto usando el algoritmo de Grover en un caso particular. En este caso lo que hacemos es, dado un número \(r\), ejecutar \(t\) iteraciones de Grover donde \(t\) es un número aleatorio entre \(0\) y \(r-1\). Probando muchas veces con muchos número aleatorio \(t\), en promedio la probabilidad \(P_r\) de obtener el resultado correcto está dada por la Ec. (46). Véase que, para un problema de Grover concreto (\(\theta\) fijo), esta probabilidad depende solo de \(r\).

Demostración

Sea \(\theta\) un ángulo tal que

(47)\[\begin{equation} \sin \theta = \sqrt{N/M}, \end{equation} \]

(como en la Ec. (29)).

Denominemos \(r_s\) al valor de \(r\) en la s-esima iteración del bucle principal, es decir

(48)\[\begin{equation} r_s = \lambda^{s-1}, \qquad \text{con } s = 1,2,\dots \quad \text{ y } \lambda = \frac{4}{3}. \end{equation} \]

(No confundir las \textbf{iteraciones del bucle principal} con las \textbf{iteraciones de Grover}: en cada iteración \(s\) del bucle principal hacemos \(t\) iteraciones de Grover.) Sea \(r_0\) tal que

(49)\[\begin{equation} r_0 = \frac{1}{\sin (2 \theta)}. \end{equation}\]

(Véase que \(r_0\) no es valor inicial de \(r_s\)).

Aplicando un poco de trigonometria

\[\begin{equation*} \sin^2 \theta = \frac{1-\cos (2\theta)}{2} \rqa 1 - 2 \sin^2 \theta = \cos (2 \theta) = \sqrt{1 - \sin^2 (2 \theta)} \rqa \sin^2 (2 \theta) = 1 - \Lp 1 - 2 \sin^2 \theta \Rp^2. \end{equation*}\]

Desarrollando el cuadrado y teniendo en cuenta la Ec. (47) llegamos a

(50)\[\begin{equation} r_0 = \frac{1}{\sin (2 \theta)} = \frac{N}{2 \sqrt{(N-M)M}} < \sqrt{\frac{N}{M}}. \end{equation} \]

donde en la desigualdad se ha tenido en cuenta que \(M \leq 3N/4\). Veámoslo

\[\begin{align*} \frac{N}{2 \sqrt{(N-M)M}} < \sqrt{\frac{N}{M}} \rqa \frac{\sqrt{N}}{2 \sqrt{(N-M)}} < 1 \rqa \frac{N}{(N-M)} < 4 \rqa 1 - \frac{1}{4} > \frac{M}{N}. \end{align*}\]

Debemos estimar el número esperado total de iteraciones de Grover que tenemos que hacer (sumando todas las interaciones de Grover en todas las iteraciones del bucle principal). El tiempo total será del orden de este número. Sabemos que \textbf{el número promedio de iteraciones de Grover que se realizan en la iteración s-esima del bucle principal es menor que} \({r_s/2}\). Escribiéndolo de forma bonita:

(51)\[\begin{equation} \bar{t}_s < \frac{r_s}{2} = \frac{\lambda^{s-1}}{2} \qquad \text{ donde la barra significa promedio}. \end{equation} \]

Esto es debido a que en cada iteración del bucle principal hacemos un número aleatorio de iteraciones \(t_s\) de Grover con \(0 \leq t_s < r_s\). Denominamos fase crítica al momento en el que hemos realizado suficientes iteraciones del bucle principal como para tener \(r_s \geq r_0\), es decir

(52)\[\begin{equation} r_s > r_0 \rqa \lambda^{s-1} > r_0 \rqa s > 1 + \log_{\lambda} r_0 \rqa s > \lceil \log_\lambda r_0 \rceil. \end{equation}\]

con lo cual, estamos en la fase crítica cuando el número de iteraciones del bucle principal es mayor que \({\lceil \log_{\lambda} r_0 \rceil}\) (donde esta notación significa redondear hacia el siguiente entero). Si nos fijamos en el Lemma anterior, esta fase corresponde a aquella donde \(P_r > 1/4\).

Teniendo en cuenta la Ec. (51), vemos que el número promedio total de iteraciones de Grover que se realizan antes de llegar a la fase crítica es

(53)\[\begin{split}\begin{equation} \begin{split} \sum_{s=1}^{\lceil \log_\lambda r_0 \rceil} \bar{t}_s & = \frac{1}{2} \sum_{s=1}^{\lceil \log_\lambda r_0 \rceil} \lambda^{s-1} = \frac{1}{2} \sum_{\tilde{s}=0}^{\lceil \log_\lambda r_0 \rceil-1} \lambda^{\tilde{s}} = \frac{1}{2} \frac{ \lambda^{\lceil \log_\lambda r_0 \rceil} -1 }{\lambda -1 } < \\ & < \frac{1}{2} \frac{\lambda^{1 + \log_\lambda r_0} -1 }{\lambda -1} = \frac{1}{2} \frac{r_0 \lambda -1 }{\lambda -1 } < \frac{1}{2} \frac{\lambda}{\lambda - 1} r_0 = \boxed{3 r_0}. \end{split} \end{equation} \end{split}\]

donde se ha aplicado la formula e la suma de la serie geométrica\footnote{Suma de la serie geométrica:

(54)\[\begin{equation} \sum_{k=0}^n r^k = \frac{1-r^{n+1}}{1-r} = \frac{r^{n+1} -1 }{r -1}. \end{equation} \]

Vemos pues que el algoritmo llega a la fase crítica en un tiempo \(\mathcal{O} (r_0) < \mathcal{O}(\sqrt{N/M})\).

Como ya comentamos, una vez alcanzado el estado crítico, por el Lemma anterior, sabemos que en cada nueva iteración del bucle principal la probabilidad de éxito \({P_r \geq 1/4}\) ya que \(r_s > 1/\sin (2 \theta)\). De ello se deduce que el número esperado de iteraciones de Grover necesarias para tener éxito una vez alcanzada la fase crítica está acotado superiormente por

(55)\[\begin{equation} \sum_{\tilde{u}=1}^\infty (1-P_r)^{\tilde{u}-1} P_r \, \bar{t}_{\tilde{u}+1+\lceil \log_\lambda r_0 \rceil} < \frac{1}{2} \sum_{\tilde{u}=1}^\infty \frac{3^{\tilde{u}-1}}{4^{\tilde{u}-1}} \frac{1}{4} \lambda^{\tilde{u}+1+\lceil \log_\lambda r_0 \rceil}, \end{equation}\]

donde \((1-P_r)^{\tilde{u}-1}\) es la probabilidad de fallar \(\tilde{u}-1\), con lo que \((1-P_r)^{\tilde{u}-1} P_r\) es la probabilidad de haber fallado \(\tilde{u}-1\) veces y acertar en la \(\tilde{u}\)-esima. \(\bar{t}_s\) viene dada por Ec. (51). Véase que para acotar las iteraciones nos hemos puesto en el peor caso, en el que la probabilidad de exito es la mínima y no aumenta (\(P_r = 1/4\)). Podemos hacer al cambio de variable \(u = \tilde{u} -1\) para poner la expresión anterior más acorde para realizar la suma de la serie geométrica (ver Ec. (54))

(56)\[\begin{equation} \frac{1}{2} \sum_{u=0}^\infty \frac{3^{u}}{4^{u}} \frac{1}{4} \lambda^{u+\lceil \log_\lambda r_0 \rceil} < \frac{1}{2} \frac{1}{4} \lambda^{1+ \log_\lambda r_0} \sum_{u=0}^\infty \frac{3^{u}}{4^{u}} \lambda^{u} = \frac{r_0 \lambda}{8} \frac{1}{1-3 \lambda/4} = \frac{\lambda}{8-6 \lambda}r_0 = \boxed{ \frac{3}{2} r_0}. \end{equation} \]

El número total esperado de iteraciones de Grover, en caso de que se alcance la fase crítica, está, por tanto, limitado por la suma de Ec. (53) más Ec. (56), es decir,

(57)\[\begin{equation} T = r_0 + \frac{3}{2} r_0 = \frac{9}{2} r_0 < \frac{9}{2} \sqrt{\frac{M}{N}}, \end{equation}\]

con lo que el tiempo esperado total es \(\mathcal{O}(\sqrt{N/M})\) siempre que \(0 < M \leq 3N/4\). Véase que \(\frac{9}{2} r_0 \approx \frac{9}{2} \sqrt{N/M}\) cuando \(M \ll N\), que es menos de 4 veces el tiempo esperado en el caso de conocer \(M\) de antemano (ver Ec. (36)). El caso \(M > 3N/4\) puede resolverse en tiempo esperado constante mediante muestreo clásico. El caso \(M = 0\) se maneja mediante un tiempo de espera apropiado en el algoritmo anterior, que permite afirmar en un tiempo en \(\mathcal{O} (\sqrt{N})\) que no hay soluciones cuando este es el caso, con una probabilidad de fallo arbitrariamente pequeña cuando de hecho hay una solución.

---

Autores:

David Castaño (UMA-SCBI), Raul Fuentes (BSC-CNS), Daniel Talaván (COMPUTAEX), Francisco Matanza (UNICAN)

---

License: Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

This work has been financially supported by the Ministry for Digital Transformation and of Civil Service of the Spanish Government through the QUANTUM ENIA project call - Quantum Spain project, and by the European Union through the Recovery, Transformation and Resilience Plan - NextGenerationEU within the framework of the Digital Spain 2026 Agenda.