¿Cómo funciona el operador de difusión Grover y por qué es óptimo?

15

En esta respuesta , se explica el algoritmo de Grover. La explicación indica que el algoritmo depende en gran medida del operador de difusión Grover , pero no proporciona detalles sobre el funcionamiento interno de este operador.

Brevemente, el Operador de Difusión Grover crea una 'inversión sobre la media' para hacer iterativamente las pequeñas diferencias en los pasos anteriores lo suficientemente grandes como para ser medibles.

Las preguntas son ahora:

  1. ¿Cómo logra esto el operador de difusión Grover?
  2. ¿Por qué es la O resultante ( O(n)en tiempo total para buscar una base de datos desordenada óptima?
Lagarto discreto
fuente
1
Solo un comentario sobre la segunda pregunta. Hay trabajos para mostrar que la pista del estado en el algoritmo de Grover sigue exactamente la geodésica que conecta el estado inicial del algoritmo y el estado de destino. Entonces es óptimo.
XXDD

Respuestas:

5

Dado que la pregunta original era sobre la descripción de un laico, ofrezco una solución ligeramente diferente que es quizás más fácil de entender (depende del fondo), basada en una evolución continua en el tiempo. (Sin embargo, no pretendo que sea adecuado para un laico).

Partimos de un estado inicial que es una superposición uniforme de todos los estados, y que son el objetivo de encontrar un estado| xque puede ser reconocida como la respuesta correcta (suponiendo que no es exactamente uno de esos estados, aunque esto se puede generalizar). Para hacer esto, evolucionamos en el tiempo bajo la acción de un Hamiltoniano H=| xx| +| PsiPsi| . La característica realmente hermosa de la búsqueda de Grover es que en este punto, podemos reducir las matemáticas a un subespacio de solo dos estados

El |ψ=12nortey{0 0,1}norteEl |y
El |X
H=El |XXEl |+El |ψψEl |.
{El |X,El |ψ}, en lugar de requerir los . Es más fácil describir si hacemos una base ortonormal a partir de estos estados, { | x , | Psi } , donde | Psi = 12norte{El |X,El |ψ} Usando esta base, la evolución del tiempoe-iHt| Psipuede ser escrito como e-it(I+2-nZ+
El |ψ=12norte-1y{0 0,1}norte:yXEl |y.
mi-yoHtEl |ψ dondeXyZson las matrices Pauli estándar. Esto puede reescribirse como e-it(Icos(t
mi-yot(yo+2-norteZ+2norte-12norteX)(12norte1-12norte),
XZ Entonces, si evolucionamos por un tiempot=π
eit(Icos(t2n/2)i12n/2sin(t2n/2)(Z+X2n1))(12n112n).
, e ignorando las fases globales, el estado final es 1t=π22n/2 En otras palabras, con probabilidad 1, obtenemos el estado| x
12n/2(Z+X2n1)(12n112n)=(12n2n12n)+(112n2n12n)=(10).
|x que estábamos buscando. La descripción habitual basada en el circuito de la búsqueda de Grover es realmente esta evolución continua del tiempo dividida en pasos discretos, con la ligera desventaja de que generalmente no puede obtener exactamente la probabilidad 1 de su resultado, solo muy cerca de ella.

H~=5HH~2n/22n/2k1/k

|x|y

DaftWullie
fuente
4

re=-HnorteU0 0HnorteU0 0

U0 0El |0 0norte=-El |0 0norte,U0 0El |X=El |XparaEl |XEl |0 0norte.

U0 0U0 0=yo-2El |0 0norte0 0norteEl |

re=2El |++El |-yo,
dónde El |+=2-norte/ /2(El |0 0+El |1)norte.

Escribiendo un estado |ψ=α|++β|+ where |+ is orthogonal to |+ (i.e. ++=0) gives that D|ψ=α|+β|+.

This gives2 that the diffusion operator is a reflection about |+

As the other part of Grover's algorithm is also a reflection, these combine to rotate the current state closer to the 'searched-for' value x0. This angle decreases linearly with the number of rotations (until it overshoots the searched-for value), giving that the probability of correctly measuring the correct value increases quadratically.

Bennet et. al. showed that this is optimal. By taking a classical solution to an NP-problem, Grover's algorithm can be used to quadratically speed this up. However, taking a language LA={y:xA(x)=y} for a length preserving function A (here, an oracle), any bounded-error oracle based quantum turing machine cannot accept this language in a time T(n)=o(2n/2).

This is achieved by taking a set of oracles where |1n has no inverse (so is not contained in the language). However, this is contained in some new language LAy by definition. The difference in probabilities of a machine accepting LA and a different machine accepting LAy in time T(n) is then less than 1/3 and so neither language is accepted and Grover's algorithm is indeed asymptotically optimal.3

Zalka later showed that Grover's algorithm is exactly optimal.


1 In Grover's algorithm, minus signs can be moved round, so where the minus sign is, is somewhat arbitrary and doesn't necessarily have to be in the definition of the diffusion operator

2 alternatively, defining the diffusion operator without the minus sign gives a reflection about |+

3 Defining the machine using the oracle A as MA and the machine using oracle Ay as MAy, this is a due to the fact that there is a set S of bit strings, where the states of MA and MAy at a time t are ϵ-close4, with a cardinality <2T2/ϵ2. Each oracle where MA correctly decides if |1n is in LA can be mapped to 2nCard(S) oracles where MA fails to correctly decide if |1n is in that oracle's language. However, it must give one of the other 2n1 potential answers and so if T(n)=o(2n/2), la máquina no puede determinar la pertenencia a LUN.

4 Usando la distancia euclidiana, el doble de la distancia de rastreo

Mithrandir24601
fuente