algoritmo de Grover

Algoritmo de búsqueda cuántica

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 solo evaluaciones de la función, donde es el tamaño del dominio de la función . Fue ideado por Lov Grover en 1996. ^[1] ${\displaystyle O({\sqrt {N}})}$ ${\displaystyle N}$

El problema análogo en la computación clásica no se puede resolver en menos de evaluaciones (porque, en promedio, uno tiene que verificar la mitad del dominio para obtener un 50% de posibilidades de encontrar la entrada correcta). Charles H. Bennett , Ethan Bernstein, Gilles Brassard y Umesh Vazirani demostraron que cualquier solución cuántica al problema necesita evaluar los tiempos de la función, 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 búsqueda no estructurada, esto sugiere que el algoritmo de Grover por sí solo no proporcionará soluciones en tiempo polinomial para NP-completos. problemas completos (ya que la raíz cuadrada de una función exponencial es una función exponencial, no polinómica). ^[3] ${\displaystyle O(N)}$ ${\displaystyle \Omega ({\sqrt {N}})}$

A diferencia de otros algoritmos cuánticos, que pueden proporcionar una aceleración exponencial con respecto a sus homólogos clásicos, el algoritmo de Grover proporciona sólo una aceleración cuadrática. Sin embargo, incluso la aceleración cuadrática es considerable cuando es grande, y el algoritmo de Grover se puede aplicar para acelerar clases amplias de algoritmos. ^[3] El algoritmo de Grover podría forzar 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 represente un riesgo significativamente mayor para el cifrado que los algoritmos clásicos existentes. ^[4] ${\displaystyle N}$

Aplicaciones y limitaciones

El algoritmo de Grover, junto con variantes como la amplificación de amplitud , se puede utilizar para acelerar una amplia gama de algoritmos. ^{[5] [6] [7]} En particular, el algoritmo de Grover puede acelerar los algoritmos para problemas NP-completos que contienen búsqueda exhaustiva como una subrutina. ^[6] El mejor algoritmo actual 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, ya 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 3SAT.

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

Criptografía

El algoritmo de Grover esencialmente resuelve el problema de la inversión de funciones . En términos generales, si tenemos una función que se puede evaluar en una computadora cuántica, el algoritmo de Grover nos permite calcularla cuando se da . En consecuencia, el algoritmo de Grover proporciona amplias aceleraciones asintóticas a muchos tipos de ataques de fuerza bruta en criptografía de clave simétrica , incluidos los ataques de colisión y los ataques de preimagen . ^[11] Sin embargo, este puede no ser necesariamente el algoritmo más eficiente ya que, por ejemplo, el algoritmo rho paralelo es capaz de encontrar una colisión en SHA2 de manera más eficiente que el algoritmo de Grover. ^[12] ${\displaystyle y=f(x)}$ ${\displaystyle x}$ ${\displaystyle y}$

Limitaciones

El artículo original de Grover describía el algoritmo como un algoritmo de búsqueda en una base de datos, y esta descripción sigue siendo común. La base de datos en esta analogía es una tabla de todas las salidas de la función, indexadas por la entrada correspondiente. Sin embargo, esta base de datos no está representada explícitamente. En cambio, se invoca un oráculo para evaluar un elemento por su índice. Leer una base de datos completa elemento por elemento y convertirla en dicha representación puede llevar mucho más tiempo que la búsqueda de Grover. Para tener en cuenta tales efectos, se puede considerar que el algoritmo de Grover resuelve una ecuación o satisface 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 normalmente impide las optimizaciones algorítmicas, mientras que los algoritmos de búsqueda convencionales a menudo se basan en dichas optimizaciones y evitan la búsqueda exhaustiva. ^[13] Afortunadamente, la implementación rápida del oráculo de Grover es posible para muchos problemas de optimización y satisfacción de restricciones. ^[14]

La principal barrera para instanciar una aceleración del algoritmo de Grover es que la aceleración cuadrática lograda es demasiado modesta para superar la gran sobrecarga de las computadoras cuánticas a corto plazo. ^[15] Sin embargo, las generaciones posteriores de computadoras cuánticas tolerantes a fallas con mejor rendimiento de hardware pueden lograr estas aceleraciones para casos prácticos de datos.

Descripción del problema

Como entrada para el algoritmo de Grover, supongamos que tenemos una función . En la analogía de la "base de datos no estructurada", el dominio representa índices de una base de datos, y f ( x ) = 1 si y sólo si los datos a los que apunta x satisfacen el criterio de búsqueda. Además, asumimos que sólo un índice satisface f ( x ) = 1 , y llamamos a este índice ω . Nuestro objetivo es identificar ω . ${\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}$

Podemos acceder a f con una subrutina (a veces llamada oráculo ) en forma de operador unitario U _ω que actúa de la siguiente manera:

${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}}$

Esto utiliza el espacio de estados de dimensiones , que es proporcionado por un registro con qubits . Esto a menudo se escribe como ${\displaystyle N}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle n=\lceil \log _{2}N\rceil }$

${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}$

El algoritmo de Grover genera ω con una probabilidad de al menos 1/2 utilizando aplicaciones de U _ω . Esta probabilidad puede hacerse arbitrariamente grande ejecutando el algoritmo de Grover varias veces. Si se ejecuta el algoritmo de Grover hasta encontrar ω , el número esperado de aplicaciones sigue siendo , ya que solo se ejecutará dos veces en promedio. ${\displaystyle O({\sqrt {N}})}$ ${\displaystyle O({\sqrt {N}})}$

Definición alternativa de oráculo

Esta sección compara el oráculo anterior con un oráculo . ${\displaystyle U_{\omega }}$ ${\displaystyle U_{f}}$

U _ω es diferente del oráculo cuántico estándar para una función f . Este oráculo estándar, denominado aquí Uf _, utiliza un sistema de qubit auxiliar . La operación entonces representa una inversión ( NO puerta ) en el sistema principal condicionada por el valor de f ( x ) del sistema auxiliar:

${\displaystyle {\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0,\end{cases}}}$

o brevemente,

${\displaystyle U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}$

Estos oráculos normalmente se realizan mediante la no computación .

Si nos dan U _f como nuestro oráculo, entonces también podemos implementar U _ω , ya que U _ω es U _f cuando el qubit auxiliar está en el estado : ${\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }$

${\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 |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 tanto, el algoritmo de Grover se puede ejecutar independientemente del oráculo que se proporcione. ^[3] Si se da U _f , entonces debemos mantener un qubit adicional en el estado y aplicar U _f en lugar de U _ω . ${\displaystyle |-\rangle }$

Algoritmo

Representación del circuito cuántico del algoritmo de Grover.

Los pasos del algoritmo de Grover se dan de la siguiente manera:

1. Inicializar el sistema a la superposición uniforme sobre todos los estados.
   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$
2. Realice los siguientes tiempos de "iteración de Grover": ${\displaystyle r(N)}$
   1. Aplicar el operador ${\displaystyle U_{\omega }}$
   2. Aplicar el operador de difusión Grover. ${\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}$
3. Mida el estado cuántico resultante en la base computacional.

Para el valor elegido correctamente de , la salida tendrá una probabilidad cercana a 1 para N ≫ 1. El análisis muestra que este valor eventual de satisface . ${\displaystyle r}$ ${\displaystyle |\omega \rangle }$ ${\displaystyle r(N)}$ ${\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 una cantidad de puertas lineales en la cantidad de qubits. ^[3] Por lo tanto, la complejidad de la puerta de este algoritmo es , o por iteración. ${\displaystyle O(\log(N)r(N))}$ ${\displaystyle O(\log(N))}$

Prueba geométrica de corrección.

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

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. Considere el plano atravesado por y ; de manera equivalente, el plano abarcado por y la perpendicular ket . ${\displaystyle |s\rangle }$ ${\displaystyle |\omega \rangle }$ ${\displaystyle |\omega \rangle }$ ${\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }$

El algoritmo de Grover comienza con el ket inicial , que se encuentra en el subespacio. El operador es una reflexión en el hiperplano ortogonal a para vectores en el plano abarcado por y , es decir, actúa como una reflexión a través de . Esto se puede ver escribiendo en forma de reflexión de cabeza de familia : ${\displaystyle |s\rangle }$ ${\displaystyle U_{\omega }}$ ${\displaystyle |\omega \rangle }$ ${\displaystyle |s'\rangle }$ ${\displaystyle |\omega \rangle }$ ${\displaystyle |s'\rangle }$ ${\displaystyle U_{\omega }}$

${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}$

El operador es un reflejo a través de . Ambos operadores y toman estados en el avión abarcados por y hacia estados en el avión. Por tanto, el algoritmo de Grover permanece en este plano durante todo el algoritmo. ${\displaystyle U_{s}=2|s\rangle \langle s|-I}$ ${\displaystyle |s\rangle }$ ${\displaystyle U_{s}}$ ${\displaystyle U_{\omega }}$ ${\displaystyle |s'\rangle }$ ${\displaystyle |\omega \rangle }$

Es sencillo comprobar que el operador de cada paso de iteración de Grover gira el vector de estado en un ángulo de . Entonces, con suficientes iteraciones, se puede rotar desde el estado inicial al estado de salida deseado . El ket inicial está cerca del estado ortogonal a : ${\displaystyle U_{s}U_{\omega }}$ ${\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}$ ${\displaystyle |s\rangle }$ ${\displaystyle |\omega \rangle }$ ${\displaystyle |\omega \rangle }$

${\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}$

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

${\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}$

Necesitamos detenernos cuando el vector de estado pase cerca de ; después de esto, las iteraciones posteriores alejan el vector de estado de , reduciendo la probabilidad de obtener la respuesta correcta. La probabilidad exacta de medir la respuesta correcta es ${\displaystyle |\omega \rangle }$ ${\displaystyle |\omega \rangle }$

${\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 momento más temprano en que obtenemos una medición casi óptima es . ${\displaystyle r\approx \pi {\sqrt {N}}/4}$

Prueba algebraica de corrección

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

${\displaystyle 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}}.}$

${\displaystyle 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}}.}$

Entonces, en la base (que no es ortogonal ni una base de todo el espacio) la acción de aplicar seguida de está dada por la matriz ${\displaystyle \{|\omega \rangle ,|s\rangle \}}$ ${\displaystyle U_{s}U_{\omega }}$ ${\displaystyle U_{\omega }}$ ${\displaystyle U_{s}}$

${\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 Jordan muy conveniente . Si definimos , es ${\displaystyle t=\arcsin(1/{\sqrt {N}})}$

${\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}$dónde ${\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

${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}$

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

${\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 a , o . Entonces el sistema está en estado ${\displaystyle 2rt\approx \pi /2}$ ${\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}$

${\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 breve cálculo ahora muestra que la observación produce la respuesta correcta ω con error . ${\displaystyle O\left({\frac {1}{N}}\right)}$

Extensiones y variantes

Varias entradas coincidentes

Si, en lugar de 1 entrada coincidente, hay k entradas coincidentes, funciona el mismo algoritmo, pero el número de iteraciones debe ser en lugar de ${\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}$ ${\textstyle {\frac {\pi }{4}}{N^{1/2}}.}$

Hay varias formas de manejar el caso si se desconoce k . ^[16] Una solución simple funciona de manera óptima hasta un factor constante: ejecute 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, tomando por iteración t hasta que se encuentre una entrada coincidente. ${\displaystyle k=N/2^{t}}$

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

${\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 se desconoce k es derivarlo mediante el algoritmo de conteo cuántico anterior.

Si (o el tradicional algoritmo de Grover marcado con el estado si se ejecuta con ), el algoritmo no proporcionará amplificación. Si , al aumentar k comenzará a aumentar el número de iteraciones necesarias para obtener una solución. ^[17] Por otro lado, si , una ejecución clásica del oráculo de verificación en una única elección aleatoria de entrada probablemente dará una solución correcta. ${\displaystyle k=N/2}$ ${\displaystyle N=2}$ ${\displaystyle k>N/2}$ ${\displaystyle k\geq N/2}$

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

Búsqueda parcial cuántica

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

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

El algoritmo de Grover requiere iteraciones. La búsqueda parcial será más rápida por un factor numérico que depende del número de bloques . La búsqueda parcial utiliza iteraciones globales e iteraciones locales. Se designa al operador global de Grover y al operador local de Grover . ${\textstyle {\frac {\pi }{4}}{\sqrt {N}}}$ ${\displaystyle K}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

Sobre los bloques actúa el operador global Grover. Básicamente, se da de la siguiente manera:

1. Realice iteraciones estándar de Grover en toda la base de datos. ${\displaystyle j_{1}}$
2. Realice iteraciones de Grover locales. Una iteración local de Grover es una suma directa de las iteraciones de Grover en cada bloque. ${\displaystyle j_{2}}$
3. Realice una iteración estándar de Grover.

Los valores óptimos de y se analizan en el artículo de Grover y Radhakrishnan. También cabría 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 llamaron búsqueda cuántica binaria. Demostraron que, de hecho, no es más rápido que realizar una única búsqueda parcial. ${\displaystyle j_{1}}$ ${\displaystyle j_{2}}$

Optimidad

El algoritmo de Grover es óptimo hasta factores subconstantes. Es decir, cualquier algoritmo que acceda a la base de datos únicamente utilizando el operador U _ω debe aplicar U _ω al menos una fracción de veces más que 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. ${\displaystyle 1-o(1)}$

Si el problema de búsqueda de Grover pudiera resolverse con aplicaciones log ^c N de U _ω , eso implicaría que NP está contenido en BQP , transformando problemas en NP en problemas de búsqueda de tipo Grover. La optimización del algoritmo de Grover sugiere que las computadoras cuánticas no pueden resolver problemas NP-completos en tiempo polinómico 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 en una base de datos de elementos en la mayoría de los pasos. Esto es más rápido que los pasos dados por el algoritmo de Grover. ^[22] ${\displaystyle N}$ ${\displaystyle O({\sqrt[{3}]{N}})}$ ${\displaystyle O({\sqrt {N}})}$

Ver también

• amplificación de amplitud
• Algoritmo de Brassard-Høyer-Tapp (para resolver el problema de colisión )
• Algoritmo de Shor (para factorización)
• Búsqueda de paseo cuántico

Notas

1. Grover, Lov K. (1 de julio de 1996). "Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos". Actas del vigésimo octavo simposio anual de ACM sobre teoría de la informática - STOC '96 . Filadelfia, Pensilvania, EE.UU.: Asociación de Maquinaria de Computación. págs. 212-219. arXiv : quant-ph/9605043 . Código Bib : 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". Revista SIAM de Computación . 26 (5): 1510-1523. arXiv : quant-ph/9701001 . doi :10.1137/s0097539796300933. S2CID  13403194.
3. Nielsen, Michael A. (2010). Computación cuántica e información cuántica. Isaac L. Chuang. Cambridge: Prensa de la Universidad de Cambridge. págs. 276–305. ISBN 978-1-107-00217-3. OCLC  665137861.
4. Bernstein, Daniel J. (2010). "Grover contra McEliece" (PDF) . En Sendrier, Nicolás (ed.). Criptografía poscuántica, tercer taller internacional, PQCrypto 2010, Darmstadt, Alemania, 25 al 28 de mayo de 2010. Actas . Apuntes de conferencias sobre informática. vol. 6061. Saltador. págs. 73–80. doi :10.1007/978-3-642-12929-2_6.
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 teoría de la computación, Dallas, Texas, EE. UU., 23 al 26 de mayo de 1998 . Asociación para Maquinaria de Computación. págs. 53–62. arXiv : quant-ph/9711043 . doi :10.1145/276698.276712.
6. Ambainis, A. (1 de junio de 2004). "Algoritmos de búsqueda cuántica". Noticias ACM SIGACT . 35 (2): 22–35. arXiv : quant-ph/0504012 . doi :10.1145/992287.992296. ISSN  0163-5700. S2CID  11326499.
7. Jordania, Stephen. "Zoológico de algoritmos cuánticos". quantumalgorithmzoo.org . Consultado el 21 de abril de 2021 .
8. Cerf, Nicolás J.; Grover, Lov K.; Williams, Colin P. (1 de mayo de 2000). "Búsqueda cuántica anidada y problemas NP-Hard". Álgebra Aplicable en Ingeniería, Comunicaciones y Computación . 10 (4): 311–338. doi :10.1007/s002000050134. ISSN  1432-0622. S2CID  311132.
9. Ambainis, Andris (1 de enero de 2007). "Algoritmo de caminata cuántica para la distinción de elementos". Revista SIAM de Computación . 37 (1): 210–239. arXiv : quant-ph/0311001 . doi :10.1137/S0097539705447311. ISSN  0097-5397. S2CID  6581885.
10. Brassard, Gilles; Hoyer, Peter; Tapp, Alain (1998). "Criptoanálisis cuántico de funciones Hash y Claw-Free". 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 . Apuntes de conferencias sobre informática. vol. 1380. Saltador. págs. 163-169. arXiv : quant-ph/9705002 . doi :10.1007/BFb0054319.
11. Criptografía poscuántica. Daniel J. Bernstein, Johannes Buchmann, Erik, Dipl.-Math Dahmén. Berlín: Springer. 2009.ISBN​ 978-3-540-88702-7. OCLC  318545517.{{cite book}}: CS1 maint: others (link)
12. Bernstein, Daniel J. (21 de abril de 2021). "Análisis de costos de las colisiones de hash: ¿las computadoras cuánticas harán que SHARCS quede obsoleto?" (PDF) . Actas de conferencias 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) , Computación en ciencia e ingeniería , 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). "El oráculo de Grover topológicamente protegido para el problema de la partición". Revisión física A. 108 (2): 022412. arXiv : 2304.10488 . doi : 10.1103/PhysRevA.108.022412. S2CID  258236417.
15. Babbush, Ryan; McClean, Jarrod R.; Newman, Michael; Gidney, Craig; Boixó, Sergio; Incluso, Hartmut (29 de marzo de 2021). "Céntrese más allá de las aceleraciones cuadráticas para obtener una ventaja cuántica con corrección de errores". PRX Cuántico . 2 (1): 010103. arXiv : 2011.04149 . doi : 10.1103/PRXQuantum.2.010103 .
16. Aaronson, Scott (19 de abril de 2021). "Notas de conferencias de Introducción a las ciencias de la información cuántica" (PDF) .
17. Nielsen-Chuang
18. Michel Boyer; Gilles Brassard; Peter Hoyer; Alain Tapp (1998), "Límites estrictos en la búsqueda cuántica", Fortschr. Física. , 46 (4–5): 493–506, arXiv : quant-ph/9605034 , Bibcode :1998ForPh..46..493B, doi :10.1002/3527603093.ch10, ISBN 9783527603091
19. Andris Ambainis (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. LK Grover; J. Radhakrishnan (7 de febrero de 2005). "¿Es más fácil la búsqueda cuántica parcial de una base de datos?". arXiv : quant-ph/0407122v4 .
21. Zalka, Christof (1 de octubre de 1999). "El algoritmo de búsqueda cuántica de Grover es óptimo". Revisión física A. 60 (4): 2746–2751. arXiv : quant-ph/9711070 . Código Bib : 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, 28º Simposio anual ACM sobre teoría de la computación, (mayo de 1996) p. 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 hacer posible que las máquinas calculen millones de veces más rápido que lo que hacen hoy The Sciences , julio/agosto de 1999, págs.
• 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

enlaces externos

• Davy Wybiral. "Simulador de circuito cuántico". Archivado desde el 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".
• François Schwarzentruber (18 de mayo de 2013). "Algoritmo de Grover".
• Alejandro 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-05-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