Oracle Construction para el algoritmo de Grover

En "Computación cuántica e información cuántica" de Mike e Ike, el algoritmo de Grover se explica con gran detalle. Sin embargo, en el libro, y en todas las explicaciones que he encontrado en línea para el algoritmo de Grover, parece que no se menciona cómo se construye el Oráculo de Grover, a menos que ya sepamos qué estado es lo que estamos buscando, lo que frustra el propósito de algoritmo. Específicamente, mi pregunta es la siguiente: dado algo de f (x) tal que para algún valor de x, f (x) = 1, pero para todos los demás, f (x) = 0, ¿cómo se construye un oráculo que nos sacará de nuestro estado inicial arbitrario | x> | y> to | x> | y + f (x)>? Se agradecería mucho la mayor cantidad de detalles explícitos posible (¿quizás un ejemplo?). Si tal construcción para cualquier función arbitraria es posible con Hadamard, Pauli u otras puertas cuánticas estándar,

quantum-computing quantum-information oracles search-problem black-box Será
fuente

"Aquí parece no mencionarse cómo se construye el Oráculo de Grover, a menos que ya sepamos qué estado es lo que estamos buscando, derrotando el propósito del algoritmo" ... "El Oráculo de Grover" es el problema a resolver. No lo construyes. Se le otorga (acceso de oráculo) y se le pide que realice un cálculo para descubrir el valor. Si ayuda, pretender que yo construyo el oráculo, y luego pedir que para resolver el problema. (Además, tenga en cuenta que leer / escribir / preparar una base de datos de

elementos lleva más tiempo que ejecutar

de Grover

N

$N$

Algoritmo

time.)

\sqrt{N}

$\sqrt{N}$

Daniel Apon el

Pero, ¿qué pasa si en lugar de recibir el oráculo, se nos da algo de f (x)? Imagine que estamos resolviendo un problema de 3-SAT y queremos usar Grover para proporcionar una solución rápida. Conocemos la f (x) en cuestión (las cláusulas de verdad 3-SAT), pero no necesariamente sabemos qué cadena de bits x producirá un resultado verdadero cuando se conecta al 3-SAT. ¿No debe haber una manera de construir un oráculo a partir de la función 3-SAT para encontrar la cadena de bits correcta? Si no existe, y es, como sugiere, algo que debe ser proporcionado por otra persona, el algoritmo de Grover parece bastante artificial, simplemente un ejercicio que se le da.

Será el

Respuestas:

El oráculo es básicamente solo una implementación del predicado para el que desea buscar una solución satisfactoria.

Por ejemplo, suponga que tiene un problema de 3 sat.

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

O, en forma de tabla, cada fila es una cláusula 3, x significa "esta variable falsa", o significa "esta variable verdadera" y espacio significa "no en la cláusula":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Ahora haga un circuito que calcule si la entrada es una solución, como esta:

Ahora, para convertir su circuito en un oráculo, golpee el bit de salida con una compuerta Z y elimine cualquier basura que haya realizado (es decir, ejecute el circuito de cómputo en orden inverso):

Eso es todo al respecto. Calcule el predicado, golpee el resultado con una Z, discuta el predicado. Eso es un oráculo.

Itere los pasos de difusión con pasos de oráculo, y tendrá una búsqueda rápida :

... aunque probablemente debería elegir un ejemplo con menos soluciones, por lo que el progreso es gradual (en lugar de girar a lo largo del plano de estado de solución de inicio en más de 90 grados por paso como lo es mi ejemplo).

Craig Gidney
fuente

Gracias, esto fue inmensamente útil. Increíblemente claro, respondí todo lo que pregunté (¡e incluso usé puertas cuánticas comunes!) ¿Hay alguna razón por la que decidas cambiar todos tus qubits iniciales al estado | 1> antes de colocarlos en superposición con las puertas Hadamard en lugar de simplemente poner el | 0 > qubits estatales a través de Hadamards (es decir, ¿hay alguna ventaja para esto?) Además, ¿qué operación es esa para sus pasos de difusión? Parece una X controlada, pero ¿estás usando | 1> 's o | 0>' s como controles?

Será

(\frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩)^{\otimes n}

$(\frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle)^{\otimes n}$

¡Fantástica respuesta, y gracias por el enlace a algassert.com/quirk !

Frédéric Grosshans