¿Podemos acelerar el algoritmo de Grover ejecutando procesos paralelos?

10

En computación clásica, podemos ejecutar la búsqueda de claves (por ejemplo, AES) ejecutando nodos de computación paralelos tantos como sea posible.

Está claro que también podemos ejecutar muchos algoritmos de Grover.

Mi pregunta es ; Es posible acelerar usando más de un algoritmo de Grover como en la informática clásica?

kelalaka
fuente

Respuestas:

6

¡Ciertamente! Imagina que tienes K=2k copias del oráculo de búsqueda US que puedes usar. Normalmente, te busca por iteración la acción

Hnorte(yonorte-2El |0 00 0El |norte)HnorteUS,
a partir de un estado inicial (HEl |0 0)norte . Esto lleva tiempo Θ(norte). (Estoy usandoyonortepara denotar lamatriz de identidad2norte×2norte).

Podría reemplazar esto con 2k copias paralelas, cada una en un índice por un X{0 0,1}k , usando

(IkH(nk))Ik(Ink2|00|(nk))(IkH(nk))US
y partiendo de un estado|x(H|0)(nk) El tiempo requerido para el funcionamiento de estos sería reducido aO(N/K), a costa de requerirKveces más espacio.

En un sentido de escala, uno podría considerar esto como un resultado irrelevante. Si tienes un número fijo de oráculos, K , entonces obtienes un número fijo ( K ) mejora (al igual que si tieneKnúcleos clásicos paralelos, la mejor mejora que puede obtener es un factor deK), y eso no cambia la escala. Pero sí cambia el tiempo de funcionamiento fundamental. Sabemos que el algoritmo de Grover es exactamente óptimo. Se necesita el tiempo mínimo absoluto posible con un solo oráculo. Entonces, sabiendo que obtienes unK mejora en el tiempo es útil con respecto a ese punto de referencia de un tiempo de funcionamiento específico en un valor específico deN.

DaftWullie
fuente
pero si haces esto, la comparación con el rendimiento clásico pierde parte de su significado, ¿no? Después de todo, también puede acelerar la búsqueda clásica ejecutando la operación que verifica si una dada es el objetivo en paralelo sobre todas las entradas. Eso claramente requiere suposiciones adicionales sobre los recursos disponibles, pero el mismo tipo de suposiciones que se hacen en su argumentox
glS
1
va al infinito pero K no. Su problema se agrava pero sus recursos siguen siendo pocos. NK
AHusain
1
Esta respuesta es correcta (aunque puede no ser óptima, como DaftWullie advierte). Esta es la misma actitud hacia la paralelización que uno toma en la complejidad del circuito clásico. Si desea una aceleración debido a la paralelización, busque la profundidad del circuito (porque coordinar múltiples procesos no reducirá el trabajo total). Ni siquiera importa si es constante --- o estás interesado en la mejora de la profundidad de la paralelización, o no lo estás. Al igual que con el cómputo cuántico en sí, ¡simplemente lanzar más computadoras a un problema no hace que todo sea mágicamente rápido! K
Niel de Beaudrap
3

En cierto sentido, si lo hiciéramos en paralelo en diferentes nodos, ahorraría tiempo para ejecutar. Pero si hablamos de complejidad (eso es a lo que generalmente nos referimos con la aceleración), necesitamos un poco de análisis.

NN1,N2N1,N2

N=N1+N2N1+N2

O notación

Sin embargo, eso aún sería interesante, especialmente si tenemos que agrupar hardware porque estamos limitados en número de qubits u otras limitaciones.

canadá
fuente
2
Para N1 = N2 sigue siendo una desigualdad: sqrt (2) * sqrt (N1) <2 * sqrt (N1)
Mariia Mykhailova
Oh de hecho. En mi cabeza $ \ sqrt {a b} = \ sqrt {a} \ sqrt {b} $ pensé. Debería dejar de responder aquí a medianoche y cuando esté cansado. Gracias por señalar eso.
Canadá
3
@ Canadá: existen al menos dos nociones diferentes de complejidad, ambas relevantes para acelerar. Uno es la complejidad del tamaño y el otro es la complejidad de la profundidad. A menos que se especifique lo contrario, a menudo preferimos considerar la complejidad del tamaño, pero la complejidad de la profundidad sigue siendo algo de gran interés en la complejidad computacional cuántica, por ejemplo en MBQC [arXiv: quant-ph / 0301052 , arXiv: 0704.1736 ] y resultados recientes en separaciones de profundidad incondicionales [arXiv: 1704.00690 ].
Niel de Beaudrap
@NieldeBeaudrap Pensé que la gente mira más en profundidad la complejidad. Pero para Grover, el tamaño y la complejidad de la profundidad son aproximadamente del mismo orden. Eso es cuadrático en el tamaño del problema (generalmente visto como el tamaño de una lista de N elementos). ¿Crees que mi enfoque aquí no es correcto?
Canadá
2
No está diciendo nada que esté mal , solo estoy señalando que está enfatizando indebidamente la complejidad del tamaño y realmente no está resolviendo el beneficio de la complejidad de la profundidad. No sucede mucho interesante si solo lo haceskO(1) procesos paralelos de Grover, pero como sugiere la respuesta de DaftWullie (y considerando el postprocesamiento clásico), la complejidad de profundidad va de norte a Iniciar sesión(k)norte/ /k para k(norte)Ω(1) procesos paralelos de Grover, que es una mejora por un factor de k/ /Iniciar sesión(k)(el factor de registro proviene de identificar cuál de los dos, si algún proceso, encuentra una solución).
Niel de Beaudrap