¿Cómo se aplica el algoritmo de Grover a una base de datos?

Pregunta

Quiero usar el algoritmo de Grover para buscar en una base de datos no ordenada un elemento $x$ . Ahora surge la pregunta, ¿cómo inicializo el índice y el valor de la base de datos con los qubits?

Ejemplo

• Digamos que tengo $4$ qubits. Por lo tanto, $2 ^ 4 = 16$ valores clásicos se pueden mapear.
• Mi base de datos no ordenada $d$ tiene los siguientes elementos: $d [\text{Value}] = [3,2,0,1]$ .
• Quiero buscar $x = 2_d = 10_b = |10\rangle$ .
• Mi enfoque: indexar la base de datos $d$ con $d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$ . Registros $0$ y $1$ para el índice y registros $2$ y $3$ para el valor. Luego aplique el algoritmo de Grover solo a los registros $2$ y $3 (\text{Value})$ . ¿Se puede realizar esto? ¿Hay otro enfoque?

Lo que ya implementé ( en GitHub )

El "Algoritmo de Grover con 2, 3, 4 Qubits", pero lo que hace es simple: los bits se inicializan con $|0\rangle$ , el oráculo marcará mi solución $x$ (que es sólo un número como $2_d = 10_b$ ), la parte Grover aumentará la probabilidad de que el elemento seleccionado $x$ y disminuir todos los demás probabilidades y luego los qubits se leen por el ser mapeado a los bits clásicos. Dejamos que este proceso se ejecute varias veces seguidas y, por lo tanto, obtenga una distribución de probabilidad, donde la probabilidad más alta tiene nuestro elemento buscado $x$ .

La salida es siempre la misma que la marcada en el oráculo. ¿Cómo puedo generar más información de la salida que no conozco cuando construí el oráculo?

He estado trabajando en este problema también. Como principiante y programador clásico (es decir, no hablo de mecánica cuántica), es difícil comprender los conceptos sin ejemplos completos. He estado trabajando con la muestra de Microsoft Q # Database Search . Simplemente busca un índice / clave específico en la base de datos, lo que no es muy útil. He ampliado esa muestra para buscar una lista de valores en una base de datos y devolver la clave correspondiente.

Como con su ejemplo, hay un "registro de clave" de dos qubits para los índices y un registro de dos qubits separado para los valores. También hay un quinto "qubit marcado" que proviene de la muestra de Microsoft, para indicar cuándo se encuentra el valor deseado. Las claves y los valores se asocian mediante enredos. Eso se demuestra mejor con un circuito. Haga clic aquí para ver el circuito Quirk real .

Tenga en cuenta que este circuito contiene solo el oráculo. No implementa todo el algoritmo de Grover.

• Los dos qubits superiores son el registro clave, los dos siguientes son el registro de valores y el qubit inferior es el qubit marcado.
• La primera sección coloca el registro de clave en una superposición uniforme utilizando puertas Haramard, como lo requiere el algoritmo de Grover.
• La segunda sección es donde las claves están asociadas con los valores a través del enredo. Cada clave se enreda con un valor correspondiente en el registro de valores mediante la aplicación de puertas X (anti) controladas. Entonces, cuando el registro de clave es 0, entonces el registro de valor se establecerá en 3. Cuando la clave es 1, el valor se establece en 2, y así sucesivamente.
• La tercera sección del circuito es el oráculo de búsqueda. El registro del valor está enredado con el qubit marcado. En este ejemplo, el valor deseado es 2. Cuando el registro de valor contiene 2, el qubit marcado se establecerá en 1.
• El algoritmo de Grover examina el registro de clave y el qubit marcado. El oráculo de búsqueda observa el registro de valores y establece el qubit marcado. Esto hará que la clave 1 se amplifique cuando el valor sea 2.

Es interesante observar que las claves y los valores no se almacenan en los qubits, sino en el circuito / programa. Se podría decir que no es realmente una base de datos per se. Es más como una declaración de cambio / caso, pero que puede ejecutarse en una superposición de valores.

Para obtener más detalles, advertencias y código Q #, consulte mi repositorio de GitHub .

EDITAR: Algo que entiendo mejor desde que respondí ... tienes que invertir / deshacer el circuito como parte de cada iteración. En el código Q #, la llamada Adjoint StatePreparationOracle () dentro de la operación ReflectStart () maneja esto, por lo que no tuve que hacerlo explícitamente. No sé si Qiskit tiene una característica similar. Si he hecho la traducción correctamente, aquí hay un circuito completo para el ejemplo anterior.

$n=4$

Creo que es mejor pensar en el algoritmo de búsqueda cuántica como la optimización de una función, en lugar de buscar en una lista / base de datos. Aquí hay un artículo en el que trabajé donde la búsqueda cuántica se usa para resolver un problema de maximización combinatoria si desea profundizar en su comprensión del algoritmo.

También debe convertir el oráculo para que contenga la base de datos, como resultado, el Oracle general (Inversión de fase) tendrá dos subóculos para ver la figura.

El primer suboráculo que debe prepararse es el circuito de memoria, en contraste con el QRAM que almacena datos cuánticos (estado) en su cuerpo, este circuito de memoria (matriz) está preparado para almacenar solo información clásica en su marco. A continuación se muestra un ejemplo de este tipo de circuito que almacena una matriz de binarios [010, 110, 100, 011]: Para más información, lea este documento .