Apr 12, 2024 | 3 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} \)

3. Número conocido de soluciones

Vamos a empezar el análisis formal tratando el caso en el que conocemos el número \(M\) de soluciones que hay en nuestro dataset. Es decir, tenemos \(M\) valores diferentes \(i\) que cumplen \(L_i=x\). 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

(22)\[\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.

Nota (Importante)

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].

Generalización de las expresiones de la sección anterior para \(M\) soluciones.

Vemos a reescribir las ecuaciones enmarcadas de la sección 2. Explicación geométrica para el caso de \(M\) soluciones. Empecemos reescribiendo las expresiones del estado inicial de la Ec. (9) y del estado \(|\Psi_j \rangle \) de la Ec. (19)

(23)\[\begin{equation} \boxed{|\Psi_0 \rangle = | \Psi (k(0),l(0)) \rangle = \sum_{i \in \omega} k(0) |i \rangle + \sum_{i \in \omega^{\perp}} l(0) |i \rangle}, \quad \text{donde} \quad \boxed{k(0) = l(0) = \frac{1}{\sqrt{N}}}. \end{equation} \]

(24)\[\begin{equation} \boxed{|\Psi(t) \rangle = | \Psi (k(t),l(t)) \rangle = \sum_{i \in \omega} k(t) |i \rangle + \sum_{i \in \omega^{\perp}} l(t) |i \rangle }. \end{equation} \]

Vemos que ahora el primer sumatorio tiene \(M\) elementos, mientras que el segundo tiene \(N-M\). Por supuesto, se cumple que \(|\Psi(t) \rangle\) tiene módulo 1, es decir

(25)\[\begin{equation} \langle \Psi(t) |\Psi(t) \rangle = \boxed{ M k(t)^2 + (N-M) l(t)^2 = 1 \, \, \forall t}. \end{equation} \]

Podemos ahora también redefinir el estado \(|\omega^{\perp} \rangle\) de la Ec. (11) y definir \(| \omega \rangle\)

(26)\[\begin{align} & \boxed{| \omega^{\perp} \rangle = \frac{1}{\sqrt{N-M}}\sum_{i \in \omega^{\perp}} |i \rangle} & \boxed{| \omega \rangle = \frac{1}{\sqrt{M}}\sum_{i \in \omega} | i \rangle} \end{align} \]

de forma que

(27)\[\begin{equation} \boxed{|\Psi(t) \rangle = k(t) \sqrt{M} |\omega \rangle + l(t) \sqrt{N-M} | \omega^{\perp} \rangle}. \end{equation} \]

Nota

Nuevamente, los factores \(\sqrt{N-M}\) y \(\sqrt{M}\) en las definiciones de \(| \omega^{\perp} \rangle\) y \(| \omega \rangle\) son para hacerlos vectores unitarios

(28)\[\begin{align} & \langle \omega^{\perp} | \omega^{\perp} \rangle = 1 & \langle \omega | \omega \rangle = 1 . \end{align}\]

Veamos ahora la expresión del esto inicial en función del ángulo \(\theta\) de la Ec. (14)

(29)\[\begin{equation} | \Psi_0 \rangle = \sin \theta \, |\omega \rangle + \cos \theta \, | \omega^{\perp} \rangle, \qquad \text{donde} \qquad \boxed{\sin \theta = \sqrt{\frac{M}{N}}}. \end{equation} \]

Nuevamente, comparando la Ec. (29) y la Ec. (27) obtenemos las expresiones de \(k(t)\) y \(l(t)\) en función del ángulo \(\theta\)

(30)\[\begin{align} & \boxed{k(t) = \frac{1}{\sqrt{M}} \sin \Lc (2t+1) \theta \Rc} & \boxed{l(t) = \frac{1}{\sqrt{N-M}}\cos \Lc (2t+1) \theta \Rc}. \end{align} \]

Vemos que estas expresiones cumplen la Ec. (25). Finalmente, por ser rigurosos (y por recopilar todas las ecuaciones juntas), tenemos que el oráculo (Ec. (15)), el difusor (Ec. (18)) nos quedan:

(31)\[\begin{split}\begin{align} & \boxed{U_\omega | i \rangle = \lch \begin{matrix} & | i \rangle \quad \text{si } i \not \in \omega \\ & - | i \rangle \quad \text{si } i \in \omega \end{matrix} \right.} & \boxed{U_{\Psi_0} = 2 |\Psi_0 \rangle \langle \Psi_0 | - I}. \end{align} \end{split}\]

donde recordemos que denominamos operador de Grover a

(32)\[\begin{equation} \boxed{G = U_{\Psi_0} U_\omega} \rqa |\Psi(t) \rangle = G^t | \Psi_0 \rangle. \end{equation} \]

Véase que el caso particular de una solución es, efectivamente, aquel con \(M=1\).

Número de iteraciones.

Denominemos \(T\) al número de iteraciones para el cual la probabilidad de medir la solución correcta se maximiza. Es decir, \(l(T) \approx 0\) y \(k(T) \approx 1\). Sabemos que \(l(\tilde{T}) =0\) cuando el coseno es igual cero, es decir:

(33)\[\begin{equation} l(\tilde{T}) = 0 \rqa (2\tilde{T}+1) \theta = \frac{\pi}{2} \rqa \tilde{T} = \frac{\pi}{4 \theta} - \frac{1}{2}. \end{equation}\]

Por regla general, este valor \(\tilde{T}\) no será un entero. Tomemos

(34)\[\begin{equation} T = \lfloor \pi / 4 \theta \rfloor \end{equation}\]

donde la notación \(\lfloor \alpha \rfloor\) quiere decir que redondeamos a un entero por truncamiento. Véase que \(|m-\tilde{m}| \leq 1/2\). Se sigue que \(|(2T+1)\theta - (2\tilde{T}+1)\theta | \leq \theta \). Pero \((2 \tilde{T}+1) \theta = \pi/2\) por definición de \(\tilde{T}\). Con lo cual \(\left| \cos \Lp (2T+1) \theta \Rp \right| \leq | \sin \theta |\). Concluimos entonces que la probabilidad de fallo después de \(T = \lfloor \pi / 4 \theta \rfloor\) es

(35)\[\begin{equation} (N-M)l^2(T) = \cos^2 \Lp (2T+1) \theta \Rp \leq \sin^2 \theta = \frac{M}{N} \end{equation}\]

que es despreciable si \(M \ll N\). Véase que el \((N-M)\) de la expresión anterior es porque hay \((N-M)\) estados incorrectos que podemos medir, cada uno de ellos con probabilidad \(l^2(T)\).

Véase que el algoritmo corre en un tiempo del orden de \(\mathcal{O}(\sqrt{N/M})\) ya que

(36)\[\begin{equation} T \leq \frac{\pi}{4 \theta} \approx \frac{\pi}{4 \sin \theta} \approx \frac{\pi}{4} \sqrt{\frac{N}{M}} \rqa \boxed{T = \left\lfloor \frac{\pi}{4} \sqrt{\frac{N}{M}} \right\rfloor}. \end{equation} \]

Extra: Formulación recursiva de \(k(t)\) y \(l(t)\).

Ya hemos comentado en cada iteración se aplican lo dos operadores de la Ec. (31), es decir

(37)\[\begin{equation} |\Psi{(t+1)} \rangle = U_{\Psi_0} U_\omega |\Psi(t) \rangle. \end{equation} \]

Desarrollemos esta expresión para ver la relación de recursivida de los coeficientes, es decir, para ver la expresión de \(k(t+1)\) y \(l(t+1)\) en función de \(k(t)\) y \(l(t)\). Primero vamos el término \(U_\omega |\Psi(t) \rangle\) usando la expresión de \(U_\omega\) de la Ec. (31):

(38)\[\begin{equation} U_\omega |\Psi(t) \rangle = - k(t) \sqrt{M}|\omega \rangle + l(t) \sqrt{N-M} | \omega^{\perp} \rangle. \end{equation} \]

Desarrollemos un poco la Ec. (37) y usando la expresión de \(U_{\Psi_0}\) de la Ec. (31):

(39)\[\begin{split}\begin{equation} \begin{split} |\Psi(t+1) \rangle & = U_{\Psi_0} U_\omega |\Psi(t) \rangle \\ & = \Bigl( 2 |\Psi_0 \rangle \langle \Psi_0 | - I \Bigr) U_\omega |\Psi(t) \rangle \\ & = 2 |\Psi_0 \rangle \langle \Psi_0 | U_\omega |\Psi(t) \rangle - U_\omega |\Psi(t) \rangle . \end{split} \end{equation} \end{split}\]

Usando la Ec. (38) el término \(\langle \Psi_0 | U_\omega |\Psi(t) \rangle\) nos queda

(40)\[\begin{equation} \langle \Psi_0 | U_\omega |\Psi(t) \rangle = \frac{1}{\sqrt{N}} \Lp -k(t) M + (N-M) l(t) \Rp. \end{equation} \]

Cálculo de \(\langle \Psi_0 | U_\omega |\Psi (t) \rangle\)

Cálculo

Hacemos ahora el producto \( \langle \Psi_0 | U_\omega |\Psi(t) \rangle = \langle \Psi_0 | \Lp U_\omega |\Psi(t) \rangle \Rp \) usando la Ec. (38)

\[\begin{equation*} \begin{split} \langle \Psi_0 | U_\omega |\Psi(t) \rangle & = \langle \Psi_0 | \Lp -k(t) \sqrt{M} |\omega \rangle + l(t) \, \sqrt{N-M} | \omega^{\perp} \rangle \Rp \\ & = \Lp k(0) \sqrt{M} \langle \omega| + l(0) \, \sqrt{N-M} \langle \omega^{\perp} | \Rp \Lp -k(t) \sqrt{M} |\omega \rangle + l(t) \, \sqrt{N-M} | \omega^{\perp} \rangle \Rp . \end{split} \end{equation*}\]

Debido a la ortogonalidad de los estado (esto es, \(\langle i | j \rangle =0\) si \(j\neq i\)), y teniendo en cuanta que \(k(0) = l(0) = 1/\sqrt{N}\) tenemos

\[\begin{equation*} \langle \Psi_0 | U_\omega |\Psi(t) \rangle = - k(0) k(t) M + (N-M) l(0) l(t) = \frac{1}{\sqrt{N}} \Lp -k(t) M + (N-M) l(t) \Rp. \end{equation*}\]

Sustituyendo la Ec. (38) y la Ec. (40) en la Ec. (39) tenemos:

(41)\[\begin{equation} |\Psi(t+1) \rangle = \lp \frac{N-2M}{N} k(t) + \frac{2(N-M)}{N} l(t) \rp \sum_{i \in \omega} | i \rangle + \lp \frac{N-2M}{N} l(t) - \frac{2M}{N} k(t) \rp \sum_{i \in \omega^{\perp}} | i \rangle. \end{equation} \]

Cálculo de la ecuación anterior

Cálculo

\[\begin{align*} |\Psi (t+1) \rangle & = \, 2 \frac{1}{\sqrt{N}} \Lp -k(t) M + (N-M) l(t) \Rp | \Psi_0 \rangle - k(t) \sqrt{M} |\omega \rangle + l(t) \, \sqrt{N-M} | \omega^{\perp} \rangle = \\ & = \, \frac{2}{\sqrt{N}} \Lp -k(t) M + (N-M) l(t) \Rp \frac{1}{\sqrt{N}} \Lp \sqrt{M} | \omega \rangle + \sqrt{N-M} |\omega^{\perp} \rangle \Rp \\ & \qquad + k(t) \sqrt{M} |\omega \rangle + l(t) \, \sqrt{N-M} | \omega^{\perp} \rangle = \\ & = \, \lc \frac{2}{N} \Lp -k(t) M + (N-M) l(t) \Rp + k(t) \rc \sqrt{M} | \omega \rangle \\ & \qquad + \lc \frac{2}{N} \Lp -k(t) M + (N-M) l(t) \Rp - l(t) \rc \sqrt{N-M} | \omega^{\perp} \rangle. \end{align*}\]

Simplificando y teniendo en cuenta que las expresión de \(| \omega \rangle\) y \(|\omega^{\perp} \rangle\) en la Ec. (26), llegamos a la Ec. (41).

Finalmente llegamos a las relaciones:

(42)\[\begin{align} & \boxed{k(t+1) = \frac{N-2M}{N} k(t) + \frac{2(N-M)}{N} l(t)}, & \boxed{l(t+1) = \frac{N-2M}{N} l(t) - \frac{2M}{N}k(t)}. \end{align} \]

---

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.