Algoritmo de Grover: ¿dónde está la lista?

15

Se utiliza el algoritmo de Grover, entre otras cosas, para buscar un elemento y en una lista desordenada de elementos [x0,x1,...,xn1] de longitud n . A pesar de que hay muchas preguntas aquí sobre este tema, todavía extraño el punto.

Buscando en una lista, la forma clásica

Normalmente, me gustaría diseñar una función de búsqueda de esta manera

search([x0,x1,...,xn1],y)=iNsuch that xi=y
Así que doy la lista y el elemento deseado como entradas, y recibo la posición del elemento en la lista como salida. Creo que he entendido que la información sobrey está incrustado en el algoritmo a través de la puerta oráculoO , por lo que nuestra función se convierte en
searchy([x1,x2,...,xn])=iNsuch that xi=y
Hagamos un ejemplo práctico. Considera buscar el as de espadas1 en una secuencia de 8 cartas de unmazo estándar de 52 cartas:

barajado barajado

La lista de longitud 8 es [x0=J, x1=10, x2=4, x3=Q, x4=3, x5=1, x6=6, x7=6] .

El elemento deseado es x5 . Debo obtener search(cards)=5 . Cada tarjeta se puede codificar con log252=6 bits, la lista tiene 8 elementos, por lo que necesitamos 6×8=48 bits para codificar la lista. En este caso, el oráculo O implementará la función:

f(x)={1,x=10,otherwise

Sin embargo, la entrada del algoritmo de Grover no es un estado de 48 qubits.

(Nota: la imagen del mazo barajado se toma desde aquí )

Grover y su oráculo

(Por ejemplo. Varias fuentes aquí - explica gráficamente) dicen que la entrada del algoritmo es diferente: la entrada es un estado tomado de la espacio de búsqueda S={0,1,2,...,N}={0,1,2,...,7} donde N es el número de elementos de la lista. Cada número corresponde a la posición de un elemento en la lista.

La entrada de search() ahora es un log28=3 qubit vector |ψ , que debe ser una superposición de todos los elementos en el espacio de búsqueda S .

Sabemos

  • |03qubits=|000 corresponde aJ ;
  • |13qubits=|001 corresponde a10 ;
  • |23qubits=|010 corresponde a4 ;
  • |53qubits=|101 corresponde a1 que es el elemento deseado;
  • y así...

En este caso tenemos que

search(|ψ)=|53qubits
Pero en este caso, nuestro oráculo tendrían que implementar la función
f(|ψ)={1,|ψ=|53qubits0,otherwise

Construir el oráculo requiere que sepamos que está en la posición 5. ¿Cuál es el punto de ejecutar el algoritmo si ya hemos buscado el elemento para construir el oráculo?

incud
fuente
También tengo dificultades para comprender la ventaja del algoritmo de Grover. Supongamos que tengo N elementos en la lista. En cada llamada al Oráculo, ¿evaluó todas las posibilidades de N? Incluso si la evaluación es muy rápida, pero si aún necesitamos iterar sobre todas las configuraciones, la complejidad de la evaluación de Oracle es O (N). Entonces, el algoritmo de Grover no parece ser más rápido que la búsqueda tonta. ¿Es esto correcto?
Sanparith Marukatat
@SanparithMarukatat No es correcto. Los elementos de su lista son los términos de la superposición del estado involucrado en la búsqueda. Cuando Oracle opera en este estado, cuenta como una sola operación. La capacidad del Oráculo para marcar el término buscado de su superposición es una parte fundamental de la visión de Grover. Para comprender el algoritmo de Grover, le recomiendo que primero comprenda cómo ocurre esta marcación del estado deseado. Después, asegúrese de comprender el papel del estado en el Oracle. |
R. Chopin
Si comprende eso, entonces debe estudiar el operador que puede aumentar la amplitud del término deseado en la superposición y, al mismo tiempo, disminuir la amplitud de los términos no deseados de la superposición. Para mí, la forma más fácil de acercarse a Grover es mirar al operador inverso sobre la media. (Algunas personas toman la vista geométrica, pero no la encuentro tan clara).
R. Chopin

Respuestas:

10

Si tiene 8 elementos en la lista (como en el ejemplo de su tarjeta), la entrada del oráculo es de 3 (qu) bits. El número de cartas en el mazo (52) es irrelevante, solo necesitas 3 bits para codificar 8 cartas.

Puede pensar que 3 bits codifican la posición en la lista de la tarjeta que está buscando; entonces no sabes la posición, pero el oráculo sí lo sabe. Entonces, si está buscando el as de espadas, entonces el oráculo sabe que el as de espadas es la sexta carta (o la quinta cuenta desde cero) e implementa la función

f(x)={1,if x = 5, or binary '101'0,otherwise

PD: Es mejor pensar en el algoritmo de Grover de manera diferente: tienes un oráculo que implementa una función booleana que genera para una sola combinación de bits de entrada, de lo contrario genera cero, y tu tarea es encontrar la combinación. El problema tiene la misma complejidad que buscar en una lista o base de datos sin clasificar, es por eso que el algoritmo de Grover generalmente se describe como buscar en una base de datos sin clasificar. Pero la aplicación del algoritmo a una búsqueda en la base de datos del mundo real plantea cuestiones que están más allá del algoritmo mismo. El algoritmo de Grover solo está buscando lo que el oráculo sabe.1

kludg
fuente
Sí, lo siento, ese 6 era de una edición anterior
incluido
2
Gracias por su respuesta. Arreglé la escritura incorrecta. ¿Cuál es el punto de ejecutar el algoritmo si para construir el oráculo necesito saber la posición del elemento buscado?
incud
1
@incud De hecho, no tiene sentido. He actualizado la respuesta.
kludg
" El algoritmo de Grover solo está buscando lo que el oráculo sabe ": no necesariamente. El oráculo puede estar buscando solo alguna propiedad específica de la entrada, de modo que el resultado que se obtiene al final contenga más información que la codificada en el oráculo itsef. Un ejemplo típico es buscar en una guía telefónica. El oráculo "pide" un registro adjunto a un nombre específico, pero una vez que se encuentra el registro correcto, también se obtiene la información adicional del número de teléfono adjunto a ese registro, que no estaba codificado en absoluto en el oráculo
glS
4

Si bien quizás sea más fácil para nosotros pensar que la función del oráculo ya ha calculado todos estos valores, eso no es lo que está haciendo. En el caso que describió, el oráculo tiene 8 entradas posibles (es decir, codificadas en 3 (qu) bits), y el oráculo hace todo el cálculo que necesita sobre la marcha . Entonces, en el momento en que intenta evaluar el oráculo para algún valor , el oráculo busca (en este caso) la tarjeta que indica el valor de xxxcorresponde a, y luego verifica si esa tarjeta es la tarjeta marcada. La idea es que cada vez que llamas al oráculo, pasa por ese proceso una vez. En general, evalúa la función varias veces que es igual a la cantidad de veces que llama al oráculo. El objetivo de cualquier algoritmo de búsqueda es llamar a ese oráculo tan pocas veces como sea posible.

En caso de que esto suene un poco circular (dada una entrada x , encuentre a qué tarjeta corresponde), recuerde que su tabla de búsqueda para qué corresponde a qué tarjeta se puede ordenar, que es una pregunta de búsqueda diferente, más simple y mucho más rápida.x

Las diferencias clave en su ejemplo en comparación con un escenario de uso más realista son:

  • El espacio de búsqueda suele ser masivo. No hay una perspectiva realista de precalcular todos los valores. De hecho, eso es exactamente lo que estamos tratando de evitar.

  • Por lo general, en realidad no decimos 'encuentra el as de espadas'. En cambio, hay una f(x) que no es trivial para evaluar y probar si es el elemento 'marcado' o no. El hecho de que el oráculo pueda tardar bastante tiempo en evaluarse, incluso para una sola entrada, es lo que hace que el oráculo sea la parte costosa de implementar (y todas las otras puertas se otorgan de forma gratuita) y por qué necesita minimizar la cantidad de llamadas .x

Entonces, realmente, la forma en que una búsqueda clásica funcionaría en su problema es: elija una al azar. Evalúe y = f ( x ) . Si y = 1 , devuelve x , de lo contrario repita. Mientras que el efecto neto de f ( x ) es 'es la entrada x 0xy=f(x)y=1xf(x)x0 , la entrada marcada?', Ese no es el cálculo real que hace.

DaftWullie
fuente
2

La pregunta es en última instancia: "¿Cuál es el punto de ejecutar el algoritmo si ya hemos buscado el elemento para construir el oráculo?"

Si bien alguien preconstruyó el oráculo, es posible que no haya sido la persona que lo utilizó.

El algoritmo de Grover requiere que el oráculo sea consultado no más de size of list . Naturalmente, no podemos esperar búsquedas de bases de datos respectivas, como se propuso anteriormente, respecto de las cuales no puedo comentar por falta de reputación, por ejemplo, 5 millones de claves devolverán el contenido que queremos si nuestro contenido no es abordado por ninguno de esos 5 millones de claves, pero al decir el Clave número 9 millones, que no está en nuestra muestra. ¿Cómo lo hace entonces el algoritmo de Grover?

Preguntamos al oráculo: ¿cuál es la respuesta que ya tiene para la pregunta que ya tiene? Incluso Mateus y Omar preguntarían el "símbolo del oráculo para un alfabeto particular" durante el tiempo de ejecución, ¿cuáles son las posiciones de su símbolo en la cadena que ya ha compilado? El oráculo dará la respuesta a nuestra consulta después de una sola consulta, pero en esta historia, por ejemplo, no puede simplemente escribir la respuesta como una cadena binaria y enviárnosla a través de un canal de comunicación clásico. Ocultará su respuesta en una superposición para que podamos extraerla.

Dejo que la fantasía o la metáfora se escapen en el siguiente fragmento: no escuchamos la respuesta la primera vez, y tenemos que pedirle al oráculo que repita la misma respuesta una y otra vez hasta que estemos seguros de lo que ha dicho el oráculo. excepto que comenzamos a alucinar por información errónea en el proceso de difusión si preguntamos demasiadas veces.

Brendan M
fuente
2

Dado el oráculo que ha proporcionado, la búsqueda no tiene sentido. Sin embargo, ese oráculo pierde el sentido del algoritmo de Grover porque buscar una carta en una baraja de cartas no es una búsqueda no estructurada porque, como dijiste, ya conoces el orden. Ergo, tu búsqueda está estructurada. La razón por la que se utiliza este oráculo es porque demuestra cómo se puede aplicar el de Grover sin tener que discutir un oráculo que haría que Grover sea útil porque dicho oráculo sería más complicado que valioso. Por lo tanto, un mejor oráculo para demostrar la utilidad de Grover podría ser algo como:

F(X)={1,X[0 0,...,3]+X[4 4,...,7 7]=10100 0,de otra manera

Lo que este oráculo implica es que tiene una búsqueda de 8 qubits donde toma los primeros cuatro qubits y los agrega a los segundos cuatro qubits y voltea M si la suma es 10 (1010 en binario). La diferencia entre este oráculo y el que proporcionó es que este oráculo prueba un patrón (los operandos suman 10) mientras que el suyo prueba la igualdad (es este índice 5). Este oráculo es mucho más difícil de construir, pero aprovecha el verdadero poder de Grover, que es, en esencia, una búsqueda de fuerza bruta donde su oráculo define el espacio de búsqueda.

Woody1193
fuente