Se utiliza el algoritmo de Grover, entre otras cosas, para buscar un elemento $\mathbf{y}$ en una lista desordenada de elementos $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ 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

$$\mathrm{search}([\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}], \mathbf{y}) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{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 sobre$\mathbf{y}$ está incrustado en el algoritmo a través de la puerta oráculo$O$ , por lo que nuestra función se convierte en $$\mathrm{search}_\mathbf{y}([\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n] ) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$$ Hagamos un ejemplo práctico. Considera buscar el as de espadas$1\spadesuit$ en una secuencia de 8 cartas de unmazo estándar de 52 cartas:

La lista de longitud $8$ es $[ \mathbf{x}_0 = J\clubsuit,$ $\mathbf{x}_1 = 10\diamondsuit,$ $\mathbf{x}_2 = 4\heartsuit,$ $\mathbf{x}_3 = Q\clubsuit,$ $\mathbf{x}_4 = 3\spadesuit,$ $\mathbf{x}_5 = 1\spadesuit,$ $\mathbf{x}_6 = 6\spadesuit,$ $\mathbf{x}_7 = 6\clubsuit]$ .

El elemento deseado es $\mathbf{x}_5$ . Debo obtener $\mathrm{search}_{\spadesuit}(cards) = 5$ . Cada tarjeta se puede codificar con $\lceil{\log_2 52}\rceil = 6$ bits, la lista tiene $8$ elementos, por lo que necesitamos $6\times 8 = 48$ bits para codificar la lista. En este caso, el oráculo $O$ implementará la función:

$$f(\mathbf{x}) = \begin{cases} 1, & \mathbf{x} = 1\spadesuit \\ 0, & \text{otherwise} \end{cases}$$

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 $\mathrm{search}_{\spadesuit}(\cdot)$ ahora es un $\lceil \log_2 8 \rceil = 3$ qubit vector $|\psi\rangle$ , que debe ser una superposición de todos los elementos en el espacio de búsqueda $S$ .

Sabemos

• $|0_{3\text{qubits}}\rangle = |000\rangle$ corresponde a$J\clubsuit$ ;
• $|1_{3\text{qubits}}\rangle = |001\rangle$ corresponde a$10\diamondsuit$ ;
• $|2_{3\text{qubits}}\rangle = |010\rangle$ corresponde a$4\heartsuit$ ;
• $|5_{3\text{qubits}}\rangle = |101\rangle$ corresponde a$1\spadesuit$ que es el elemento deseado;
• y así...

En este caso tenemos que

$$\mathrm{search}_{\spadesuit}(|\psi\rangle) = |5_{3\text{qubits}}\rangle$$ Pero en este caso, nuestro oráculo tendrían que implementar la función $$f(|\psi\rangle) = \begin{cases} 1, & |\psi\rangle = |5_{3\text{qubits}}\rangle \\ 0, & \text{otherwise} \end{cases}$$

Construir el oráculo requiere que sepamos que $\spadesuit$ 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?

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(\mathbf{x}) = \begin{cases} 1, & \text{if x = 5, or binary '101'} \\ 0, & \text{otherwise} \end{cases}$$

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$

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 $x$$x$corresponde 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 $x$$y=f(x)$$y=1$$x$$f(x)$$x_0$ , la entrada marcada?', Ese no es el cálculo real que hace.

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 $\sqrt{\text{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.

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) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases}$$

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.