Apr 12, 2024 | 4 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} \)
1. Introducci贸n#
La computaci贸n cu谩ntica es un campo relativamente joven y en el cual hay depositadas muchas esperanzas, pues se cree que tiene el potencial de poder resolver algunos problemas con los que la computaci贸n cl谩sica no puede lidiar. Estamos hablando de los famosos problemas de la clase de complejidad NP-hard. Sin embargo, pese a esta creencia, pocas demostraciones te贸ricas hay sobre el tema. La demostraci贸n m谩s famosa es la del Algoritmo de Shor, que es capaz de abordar el problema de la factorizaci贸n de un n煤mero en sus factores primos. Esto es porque el algoritmo es capaz de calcular los factores primos en un tiempo polin贸mico, frente al tiempo exponencial que requieren los mejores algoritmos cl谩sicos. El algoritmo sobre el que tratan estas notas, el tambi茅n archiconocido Algoritmo de Grover, no ofrece una ventaja exponencial respecto al mejor algoritmo cl谩sico, pero si ofrece una mejora sustancial (cuadr谩tica).
Resumiendo mucho, el algoritmo de Grover es un algoritmo de b煤squeda no estructurada. El objetivo del algoritmo es encontrar un valor (o varios) en una secuencia no ordenada de \(N\) componentes. Supongamos que tenemos una lista \(L\) con \(N\) elementos donde denominamos \(L_i\), con \(i=0,1,\dots,N-1\), al i-茅sido elemento de la lista. Supongamos que queremos encontrar un elemento \(q\) en la lista, es decir, lo que queremos encontrar es el 铆ndice \(\omega\) tal que \(L_\omega = q\). Si asumimos que la lista est谩 desordenada, ning煤n algoritmo cl谩sico conocido puede darnos un tiempo de b煤squeda mejor que \(\mathcal{O}(N)\). Es decir, el tiempo promedio de b煤squeda crece linealmente con \(N\), con el n煤mero de elementos entre los que buscamos. Esto es f谩cil de ver, pues para encontrar nuestro elemento tendremos que ir probando uno a uno los elementos de la lista. De esta forma en promedio tendremos que hacer \(N/2\) pruebas para encontrar el resultado deseado.
Este tipo de problemas se denominan problemas de b煤squeda no estructurada o problemas de b煤squeda en conjuntos de datos (datasets) no estructurados. Como acabamos de comentar, estos problemas requieren un tiempo polin贸mico (en concreto, lineal) para ser resueltos. Se engloban dentro de esta categor铆a tambi茅n problemas que presenten un dataset con alguna clase de estructura siempre que esta no se pueda aprovechar para acelerar la b煤squeda.
La ventaja que aporta el algoritmo de Grover es cuadr谩tica, ya que pasamos de necesitar un tiempo \(\mathcal{O}(N)\) a un tiempo \(\mathcal{O}(\sqrt{N})\). Esto puede parecer decepcionante si lo comparamos con la mejora exponencial que promete el algoritmo de Shor, pero est谩 lejos de serlo. Aunque a priori no parezca una mejora sustancial, cuando tratamos con valores suficientemente grandes de \(N\) (datasets inmenso), la mejora en tiempo respecto a su contrapartida cl谩sica puede ser de ordenes de magnitud, es decir, para nada despreciable.
El algoritmo de Grover no hace uso de la estructura interna del dataset en el que realiza la b煤squeda, lo cual lo hace gen茅rico y aplicable a una gran variedad de casos. Los problemas de b煤squeda aparecen por doquier en las ciencias computacionales, con lo que una mejora en la eficiencia de estos es de gran inter茅s. Adem谩s, este algoritmo no solo nos sirve para b煤squedas, sino que nos sirve como subrutina para conseguir un aumento de velocidad cuadr谩tico en otros algoritmos. A esto 煤ltimo se lo denomina el truco de la amplificaci贸n de la amplitud.
En estas notas vamos a ver todo lo necesario para entender el algoritmo de Grover, hablando tanto de matem谩tica como de implementaciones. La estructura de las notas es la siguiente. En la secci贸n 2. Explicaci贸n geom茅trica veremos una explicaci贸n geom茅trica del algoritmo, donde se usar谩 como ejemplo el caso m谩s simple (una soluci贸n, \(N=2^n\) y distribuci贸n uniforme) y se ver谩n las diferentes partes del algoritmo. En las siguientes secciones iremos generalizando el algoritmo a medida que relajamos las condiciones del ejemplo anterior. En la secci贸n 3. N煤mero conocido de soluciones veremos que pasa cuando tenemos un n煤mero \(M\) de soluciones (conocido \(M\)).
En la secci贸n 4. N煤mero desconocido de soluciones relajaremos la condici贸n de conocer el n煤mero \(M\) de soluciones y veremos que el algoritmo sigue siendo eficiente. Como continuaci贸n l贸gica de la secci贸n anterior, en la secci贸n 5. Conteo de soluciones (Quantum counting) veremos un algoritmo inspirado en el algoritmo de Shor que usa el operador de Grover para contar el n煤mero de soluciones (obtener \(M\)). En la secci贸n 6. Consideraciones sobre la implementaci贸n hablaremos sobre la implementaci贸n del difusor y como la formulaci贸n m谩s habitual del mismo es la responsable de imponer la condici贸n \(N=2^n\). Veremos en la subseci贸n Caso con N \neq 2^n. como podemos eliminar tambi茅n esta condici贸n. Por 煤ltimo, en la secci贸n 7. Distribuci贸n de probabilidad inicial aleatoria veremos que tambi茅n es posible relajar la condici贸n de partir de una distribuci贸n de probabilidad uniforme.
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.
