Hispanopedia Wiki
Articulo de referencia

El algoritmo de Grover

En computación cuántica , el algoritmo de Grover , también conocido como algoritmo de búsqueda cuántica , es un algoritmo cuántico para búsqueda no estructurada que encuentra co...

Hispanopedia WikiContenido en espanolLectura gratuita

En computación cuántica , el algoritmo de Grover , también conocido como algoritmo de búsqueda cuántica , es un algoritmo cuántico para búsqueda no estructurada que encuentra con alta probabilidad la entrada única a una función de caja negra que produce un valor de salida particular, utilizando soloO(norte){\displaystyle O({\sqrt {N}})}evaluaciones de la función, dondenorte{\displaystyle N}es el tamaño del dominio de la función . Fue ideado por el científico informático indio - estadounidense Lov Grover en 1996. [ 1 ]

El problema análogo en computación clásica tendría una complejidad de consulta.O(norte){\displaystyle O(N)}(es decir, la función tendría que ser evaluada)O(norte){\displaystyle O(N)}veces: no hay mejor enfoque que probar todos los valores de entrada uno tras otro, lo que, en promedio, llevanorte/2{\displaystyle N/2}pasos). [ 1 ]

Charles H. Bennett , Ethan Bernstein, Gilles Brassard y Umesh Vazirani demostraron que cualquier solución cuántica al problema necesita evaluar la funciónΩ(norte){\displaystyle \Omega ({\sqrt {N}})}veces, por lo que el algoritmo de Grover es asintóticamente óptimo . [ 2 ] Dado que los algoritmos clásicos para problemas NP-completos requieren exponencialmente muchos pasos, y el algoritmo de Grover proporciona como máximo una aceleración cuadrática sobre la solución clásica para la búsqueda no estructurada, esto sugiere que el algoritmo de Grover por sí solo no proporcionará soluciones de tiempo polinomial para problemas NP-completos (ya que la raíz cuadrada de una función exponencial sigue siendo una función exponencial, no una función polinomial). [ 3 ]

A diferencia de otros algoritmos cuánticos, que pueden proporcionar una aceleración exponencial sobre sus contrapartes clásicas, el algoritmo de Grover proporciona solo una aceleración cuadrática. Sin embargo, incluso una aceleración cuadrática es considerable cuandonorte{\displaystyle N}es grande, y el algoritmo de Grover se puede aplicar para acelerar amplias clases de algoritmos. [ 3 ] El algoritmo de Grover podría descifrar por fuerza bruta una clave criptográfica simétrica de 128 bits en aproximadamente 2 64 iteraciones, o una clave de 256 bits en aproximadamente 2 128 iteraciones. Sin embargo, puede que no sea cierto que el algoritmo de Grover suponga un riesgo significativamente mayor para el cifrado que los algoritmos clásicos existentes. [ 4 ]

Aplicaciones y limitaciones

El algoritmo de Grover, junto con variantes como la amplificación de amplitud , puede utilizarse para acelerar una amplia gama de algoritmos. [ 5 ] [ 6 ] [ 7 ] En particular, los algoritmos para problemas NP-completos que contienen búsqueda exhaustiva como subrutina pueden acelerarse mediante el algoritmo de Grover. [ 6 ] El mejor algoritmo teórico actual, en términos de complejidad en el peor de los casos, para 3SAT es un ejemplo de ello. Los problemas genéricos de satisfacción de restricciones también experimentan aceleraciones cuadráticas con Grover. [ 8 ] Estos algoritmos no requieren que la entrada se proporcione en forma de oráculo, puesto que el algoritmo de Grover se aplica con una función explícita, por ejemplo, la función que comprueba que un conjunto de bits satisface una instancia de 3SAT. Sin embargo, no está claro si el algoritmo de Grover podría acelerar los mejores algoritmos prácticos para estos problemas.

El algoritmo de Grover también puede proporcionar aceleraciones demostrables para problemas de caja negra en complejidad de consulta cuántica , incluyendo la distinción de elementos [ 9 ] y el problema de colisión [ 10 ] (resuelto con el algoritmo de Brassard-Høyer-Tapp ). En este tipo de problemas, se trata la función oráculo f como una base de datos, y el objetivo es usar la consulta cuántica a esta función la menor cantidad de veces posible.

Criptografía

El algoritmo de Grover resuelve esencialmente la tarea de inversión de funciones . En términos generales, si tenemos una funcióny=F(incógnita){\displaystyle y=f(x)}que se puede evaluar en una computadora cuántica, el algoritmo de Grover nos permite calcularincógnita{\displaystyle x}cuando se day{\displaystyle y}En consecuencia, el algoritmo de Grover proporciona amplias aceleraciones asintóticas a muchos tipos de ataques de fuerza bruta contra la criptografía de clave simétrica , incluidos los ataques de colisión y los ataques de preimagen . [ 11 ] Sin embargo, este no es necesariamente el algoritmo más eficiente, ya que, por ejemplo, el algoritmo rho de Pollard es capaz de encontrar una colisión en SHA-2 de forma más eficiente que el algoritmo de Grover. [ 12 ]

Limitaciones

El artículo original de Grover describía el algoritmo como un algoritmo de búsqueda en bases de datos, y esta descripción sigue siendo común. En esta analogía, la base de datos es una tabla con todas las salidas de la función, indexadas por la entrada correspondiente. Sin embargo, esta base de datos no se representa explícitamente. En su lugar, se invoca un oráculo para evaluar un elemento mediante su índice. Leer una base de datos completa elemento por elemento y convertirla a dicha representación puede llevar mucho más tiempo que la búsqueda de Grover. Para tener en cuenta estos efectos, el algoritmo de Grover puede considerarse como la resolución de una ecuación o la satisfacción de una restricción . En tales aplicaciones, el oráculo es una forma de verificar la restricción y no está relacionado con el algoritmo de búsqueda. Esta separación suele impedir las optimizaciones algorítmicas, mientras que los algoritmos de búsqueda convencionales a menudo dependen de dichas optimizaciones y evitan la búsqueda exhaustiva. [ 13 ] Afortunadamente, es posible una implementación rápida del oráculo de Grover para muchos problemas de satisfacción de restricciones y optimización. [ 14 ]

La principal barrera para implementar una mejora de velocidad a partir del algoritmo de Grover es que la mejora de velocidad cuadrática lograda es demasiado modesta para superar la gran sobrecarga de las computadoras cuánticas de corto plazo. [ 15 ] Sin embargo, las generaciones posteriores de computadoras cuánticas tolerantes a fallos con un mejor rendimiento de hardware podrían lograr estas mejoras de velocidad para casos prácticos de datos.

Descripción del problema

Como entrada para el algoritmo de Grover, supongamos que tenemos una funciónF:{0,1,…,norte−1}→{0,1}{\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}. En la analogía de la "base de datos no estructurada", el dominio representa los índices de una base de datos, yF(incógnita)=1{\displaystyle f(x)=1}si los datos queincógnita{\displaystyle x}apunta a satisfacer el criterio de búsqueda. Además, asumimos que solo un índice satisfaceF(incógnita)=1{\displaystyle f(x)=1}y a esto lo llamamos índiceω{\displaystyle \omega }Nuestro objetivo es identificarω{\displaystyle \omega }.

Podemos accederF{\displaystyle f}con una subrutina (a veces llamada oráculo ) en forma de operador unitarioUω{\displaystyle U_{\omega }}que actúa de la siguiente manera:

{Uω|incógnita⟩=−|incógnita⟩para incógnita=ω, eso es, F(incógnita)=1,Uω|incógnita⟩=|incógnita⟩para incógnita≠ω, eso es, F(incógnita)=0.{\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{para }}x=\omega {\text{, es decir, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{para }}x\neq \omega {\text{, es decir, }}f(x)=0.\end{cases}}}

Esto utiliza elnorte{\displaystyle N}espacio de estados dimensionalH{\displaystyle {\mathcal {H}}}, que es suministrado por un registro connorte=⌈registro2⁡norte⌉{\displaystyle n=\lceil \log _{2}N\rceil }cúbits . Esto se suele escribir como

Uω|incógnita⟩=(−1)F(incógnita)|incógnita⟩.{\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}

Resultados del algoritmo de Groverω{\displaystyle \omega }con probabilidad al menos1/2{\displaystyle 1/2}usandoO(norte){\displaystyle O({\sqrt {N}})}aplicaciones deUω{\displaystyle U_{\omega }}Esta probabilidad puede hacerse arbitrariamente grande ejecutando el algoritmo de Grover varias veces. Si se ejecuta el algoritmo de Grover hastaω{\displaystyle \omega }Se encuentra, el número esperado de solicitudes aún esO(norte){\displaystyle O({\sqrt {N}})}, ya que, en promedio, solo se ejecutará dos veces.

Definición alternativa de oráculo

Esta sección compara el oráculo anteriorUω{\displaystyle U_{\omega }}con un oráculoUF{\displaystyle U_{f}}.

Uω{\displaystyle U_{\omega }}es diferente del oráculo cuántico estándar para una funciónF{\displaystyle f}. Este oráculo estándar, denominado aquí comoUF{\displaystyle U_{f}}, utiliza un sistema de cúbits auxiliar . La operación representa entonces una inversión ( puerta NOT ) en el sistema principal condicionada por el valor de f ( x ) del sistema auxiliar:

{UF|incógnita⟩|y⟩=|incógnita⟩|¬y⟩para incógnita=ω, eso es, F(incógnita)=1,UF|incógnita⟩|y⟩=|incógnita⟩|y⟩para incógnita≠ω, eso es, F(incógnita)=0,{\displaystyle {\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{para }}x=\omega {\text{, es decir, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{para }}x\neq \omega {\text{, es decir, }}f(x)=0,\end{cases}}}

o brevemente,

UF|incógnita⟩|y⟩=|incógnita⟩|y⊕F(incógnita)⟩.{\displaystyle U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}

Estos oráculos se realizan típicamente mediante la no computación .

Si se nos daUF{\displaystyle U_{f}}como nuestro oráculo, entonces también podemos implementarUω{\displaystyle U_{\omega }}, desdeUω{\displaystyle U_{\omega }}esUF{\displaystyle U_{f}}cuando el cúbit auxiliar está en el estado|−⟩=12(|0⟩−|1⟩)=H|1⟩{\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }:

UF(|incógnita⟩⊗|−⟩)=12(UF|incógnita⟩|0⟩−UF|incógnita⟩|1⟩)=12(|incógnita⟩|0⊕F(incógnita)⟩−|incógnita⟩|1⊕F(incógnita)⟩)={12(−|incógnita⟩|0⟩+|incógnita⟩|1⟩)si F(incógnita)=1,12(|incógnita⟩|0⟩−|incógnita⟩|1⟩)si F(incógnita)=0=(Uω|incógnita⟩)⊗|−⟩{\displaystyle {\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|x\rangle |1\rangle \right)\\&={\frac {1}{\sqrt {2}}}\left(|x\rangle |0\oplus f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)\\&={\begin{cases}{\frac {1}{\sqrt {2}}}\left(-|x\rangle |0\rangle +|x\rangle |1\rangle \right)&{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)&{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}}

Por lo tanto, el algoritmo de Grover se puede ejecutar independientemente del oráculo que se proporcione. [ 3 ] SiUF{\displaystyle U_{f}}Si se da, entonces debemos mantener un cúbit adicional en el estado.|−⟩{\displaystyle |-\rangle }y aplicarUF{\displaystyle U_{f}}en lugar deUω{\displaystyle U_{\omega }}.

Algoritmo

Representación de circuitos cuánticos del algoritmo de Grover

Los pasos del algoritmo de Grover se describen a continuación:

  1. Inicializa el sistema a la superposición uniforme sobre todos los estados.|s⟩=1norte∑incógnita=0norte−1|incógnita⟩.{\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}
  2. Realice la siguiente "iteración de Grover".r(norte){\displaystyle r(N)}veces:
    1. Aplicar el operadorUω{\displaystyle U_{\omega }}
    2. Aplicar el operador de difusión de GroverUs=2|s⟩⟨s|−I{\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}
  3. Medir el estado cuántico resultante en la base computacional.

Para el valor de elegido correctamenter{\displaystyle r}, el resultado será|ω⟩{\displaystyle |\omega \rangle }con una probabilidad que se aproxima a 1 para N ≫ 1. El análisis muestra que este valor eventual parar(norte){\displaystyle r(N)}Satisfacer(norte)≤⌈π4norte⌉{\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}.

La implementación de los pasos de este algoritmo se puede realizar utilizando un número de compuertas lineal en el número de cúbits. [ 3 ] Por lo tanto, la complejidad de compuertas de este algoritmo esO(registro⁡(norte)r(norte)){\displaystyle O(\log(N)r(N))}, oO(registro⁡(norte)){\displaystyle O(\log(N))}por iteración.

Demostración geométrica

Imagen que muestra la interpretación geométrica de la primera iteración del algoritmo de Grover. El vector de estado|s⟩{\displaystyle |s\rangle }se gira hacia el vector objetivo|ω⟩{\displaystyle |\omega \rangle }como se muestra.

Existe una interpretación geométrica del algoritmo de Grover, que se deriva de la observación de que el estado cuántico del algoritmo de Grover permanece en un subespacio bidimensional después de cada paso. Consideremos el plano generado por|s⟩{\displaystyle |s\rangle }y|ω⟩{\displaystyle |\omega \rangle }; equivalentemente, el plano abarcado por|ω⟩{\displaystyle |\omega \rangle }y el ket perpendicular|s′⟩=1norte−1∑incógnita≠ω|incógnita⟩{\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }.

El algoritmo de Grover comienza con el ket inicial|s⟩{\displaystyle |s\rangle }, que se encuentra en el subespacio. El operadorUω{\displaystyle U_{\omega }}es una reflexión en el hiperplano ortogonal a|ω⟩{\displaystyle |\omega \rangle }para vectores en el plano generado por|s′⟩{\displaystyle |s'\rangle }y|ω⟩{\displaystyle |\omega \rangle }, es decir, actúa como un reflejo a través de|s′⟩{\displaystyle |s'\rangle }Esto se puede ver escribiendoUω{\displaystyle U_{\omega }}en forma de reflexión de un miembro de la familia Householder :

Uω=I−2|ω⟩⟨ω|.{\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}

El operadorUs=2|s⟩⟨s|−I{\displaystyle U_{s}=2|s\rangle \langle s|-I}es un reflejo a través de|s⟩{\displaystyle |s\rangle }Ambos operadoresUs{\displaystyle U_{s}}yUω{\displaystyle U_{\omega }}tomar estados en el plano abarcado por|s′⟩{\displaystyle |s'\rangle }y|ω⟩{\displaystyle |\omega \rangle }a estados en el plano. Por lo tanto, el algoritmo de Grover permanece en este plano durante todo el proceso.

Es sencillo comprobar que el operadorUsUω{\displaystyle U_{s}U_{\omega }}En cada paso de iteración de Grover se rota el vector de estado en un ángulo deθ=2arcoseno⁡1norte{\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}. Por lo tanto, con suficientes iteraciones, se puede rotar desde el estado inicial.|s⟩{\displaystyle |s\rangle }al estado de salida deseado|ω⟩{\displaystyle |\omega \rangle }. El ket inicial está cerca del estado ortogonal a|ω⟩{\displaystyle |\omega \rangle }:

⟨s′|s⟩=norte−1norte.{\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}

En términos geométricos, el ánguloθ/2{\displaystyle \theta /2}entre|s⟩{\displaystyle |s\rangle }y|s′⟩{\displaystyle |s'\rangle }es dado por

pecado⁡θ2=1norte.{\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}

Necesitamos detenernos cuando el vector de estado pase cerca de|ω⟩{\displaystyle |\omega \rangle }; después de esto, las iteraciones subsiguientes rotan el vector de estado alejándolo de|ω⟩{\displaystyle |\omega \rangle }, reduciendo la probabilidad de obtener la respuesta correcta. La probabilidad exacta de medir la respuesta correcta es

pecado2⁡((r+12)θ),{\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),}

donde r es el número (entero) de iteraciones de Grover. Por lo tanto, el tiempo más temprano en el que obtenemos una medición casi óptima esr≈πnorte/4{\displaystyle r\approx \pi {\sqrt {N}}/4}.

Demostración algebraica

Para completar el análisis algebraico, necesitamos averiguar qué sucede cuando aplicamos repetidamenteUsUω{\displaystyle U_{s}U_{\omega }}. Una forma natural de hacerlo es mediante el análisis de valores propios de una matriz. Nótese que durante todo el cálculo, el estado del algoritmo es una combinación lineal des{\displaystyle s}yω{\displaystyle \omega }Podemos escribir la acción deUs{\displaystyle U_{s}}yUω{\displaystyle U_{\omega }}en el espacio abarcado por{|s⟩,|ω⟩}{\displaystyle \{|s\rangle ,|\omega \rangle \}}como:

Us:a|ω⟩+b|s⟩↦[|ω⟩|s⟩][−102/norte1][ab].Uω:a|ω⟩+b|s⟩↦[|ω⟩|s⟩][−1−2/norte01][ab].{\displaystyle {\begin{aligned}U_{s}:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\\U_{\omega }:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\end{aligned}}}

Entonces, en base{|ω⟩,|s⟩}{\displaystyle \{|\omega \rangle ,|s\rangle \}}(que no es ni ortogonal ni una base de todo el espacio) la acciónUsUω{\displaystyle U_{s}U_{\omega }}de aplicarUω{\displaystyle U_{\omega }}seguido deUs{\displaystyle U_{s}}viene dada por la matriz

UsUω=[−102/norte1][−1−2/norte01]=[12/norte−2/norte1−4/norte].{\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.}

Esta matriz tiene una forma de Jordan muy conveniente . Si definimost=arcoseno⁡(1/norte){\displaystyle t=\arcsin(1/{\sqrt {N}})}, es

UsUω=METRO[mi2it00mi−2it]METRO−1{\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}

dóndeMETRO=[−iimiitmi−it].{\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}

De ello se deduce que la r -ésima potencia de la matriz (correspondiente a r iteraciones) es

(UsUω)r=METRO[mi2rit00mi−2rit]METRO−1.{\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}

Utilizando esta forma, podemos usar identidades trigonométricas para calcular la probabilidad de observar ω después de r iteraciones mencionadas en la sección anterior,

|[⟨ω|ω⟩⟨ω|s⟩](UsUω)r[01]|2=pecado2⁡((2r+1)t).{\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).}

Alternativamente, uno podría imaginar razonablemente que un momento casi óptimo para distinguir sería cuando los ángulos 2 rt y −2 rt estén lo más separados posible, lo que corresponde a2rt≈π/2{\displaystyle 2rt\approx \pi /2}, or=π/4t=π/4arcoseno⁡(1/norte)≈πnorte/4{\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}Entonces el sistema está en estado

[|ω⟩|s⟩](UsUω)r[01]≈[|ω⟩|s⟩]METRO[i00−i]METRO−1[01]=|ω⟩1porque⁡(t)−|s⟩pecado⁡(t)porque⁡(t).{\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.}

Un cálculo sencillo muestra ahora que la observación arroja la respuesta correcta ω con error.O(1norte){\displaystyle O\left({\frac {1}{N}}\right)}.

Extensiones y variantes

Múltiples entradas coincidentes

Si, en lugar de 1 entrada coincidente, hay k entradas coincidentes, el mismo algoritmo funciona, pero el número de iteraciones debe serπ4nortek{\textstyle {\frac {\pi }{4}}{\sqrt {\frac {N}{k}}}}en lugar deπ4norte{\textstyle {\frac {\pi }{4}}{\sqrt {N}}}.

Hay varias maneras de manejar el caso si k es desconocido. [ 16 ] Una solución simple funciona de manera óptima hasta un factor constante: ejecutar el algoritmo de Grover repetidamente para valores cada vez más pequeños de k , por ejemplo, tomando k = N , N /2, N /4, ..., y así sucesivamente, tomandok=norte/2t{\displaystyle k=N/2^{t}}para la iteración t hasta que se encuentre una entrada coincidente.

Con una probabilidad suficientemente alta, se encontrará una entrada marcada mediante iteración.t=registro2⁡(norte/k)+do{\displaystyle t=\log _{2}(N/k)+c}para alguna constante c . Por lo tanto, el número total de iteraciones tomadas es como máximo

π4(1+2+4+⋯+nortek2do)=O(norte/k).{\displaystyle {\frac {\pi }{4}}{\Big (}1+{\sqrt {2}}+{\sqrt {4}}+\cdots +{\sqrt {\frac {N}{k2^{c}}}}{\Big )}=O{\big (}{\sqrt {N/k}}{\big )}.}

Otro enfoque, si k es desconocido, es derivarlo mediante el algoritmo de conteo cuántico previo.

Sik=norte/2{\displaystyle k=N/2}(o el tradicional marcado como estado Algoritmo de Grover si se ejecuta connorte=2{\displaystyle N=2}), el algoritmo no proporcionará ninguna amplificación. Sik>norte/2{\displaystyle k>N/2}, aumentar k comenzará a aumentar el número de iteraciones necesarias para obtener una solución. [ 17 ] Por otro lado, sik≥norte/2{\displaystyle k\geq N/2}, una ejecución clásica del oráculo de verificación sobre una única elección aleatoria de entrada dará, con mucha probabilidad, una solución correcta.

Se utiliza una versión de este algoritmo para resolver el problema de colisión . [ 18 ] [ 19 ]

Grover y Radhakrishnan describieron en 2004 una modificación del algoritmo de Grover llamada búsqueda parcial cuántica. [ 20 ] En la búsqueda parcial, no interesa encontrar la dirección exacta del elemento objetivo, sino solo los primeros dígitos de la dirección. De forma equivalente, podemos pensar en "fragmentar" el espacio de búsqueda en bloques y luego preguntar "¿en qué bloque está el elemento objetivo?". En muchas aplicaciones, dicha búsqueda proporciona suficiente información si la dirección objetivo contiene la información deseada. Por ejemplo, para usar el ejemplo dado por LK Grover, si se tiene una lista de estudiantes organizados por clasificación de clase, es posible que solo nos interese saber si un estudiante está en el percentil inferior del 25%, 25-50%, 50-75% o 75-100%.

Para describir la búsqueda parcial, consideramos una base de datos separada enK{\displaystyle K}bloques, cada uno de tamañob=norte/K{\displaystyle b=N/K}El problema de búsqueda parcial es más sencillo. Consideremos el enfoque que adoptaríamos clásicamente: elegimos un bloque al azar y luego realizamos una búsqueda normal a través del resto de los bloques (en el lenguaje de la teoría de conjuntos, el complemento). Si no encontramos el objetivo, sabemos que está en el bloque que no buscamos. El número promedio de iteraciones disminuye denorte/2{\displaystyle N/2}a(norte−b)/2{\displaystyle (N-b)/2}.

El algoritmo de Grover requiereπ4norte{\textstyle {\frac {\pi }{4}}{\sqrt {N}}}iteraciones. La búsqueda parcial será más rápida por un factor numérico que depende del número de bloques.K{\displaystyle K}La búsqueda parcial utilizanorte1{\displaystyle n_{1}}iteraciones globales ynorte2{\displaystyle n_{2}}iteraciones locales. El operador global de Grover está designadoGRAMO1{\displaystyle G_{1}}y el operador local de Grover es designadoGRAMO2{\displaystyle G_{2}}.

El operador global de Grover actúa sobre los bloques. Básicamente, se define de la siguiente manera:

  1. Llevar a caboj1{\displaystyle j_{1}}Iteraciones estándar de Grover en toda la base de datos.
  2. Llevar a caboj2{\displaystyle j_{2}}Iteraciones locales de Grover. Una iteración local de Grover es la suma directa de las iteraciones de Grover realizadas sobre cada bloque.
  3. Realiza una iteración estándar de Grover.

Los valores óptimos dej1{\displaystyle j_{1}}yj2{\displaystyle j_{2}}Estos temas se discuten en el artículo de Grover y Radhakrishnan. También cabe preguntarse qué sucede si se aplican búsquedas parciales sucesivas en diferentes niveles de "resolución". Esta idea fue estudiada en detalle por Vladimir Korepin y Xu, quienes la denominaron búsqueda cuántica binaria. Demostraron que, de hecho, no es más rápida que realizar una única búsqueda parcial.

Optimalidad

El algoritmo de Grover es óptimo salvo factores subconstantes. Es decir, cualquier algoritmo que acceda a la base de datos únicamente mediante el operador U ω debe aplicar U ω al menos una1−o(1){\displaystyle 1-o(1)}fracciona tantas veces como el algoritmo de Grover. [ 21 ] La extensión del algoritmo de Grover a k entradas coincidentes, π ( N / k ) 1/2 /4, también es óptima. [ 18 ] Este resultado es importante para comprender los límites de la computación cuántica.

Si el problema de búsqueda de Grover se pudiera resolver con log c N aplicaciones de U ω , eso implicaría que NP está contenido en BQP , al transformar problemas de NP en problemas de búsqueda de tipo Grover. La optimalidad del algoritmo de Grover sugiere que las computadoras cuánticas no pueden resolver problemas NP-completos en tiempo polinomial, y por lo tanto, NP no está contenido en BQP.

Se ha demostrado que una clase de computadoras cuánticas de variables ocultas no locales podría implementar una búsqueda de unanorte{\displaystyle N}-base de datos de elementos en como máximoO(norte3){\displaystyle O({\sqrt[{3}]{N}})}pasos. Esto es más rápido que elO(norte){\displaystyle O({\sqrt {N}})}pasos dados por el algoritmo de Grover. [ 22 ]

Véase también

Notas

  1. 1 2 Grover, Lov K. (1996-07-01). "Un algoritmo mecánico cuántico rápido para la búsqueda en bases de datos" . Actas del vigésimo octavo simposio anual de la ACM sobre Teoría de la Computación - STOC '96 . Filadelfia, Pensilvania, EE. UU.: Association for Computing Machinery. págs. 212–219 . arXiv : quant-ph/9605043 . Bibcode : 1996quant.ph..5043G . doi : 10.1145/237814.237866 . ISBN  978-0-89791-785-8. S2CID 207198067 . 
  2. ↑ Bennett, CH; Bernstein, E.; Brassard, G.; Vazirani, U. (1997). "Las fortalezas y debilidades de la computación cuántica" . SIAM Journal on Computing . 26 (5): 1510– 1523. arXiv : quant-ph/9701001 . doi : 10.1137/s0097539796300933 . S2CID 13403194 . 
  3. 1 2 3 4 Nielsen, Michael A.; Chuang, Isaac L. (2010). Computación cuántica e información cuántica . Cambridge: Cambridge University Press. págs. 276–305 . ISBN  978-1-107-00217-3OCLC 665137861​​ 
  4. ↑ Bernstein, Daniel J. (2010). "Grover vs. McEliece" (PDF) . En Sendrier, Nicolas (ed.). Criptografía postcuántica, Tercer taller internacional, PQCrypto 2010, Darmstadt, Alemania, 25-28 de mayo de 2010. Actas . Lecture Notes in Computer Science. Vol. 6061. Springer. pp. 73–80 . doi : 10.1007/978-3-642-12929-2_6 . ISBN   978-3-642-12928-5.
  5. ↑ Grover, Lov K. (1998). «Un marco para algoritmos mecánicos cuánticos rápidos». En Vitter, Jeffrey Scott (ed.). Actas del Trigésimo Simposio Anual de la ACM sobre la Teoría de la Computación, Dallas, Texas, EE. UU., 23-26 de mayo de 1998. Association for Computing Machinery. págs. 53-62 . arXiv : quant-ph/9711043 . doi : 10.1145/276698.276712 . ISBN  0-89791-962-9.
  6. 1 2 Ambainis, A. (2004-06-01). "Algoritmos de búsqueda cuántica". ACM SIGACT News . 35 (2): 22– 35. arXiv : quant-ph/0504012 . doi : 10.1145/992287.992296 . ISSN 0163-5700 . S2CID 11326499 .  
  7. ↑ Jordan, Stephen. "Quantum Algorithm Zoo" . quantumalgorithmzoo.org . Consultado el 21 de abril de 2021 .
  8. ↑ Cerf, Nicolas J.; Grover, Lov K.; Williams, Colin P. (2000-05-01). "Búsqueda cuántica anidada y problemas NP-difíciles". Applicable Algebra in Engineering, Communication and Computing . 10 (4): 311– 338. doi : 10.1007/s002000050134 . ISSN 1432-0622 . S2CID 311132 .  
  9. ↑ Ambainis, Andris (2007-01-01). "Algoritmo de paseo cuántico para la distinción de elementos" . SIAM Journal on Computing . 37 (1): 210– 239. arXiv : quant-ph/0311001 . doi : 10.1137/S0097539705447311 . ISSN 0097-5397 . S2CID 6581885 .  
  10. ↑ Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998). "Criptoanálisis cuántico de funciones hash y libres de garras". En Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.). LATIN '98: Informática teórica, Tercer Simposio Latinoamericano, Campinas, Brasil, 20-24 de abril de 1998, Actas . Lecture Notes in Computer Science. Vol. 1380. Springer. pp. 163–169 . arXiv : quant-ph/9705002 . doi : 10.1007/BFb0054319 . ISBN   978-3-540-64275-6.
  11. ↑ Criptografía poscuántica . Daniel J. Bernstein, Johannes Buchmann, Erik, Dipl.-Math Dahmén. Berlín: Springer. 2009.ISBN​ 978-3-540-88702-7OCLC 318545517​​ {{cite book}}: CS1 mantenimiento: otros ( enlace )
  12. ↑ Bernstein, Daniel J. (21 de abril de 2021). "Análisis de costos de colisiones de hash: ¿Dejarán obsoletos los ordenadores cuánticos a SHARCS?" (PDF) . Actas de la conferencia sobre hardware de propósito especial para atacar sistemas criptográficos (SHARCS '09) . 09 : 105–117 .
  13. ↑ Viamontes GF; Markov IL; Hayes JP (2005), "¿Es práctica la búsqueda cuántica?" (PDF) , Computing in Science and Engineering , 7 (3): 62–70 , arXiv : quant-ph/0405001 , Bibcode : 2005CSE.....7c..62V , doi : 10.1109/mcse.2005.53 , S2CID 8929938 
  14. ↑ Sinitsyn NA; Yan B. (2023). "Oráculo de Grover protegido topológicamente para el problema de partición". Physical Review A . 108 (2) 022412. arXiv : 2304.10488 . Bibcode : 2023PhRvA.108b2412S . doi : 10.1103/PhysRevA.108.022412 . S2CID 258236417 . 
  15. ↑ Babbush, Ryan; McClean, Jarrod R.; Newman, Michael; Gidney, Craig; Boixo, Sergio; Neven, Hartmut (2021-03-29). "Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage" . PRX Quantum . 2 (1) 010103. arXiv : 2011.04149 . doi : 10.1103/PRXQuantum.2.010103 .
  16. ↑ Aaronson, Scott (19 de abril de 2021). "Introducción a las notas de clase de la ciencia de la información cuántica" (PDF) .
  17. ^ Nielsen-Chuang
  18. ^ Boyer , Michel; Brassard, Gilles; Hoyer, Peter; Tapp, Alain (1998), "Límites estrictos en la búsqueda cuántica", Fortschritte der Physik , vol. 46, págs. 493–506 , arXiv : quant-ph/9605034 , Bibcode : 1998ForPh..46..493B , doi : 10.1002/3527603093.ch10 , ISBN   978-3-527-60309-1
  19. ↑ Ambainis, Andris (2004), "Algoritmos de búsqueda cuántica", SIGACT News , 35 (2): 22–35 , arXiv : quant-ph/0504012 , Bibcode : 2005quant.ph..4012A , doi : 10.1145/992287.992296 , S2CID 11326499 
  20. ↑ Grover, LK; Radhakrishnan, J. (2005-02-07). "¿Es más fácil la búsqueda cuántica parcial en una base de datos?". arXiv : quant-ph/0407122v4 .
  21. ↑ Zalka, Christof (1999-10-01). "El algoritmo de búsqueda cuántica de Grover es óptimo" . Physical Review A. 60 ( 4): 2746– 2751. arXiv : quant-ph/9711070 . Bibcode : 1999PhRvA..60.2746Z . doi : 10.1103/PhysRevA.60.2746 . S2CID 1542077 . 
  22. ↑ Aaronson, Scott. "Computación cuántica y variables ocultas" (PDF) .

Referencias

  • Grover LK: Un algoritmo mecánico cuántico rápido para la búsqueda en bases de datos , Actas del 28.º Simposio Anual de la ACM sobre la Teoría de la Computación (mayo de 1996), pág.  212.
  • Grover LK: De la ecuación de Schrödinger al algoritmo de búsqueda cuántica , American Journal of Physics, 69(7): 769–777, 2001. Revisión pedagógica del algoritmo y su historia.
  • Grover LK: COMPUTACIÓN CUÁNTICA: Cómo la extraña lógica del mundo subatómico podría permitir que las máquinas calculen millones de veces más rápido que en la actualidad. The Sciences , julio/agosto de 1999, págs.  24-30.
  • Nielsen, MA y Chuang, IL Computación cuántica e información cuántica . Cambridge University Press, 2000. Capítulo 6.
  • ¿Qué es una guía telefónica cuántica?, Lov Grover, Lucent Technologies
  • Davy Wybiral. "Simulador de circuitos cuánticos" . Archivado del original el 16 de enero de 2017. Consultado el 13 de enero de 2017 .
  • Craig Gidney (5 de marzo de 2013). "Algoritmo de búsqueda cuántica de Grover" . Archivado del original el 17 de noviembre de 2020. Consultado el 8 de marzo de 2013 .
  • François Schwarzentruber (18 de mayo de 2013). "El algoritmo de Grover" .
  • Alexander Prokopenya. "Circuito cuántico que implementa el algoritmo de búsqueda de Grover" . Wolfram Alpha .
  • "Computación cuántica, teoría de" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
  • Roberto Maestre (11 de mayo de 2018). "Algoritmo de Grover implementado en R y C" . GitHub .
  • Bernhard Ömer. "QCL - Un lenguaje de programación para computadoras cuánticas" . Consultado el 30 de abril de 2022. Implementado en /qcl-0.6.4/lib/grover.qcl