Algoritmo de Grover: ¿qué ingresar a Oracle?

Estoy confundido acerca de qué ingresar a Oracle en el algoritmo de Grover.

¿No necesitamos ingresar a Oracle lo que estamos buscando y dónde encontrar lo que estamos buscando, además de los estados cuánticos superpuestos?

Por ejemplo, supongamos que tenemos una lista de nombres de personas {"Alice", "Bob", "Corey", "Dio"}, y queremos saber si "Dio" está en la lista. Entonces, Oracle debería tomar como entrada y salida . Entiendo eso. $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$

¿Pero no necesitamos también ingresar la palabra "Dio" y la lista {"Alice", "Bob", "Corey", "Dio"} a Oracle? De lo contrario, ¿cómo puede Oracle devolver la salida? ¿No se menciona explícitamente ya que Oracle es una caja negra y no tenemos que pensar en cómo implementarlo?

Mi comprensión sobre Oracle es,

Oracle tiene la capacidad de reconocer si la palabra "Dio" está en la lista.
Para hacerlo, Oracle toma los estados cuánticos superpuestos como una entrada, donde cada estado cuántico representa el índice de la lista.
Entonces, ingrese a Oracle significa, verifique si la palabra "Dio" está en el índice 0 de la lista y devuelva caso afirmativo y devuelva contrario. $|00\rangle$ $-|00\rangle$ $|00\rangle$
En nuestro caso, Oracle devuelve . $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$
¿Pero qué hay de la lista y la palabra?

algorithm grovers-algorithm oracles Bick
fuente

Si bien no está redactado de la misma manera, creo que su pregunta es más o menos la misma que esta: el algoritmo de Grover: ¿dónde está la lista?

DaftWullie

Respuestas:

Aunque las explicaciones populares del algoritmo de Grover hablan de buscar en una lista, en realidad lo usa para buscar posibles entradas 0..N-1 a una función. El costo del algoritmo es donde es el número de entradas que desea buscar y es el costo de evaluar la función. Si desea que esa función busque en una lista, debe codificar la lista en la función. $O(\sqrt{N} \cdot F)$ $N$ $F$

La codificación dura de la función para usar una lista de elementos suele ser una muy mala idea, ya que tiende a hacer que igual a . Lo que haría que el costo total del algoritmo de Grover . ¿Qué tipo de derrotas el propósito, ya que . $N$ $F$ $O(N)$ $O(\sqrt{N} \cdot F) = O(\sqrt{N} \cdot N) = O(N^{1.5})$ $N^{1.5} > N$

Craig Gidney
fuente

¿No ingresaría una lista ordenada , haciendo la búsqueda mucho más rápida? Por supuesto, es posible que desee incluir el costo de ordenar la lista, pero supongo que aún aparece como general.

O (\sqrt{N} \log (N))

$O(\sqrt{N}\log(N))$

DaftWullie

@DaftWullie El problema es que Grover debe hacer una búsqueda bajo superposición, y esto requiere un circuito multiplexor con puertas N AND (u otras operaciones que no sean de Clifford). Una compuerta AND cuántica (es decir, un Toffoli) tiene un costo no despreciable al realizar la corrección de errores. Este costo también está técnicamente presente en la máquina clásica (es decir, la RAM tiene O (N) Y puertas), simplemente resulta insignificante e incluso evitable en ese contexto.

Craig Gidney,

No entiendo lo que dices. ¿Sería capaz de expresar una pregunta y responderla para mostrar los detalles? (No creo que pueda formular una pregunta lo suficientemente buena en este momento)

DaftWullie

@DaftWullie Creo que la pregunta sería algo así como "¿cómo le doy a una computadora cuántica acceso de lectura a una base de datos clásica y qué tan costosa es?".

Craig Gidney