Búsqueda no estructurada

Resumen

Comenzamos con una descripción del problema que resuelve el algoritmo de Grover. Como es habitual, escribimos $\Sigma = \{0,1\}$ para el alfabeto binario a lo largo de toda esta discusión.

Sea

$$f:\Sigma^n \rightarrow \Sigma$$

una función de cadenas binarias de longitud $n$ a bits. Asumimos que podemos evaluar esta función de manera eficiente; sin embargo, aparte de eso, es arbitraria y no podemos contar con ninguna estructura particular ni con una implementación específica.

Lo que hace el algoritmo de Grover es buscar una cadena $x\in\Sigma^n$ para la cual $f(x) = 1$. Tales cadenas se denominan soluciones del problema de búsqueda. Si hay múltiples soluciones, cualquiera de ellas es una salida correcta; si no hay solución, la respuesta debe ser que no existe ninguna solución.

Esta tarea se denomina problema de búsqueda no estructurada porque no podemos asumir que $f$ tiene alguna estructura particular que lo haga fácil. No estamos buscando en una lista ordenada ni en una estructura de datos diseñada específicamente para la búsqueda — básicamente estamos buscando una aguja en un pajar.

Intuitivamente, se puede imaginar que tenemos un circuito booleano extremadamente complejo que calcula $f$, y que podemos ejecutar fácilmente este circuito para una cadena de entrada seleccionada. Sin embargo, como el circuito es tan complicado, no tenemos posibilidad de entenderlo mediante inspección (aparte de la posibilidad de evaluarlo para entradas seleccionadas).

Una forma de realizar esta tarea de búsqueda clásicamente consiste en recorrer todas las cadenas $x\in\Sigma^n$ en orden y evaluar $f$ para cada una, comprobando si es una solución. En lo sucesivo, escribimos

$$N = 2^n$$

por conveniencia. Hay $N$ cadenas en $\Sigma^n$, por lo que recorrerlas todas requiere $N$ evaluaciones de $f$. Bajo la suposición de que estamos limitados a evaluar $f$ en entradas seleccionadas, esto es lo mejor que podemos hacer con un algoritmo determinista si queremos garantizar el éxito. Con un algoritmo probabilístico se podría ahorrar tiempo eligiendo entradas para $f$ al azar, pero aun así se necesitan $O(N)$ evaluaciones de $f$ si el método debe tener éxito con alta probabilidad.

El algoritmo de Grover resuelve este problema de búsqueda con alta probabilidad usando solo $O(\sqrt{N})$ evaluaciones de $f$. Estas evaluaciones de la función deben realizarse en superposición, de manera similar a los algoritmos de consulta discutidos en la lección Algoritmos cuánticos de consulta, incluyendo el algoritmo de Deutsch, el algoritmo de Deutsch-Jozsa y el algoritmo de Simon. A diferencia de esos algoritmos, el algoritmo de Grover adopta un enfoque iterativo: evalúa $f$ sobre superposiciones de cadenas de entrada e intercala estas evaluaciones con otras operaciones que crean patrones de interferencia y, después de $O(\sqrt{N})$ iteraciones, conducen con alta probabilidad a una solución (si existe alguna).

Formulación formal del problema

Formalizamos el problema que resuelve el algoritmo de Grover utilizando el modelo de consulta de la computación. Es decir, asumimos que tenemos acceso a la función $f:\Sigma^n\rightarrow\Sigma$ a través de una puerta de consulta, definida como es habitual:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

para cada $x\in\Sigma^n$ y $a\in\Sigma$. Esta es la acción de $U_f$ sobre estados de la base estándar; su acción en general se determina por linealidad.

Como se discutió en la lección Fundamentos algorítmicos de la computación cuántica, podemos convertir la descripción de un circuito booleano que calcula $f$ en un circuito cuántico que implementa $U_f$ (usando algunos qubits auxiliares que comienzan y terminan la computación en el estado $\vert 0\rangle$). Aunque usamos el modelo de consulta para formalizar el problema, el algoritmo de Grover no se limita a este modelo; podemos aplicarlo a cualquier función $f$ para la que tengamos un circuito booleano.

Aquí hay una formulación precisa del problema, llamado el problema de búsqueda, porque buscamos una solución — es decir, una cadena $x$ para la cual $f$ produce el valor $1$.

Problema de búsqueda

Entrada: una función $f:\Sigma^n\rightarrow\Sigma$
Salida: una cadena $x\in\Sigma^n$ con $f(x) = 1,$ o "sin solución" si no existe tal cadena $x$

Observa que esto no es un problema con promesa — la función $f$ es arbitraria. Sin embargo, es útil considerar la siguiente variante con promesa del problema, en la que se garantiza que existe exactamente una solución. Este problema fue introducido en la lección Algoritmos cuánticos de consulta como ejemplo de un problema con promesa.

Problema de búsqueda única

Entrada: una función de la forma $f:\Sigma^n \rightarrow \Sigma$
Promesa: Existe exactamente una cadena $z\in\Sigma^n$ para la cual $f(z) = 1$, y $f(x) = 0$ para todas las cadenas $x\neq z$
Salida: la cadena $z$

Observa también que el problema Or de la misma lección está estrechamente relacionado con el problema de búsqueda. En aquel problema, el objetivo es simplemente determinar si existe una solución — y no encontrar realmente una solución.