Descripción del algoritmo de Grover

En esta sección describimos el algoritmo de Grover. Comenzamos con la discusión de las puertas de consulta de fase y cómo construirlas, seguida de la descripción del algoritmo en sí. Finalmente, discutimos brevemente cómo el algoritmo se aplica naturalmente a la búsqueda.

Puertas de consulta de fase

El algoritmo de Grover utiliza operaciones conocidas como puertas de consulta de fase. A diferencia de una puerta de consulta ordinaria $U_f$, que para una función dada $f$ se define como se describió anteriormente, una puerta de consulta de fase para la función $f$ se define de la siguiente manera:

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

para cada cadena $x\in\Sigma^n$.

La operación $Z_f$ puede implementarse con una sola puerta de consulta $U_f$, como muestra este diagrama:

Esta implementación aprovecha el fenómeno de retroceso de fase y requiere que un qubit auxiliar, inicializado en el estado $\vert -\rangle$, esté disponible. Este qubit permanece en el estado $\vert - \rangle$ después de la implementación y puede reutilizarse (por ejemplo, para implementar puertas $Z_f$ posteriores) o simplemente descartarse.

Además de la operación $Z_f$, también usamos una puerta de consulta de fase para la función OR de $n$ bits, que se define para cada cadena $x\in\Sigma^n$ de la siguiente manera:

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Explícitamente, la puerta de consulta de fase para la función OR de $n$ bits actúa así:

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

Para ser claros: así es como $Z_{\mathrm{OR}}$ actúa sobre estados de la base estándar; su comportamiento para estados arbitrarios se obtiene por linealidad a partir de esta expresión.

La operación $Z_{\mathrm{OR}}$ puede implementarse como un circuito cuántico comenzando con un circuito booleano para la función OR, convirtiéndolo en una operación $U_{\mathrm{OR}}$ (es decir, una puerta de consulta estándar para la función OR de $n$ bits) — según el procedimiento descrito en la lección Fundamentos algorítmicos de la computación cuántica —, y finalmente construyendo una operación $Z_{\mathrm{OR}}$ mediante el fenómeno de retroceso de fase. Observa que $Z_{\mathrm{OR}}$ no tiene dependencia de la función $f$ y, por lo tanto, puede implementarse mediante un circuito cuántico sin puertas de consulta.

Descripción del algoritmo

Ahora que tenemos las dos operaciones $Z_f$ y $Z_{\mathrm{OR}}$, podemos describir el algoritmo de Grover.

El algoritmo se refiere a un número $t$, que indica el número de iteraciones (y por tanto el número de consultas a la función $f$). Este número $t$ no está determinado por el algoritmo de Grover en la forma aquí descrita; discutiremos más adelante en la lección cómo puede elegirse.

Algoritmo de Grover

1. Inicializar un registro de $n$ qubits $\mathsf{Q}$ en el estado cero $\vert 0^n \rangle$ y luego aplicar una operación de Hadamard a cada qubit de $\mathsf{Q}$.
2. Aplicar $t$ veces la operación unitaria $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ al registro $\mathsf{Q}$.
3. Medir los qubits de $\mathsf{Q}$ en la base estándar y devolver la cadena resultante.

La operación $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ iterada en el paso 2 se denominará la operación de Grover en el resto de esta lección. Aquí hay una representación en circuito cuántico de la operación de Grover para $n=7\!:$

En este diagrama, la operación $Z_f$ se muestra más grande que $Z_{\mathrm{OR}}$ — una indicación visual informal de que probablemente es la operación más costosa. En particular, $Z_f$ requiere una consulta en el modelo de consulta, mientras que $Z_{\mathrm{OR}}$ no requiere consultas. Si, en cambio, tenemos un circuito booleano para la función $f$ y lo convertimos en un circuito cuántico para $Z_f$, puede suponerse que el circuito cuántico resultante será más grande y complejo que uno para $Z_{\mathrm{OR}}$.

Aquí hay un diagrama de un circuito cuántico para el algoritmo completo con $n=7$ y $t=3$. Para valores más grandes de $t$, simplemente podemos insertar más instancias de la operación de Grover inmediatamente antes de las mediciones.

Aplicación a la búsqueda

El algoritmo de Grover puede aplicarse al problema de búsqueda de la siguiente manera:

• Elegir el número $t$ en el paso 2. (Esto se discutirá más adelante en la lección.)
• Ejecutar el algoritmo de Grover para la función $f$ con el número $t$ elegido, para obtener una cadena $x\in\Sigma^n$.
• Consultar la función $f$ para la cadena $x$ para verificar si es una solución válida:
  • Si $f(x) = 1,$ hemos encontrado una solución y podemos detenernos y devolver $x$.
  • Si $f(x) = 0,$ podemos ejecutar el procedimiento de nuevo, posiblemente con una elección diferente para $t$, o podemos rendirnos y devolver "sin solución".

Una vez que hayamos analizado cómo funciona el algoritmo de Grover, veremos que eligiendo $t = O(\sqrt{N})$ obtenemos una solución a nuestro problema de búsqueda con alta probabilidad (siempre que exista una).