¿Qué aplicaciones tiene el algoritmo de búsqueda de Grover?

Además de los que mencionó, otra aplicación del algoritmo de Grover (modificado) que conozco es resolver el problema de colisión en la teoría de la complejidad, la computación cuántica y las matemáticas computacionales . También se llama algoritmo BHT .

Introducción :

El problema de colisión se refiere con mayor frecuencia a la versión 2 a 1 que fue descrita por Scott Aaronson en su tesis doctoral. Dado que es par y una función sabemos de antemano que es 1 a 1 o 2 a 1. Solo se nos permite hacer consultas sobre el valor de para cualquier $n$ $f:\{1,...,n\}\to\{1,...,n\}$ $f$ $f(i)$ . El problema luego pregunta cuántas consultas debemos hacer para determinar con certeza si es 1 a 1 o 2 a 1. $i\in\{1,2,...,n\}$ $f$

Resolver la versión 2-a-1 de manera determinista requiere consultas, y en general distinguir las funciones r-a-1 de las funciones 1-a-1 requiere consultas. $n/2+1$ $n/r+1$

Solución determinista clásica :

Esta es una aplicación directa del principio de casillero: si una función es r-a-1, entonces después de consultas, se garantiza que hemos encontrado una colisión. Si una función es 1 a 1, entonces no existe colisión. Si no tenemos suerte, entonces las consultas podrían devolver respuestas distintas. Por lo tanto, consultas son necesarias. $n/r+1$ $n/r$ $n/r+1$

Solución clásica aleatorizada :

Si permitimos la aleatoriedad, el problema es más fácil. Según la paradoja del cumpleaños, si elegimos consultas (distintas) al azar, entonces con alta probabilidad encontramos una colisión en cualquier función fija 2 a 1 después de consultas. $\Theta(\sqrt{n})$

Solución Quantum BHT :

Intuitivamente, el algoritmo combina la aceleración de la raíz cuadrada de la paradoja del cumpleaños usando aleatoriedad (clásica) con la aceleración de la raíz cuadrada del algoritmo de Grover (cuántico).

En primer lugar, entradas a se seleccionan al azar y se consulta a todos ellos. Si hay una colisión entre estas entradas, entonces devolvemos el par de entradas en colisión. De lo contrario, todas estas entradas se asignan a valores distintos por . Luego, el algoritmo de Grover se usa para encontrar una nueva entrada para que colisiona. Dado que sólo hay tales entradas a , el algoritmo de Grover puede encontrar uno (si existe) haciendo solamente $n^{1/3}$ $f$ $f$ $f$ $f$ $n^{2/3}$ $f$ $\mathcal{O}(\sqrt{n^{2/3}})=\mathcal{O}(n^{1/3})$ $f$

Fuentes:

Sanchayan Dutta
fuente

n^{1 / 3}

$n^{1/3}$

f

$f$

x

$x$

f (x)

$f(x)$ . Ahora si

f (x)

$f(x)$ es 2 a 1, hay

n^{1 / 3}

$n^{1/3}$ valores

x

$x$ Todavía no probado que colisionan con los probados. Entonces, defina una función que verifique "no probado y colisiona". Esto define las entradas marcadas. La colisión es fácil de probar con la lista ordenada de valores

f (x)

$f(x)$ . Al conocer el número exacto de entradas marcadas (si es 2 a 1), Grover's (casi) garantiza una solución.

DaftWullie

@DaftWullie Sí, eso tiene sentido. El algoritmo de Grover no garantiza una solución, pero tiene una alta probabilidad de proporcionar la solución correcta. ¿Pero no es eso bastante obvio de la descripción de Wikipedia en sí? No estoy seguro de entender el punto o la objeción que estás haciendo. ¿Me estoy perdiendo de algo?

Sanchayan Dutta

Todo lo que puedo decir es que no era obvio para mí . En la primera lectura, entendí (falsamente) que para Grover, en lugar de preparar una superposición de todos los estados posibles, solo preparó una superposición sobre los que aún no se han probado. Pero eso parecía crucial para la forma en que se explicaba la aceleración. Además, inicialmente me preocupaba cómo se verificaban las colisiones: ¿qué pares se verificaban para detectar colisiones y qué tan eficientemente se podía calcular la colisión?

DaftWullie

@DaftWullie Ah, está bien. Entiendo tu punto. Wikipedia no entra en tantos detalles del algoritmo. Siempre puede consultar el documento original ( arxiv.org/abs/quant-ph/9705002 ) para obtener los detalles (lo que supongo que ya hizo). Más adelante, intentaré ampliar esta respuesta para incluir todos los detalles. Todavía estoy leyendo el periódico.

Sanchayan Dutta

A menos que los qubits y las puertas cuánticas resulten increíblemente más baratas que los bits y las puertas clásicas, cualquier discusión sobre BHT debe incluir la advertencia de que los costos superan la búsqueda de colisión clásica de vanguardia con la máquina van Oorschot-Wiener. Consulte cr.yp.to/papers.html#collisioncost o blog.cr.yp.to/20171017-collisions.html para más detalles. (Esta última es una respuesta a una supuesta mejora en BHT que dice ser más rentable que la búsqueda de colisión clásica.)

Squeamish Ossifrage

El algoritmo de Grover se puede usar para resolver cualquier problema de optimización numérica más rápido que la búsqueda de fuerza bruta, porque cualquier problema de optimización se puede formular como un problema de búsqueda (donde está buscando una salida de función mayor / menor que alguna fija $M$ dentro de cada ejecución, y repite para un número logarítmico de ejecuciones utilizando la búsqueda binaria para llegar al punto óptimo $M$ ): https://epubs.siam.org/doi/abs/10.1137/040605072?journalCode=sjope8 .

De hecho, el algoritmo de Grover es el algoritmo cuántico más conocido para muchos problemas de optimización difíciles (como los que completan NP) que no tienen mucha estructura que sea capaz de un algoritmo clásico más inteligente que la búsqueda de fuerza bruta: https: // link.springer.com/chapter/10.1007/978-3-540-78773-0_67 .

tparker
fuente

¿Qué aplicaciones tiene el algoritmo de búsqueda de Grover?

Respuestas: