¿Podemos acelerar el algoritmo de Grover ejecutando procesos paralelos?

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?

classical-computing grovers-algorithm cryptography kelalaka
fuente

Respuestas:

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

H^{\otimes norte} ({yo}_{norte} - 2 El | 0 0 ⟩ ⟨ 0 0 {El |}^{\otimes norte}) H^{\otimes norte} U_{S},

$H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S,$ a partir de un estado inicial

(H | 0 ⟩)^{\otimes n}

$(H|0\rangle)^{\otimes n}$ . Esto lleva tiempo

Θ (\sqrt{N})

$\Theta(\sqrt{N})$ . (Estoy usando

I_{n}

$\mathbb{I}_n$ para denotar lamatriz de identidad

2^{n} \times 2^{n}

$2^n\times 2^n$ ).

Podría reemplazar esto con $2^k$ copias paralelas, cada una en un índice por un $x\in\{0,1\}^k$ , usando

(I_{k} \otimes H^{\otimes (n - k)}) I_{k} \otimes (I_{n - k} - 2 | 0 ⟩ ⟨ 0 |^{\otimes (n - k)}) (I_{k} \otimes H^{\otimes (n - k)}) U_{S}

$\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)\mathbb{I}_k\otimes(\mathbb{I}_{n-k}-2|0\rangle\langle 0|^{\otimes (n-k)})\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)U_S$ y partiendo de un estado

| x ⟩ (H | 0 ⟩)^{\otimes (n - k)}

$|x\rangle(H|0\rangle)^{\otimes(n-k)}$ El tiempo requerido para el funcionamiento de estos sería reducido a

O (\sqrt{N / K})

$O(\sqrt{N/K})$ , a costa de requerir

K

$K$ veces 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 ( $\sqrt{K}$ ) mejora (al igual que si tiene $K$ núcleos clásicos paralelos, la mejor mejora que puede obtener es un factor de $K$ ), 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 un $\sqrt{K}$ 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 de $N$ .

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 argumento

x

$x$

glS

va al infinito pero

no. Su problema se agrava pero sus recursos siguen siendo pocos.

N

$N$

K

$K$

AHusain

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

$K$

Niel de Beaudrap

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.

$\sqrt{N}$ $N_1,N_2$ $\sqrt{N_1},\sqrt{N_2}$

\sqrt{N} = \sqrt{N_{1} + N_{2}} \leq \sqrt{N_{1}} + \sqrt{N_{2}}

$\sqrt{N} = \sqrt{N_1+N_2} \le \sqrt{N_1} + \sqrt{N_2}$

$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

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á

@ 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á

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 haces

k \in O (1)

$k \in O(1)$ procesos paralelos de Grover, pero como sugiere la respuesta de DaftWullie (y considerando el postprocesamiento clásico), la complejidad de profundidad va de

\sqrt{N}

$\sqrt N$ a

\log (k) \sqrt{N / k}

$\log(k) \sqrt{N/k}$ para

k (N) \in Ω (1)

$k(N) \in \Omega(1)$ procesos paralelos de Grover, que es una mejora por un factor de

\sqrt{k} / \log (k)

$\sqrt{k}/\!\!\;\log(k)$ (el factor de registro proviene de identificar cuál de los dos, si algún proceso, encuentra una solución).

Niel de Beaudrap