¿El oráculo en el algoritmo de Grover necesita contener información sobre la totalidad de la base de datos?

El algoritmo de Grover a menudo se describe como una forma de buscar una base de datos en $O(\sqrt{N})$tiempo. Para usarlo necesitamos una puerta de oráculo que represente alguna función$f$tal que$f^{-1}(1)$sea ​​la respuesta. Pero, ¿cómo se hace realmente un "oráculo de base de datos"?

Supongamos que tengo una matriz de números $a$ que contiene $w$ exactamente una vez y necesito encontrar el índice de $w$ . En una computadora clásica, cargaría la matriz en la memoria e iteraría hasta encontrar $w$ .

Por ejemplo, si $a = [3, 2, 0, 1, 2, 3]$ y $w = 0$ , I esperan obtener 2 como la respuesta (o 3 en 1-indexación).

¿Cómo represento esta matriz en una computadora cuántica y hago una puerta que devuelve $a_x$ para alguna $x$ ?

En particular, ¿necesita tener la totalidad de la "base de datos" dentro de la memoria cuántica (suponiendo que haya algunas formas de acceder a los registros clásicos desde las puertas cuánticas)?

$\newcommand{\xtarget}{\boldsymbol{x}_{\operatorname{target}}}\newcommand{\bs}[1]{{\boldsymbol #1}}\newcommand{\on}[1]{{\operatorname{#1}}}$ No, no lo hace.

El " oráculo " en el algoritmo de Grover es una función que, dado cualquier elemento , verifica si es el elemento que estamos buscando, digamos . Para hacer esto, el oráculo no necesita ningún conocimiento de todos los otros elementos que están en la base de datos .$\boldsymbol x_k$$\boldsymbol x_k$$\xtarget$$x_j$

Puede ser útil considerar un ejemplo más concreto. Supongamos que tiene una base de datos de números de teléfono de cuatro dígitos, con indica el elemento -ésimo en esta base de datos. Le interesa saber qué posición en la base de datos corresponde al elemento . Supongamos que el elemento 10000 de la base de datos es el único elemento, es decir, y para todos los .$20000$$\boldsymbol x_k$$k$$1234$$\bs x_{10000}=1234$$\bs x_k\neq 1234$$k\neq10000$

En el caso clásico, al estar la base de datos sin clasificar, no hay mejor manera que revisar cada uno de los elementos de la base de datos y comparar cada uno con el objetivo . Para hacer esto, solo necesita tener un algoritmo que, dado , devuelva if y contrario. Una forma equivalente de plantear este problema es decir que queremos un algoritmo que, dada una lista de pares , devuelva el par de tal manera que es lo que queremos. Por lo tanto, en nuestro caso, queremos un algoritmo que proporcione devuelve$1234$$\bs x_k$$\on{yes}$$\bs x_k=1234$$\on{no}$$\{(k,\bs x_k)\}_{k=1}^{20000}$$\bs x_k$$\{(k,\bs x_k)\}_{k=1}^{20000}$$(10000,\bs x_{10000}=1234)$. Tenga en cuenta que esto significa que la función que verifica cada par solo verifica las características de una parte del estado , a saber, la parte . De hecho, si este no fuera el caso, todo sería inútil porque no estaríamos recuperando ninguna información.$\bs x_k$

Este último encuadre del problema es el que uno debe tener en cuenta al pensar en el algoritmo de Grover.

En el caso cuántico, los pares convierten en los estados cuánticos (o simplemente como generalmente se denotan), y la función oracular solo verifica esa parte de la información almacenada en coincide con el objetivo . La salida del procedimiento es el estado . Ahora, ya sabemos parte de este estado , porque estaba codificado en el oráculo: sabemos que la segunda parte de la información codificada en es$(k, \bs x_k)$$|\psi_k\rangle$$|k\rangle$$|\psi_k\rangle$$|\psi_{10000}\rangle$$|\psi_{10000}\rangle$$1234$, porque eso es lo que estábamos buscando en primer lugar, y es la información que se codificó en el oráculo mismo. Sin embargo , el estado también contiene información adicional , a saber, la posición en la base de datos: . Esta información no se usó para construir el oráculo , y es la información que obtenemos al ejecutar el algoritmo.$|\psi_{10000}\rangle$ $10000$

Finalmente, tenga en cuenta que el oráculo no sabe nada sobre el contenido de la base de datos completa. Solo implementa coherentemente una función que verifica un solo estado contra su objetivo. Sin embargo, el hecho de que esta puerta funcione de manera coherente significa que se puede ingresar a esta función de verificación una superposición de muchos (posiblemente todos) los elementos de la base de datos y obtener una salida que contiene información global sobre todos los elementos de la base de datos.$|\psi_k\rangle$

Construiría una función tal que primero acceda al elemento -th de su matriz y luego lo compare con . Una implementación real podría acceder a la matriz codificada en qubits de entrada adicionales (parámetros) como si fueran bits.$f$$f(x)$$x$$w$