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 de 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 computación clásica no puede resolverse en menos de evaluaciones (porque, en promedio, uno tiene que verificar la mitad del dominio para obtener una probabilidad del 50% 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 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 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 es una función exponencial, no polinomial). ^[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 contrapartes clásicas, el algoritmo de Grover proporciona solo 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 amplias clases de algoritmos. ^[3] El algoritmo de Grover podría forzar una clave criptográfica simétrica de 128 bits en aproximadamente 2 ⁶⁴ iteraciones, o una clave de 256 bits en aproximadamente 2 ¹²⁸ iteraciones. Sin embargo, puede que no sea el caso de que el algoritmo de Grover plantee un riesgo significativamente mayor para el cifrado en comparación con 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, los algoritmos para problemas NP-completos que contienen una búsqueda exhaustiva como subrutina se pueden acelerar con el algoritmo de Grover. ^[6] El mejor algoritmo teórico actual, en términos de complejidad del peor caso, para 3SAT es un ejemplo de ello. Los problemas de satisfacción de restricciones genéricas también ven 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 verifica que un conjunto de bits satisface una instancia 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 la 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 oráculo f como una base de datos y el objetivo es utilizar 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ón que se puede evaluar en una computadora cuántica, el algoritmo de Grover nos permite calcular cuando se da . En consecuencia, el algoritmo de Grover proporciona amplias aceleraciones asintóticas para muchos tipos de ataques de fuerza bruta en criptografía de clave simétrica , incluidos ataques de colisión y 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 describió el algoritmo como un algoritmo de búsqueda de base de datos, y esta descripción aún es 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 su lugar, se invoca un oráculo para evaluar un elemento por su índice. Leer una base de datos completa elemento por elemento y convertirla en una representación de este tipo puede llevar mucho más tiempo que la búsqueda de Grover. Para tener en cuenta estos efectos, el algoritmo de Grover puede verse como la solució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 generalmente evita las optimizaciones algorítmicas, mientras que los algoritmos de búsqueda convencionales a menudo se basan en tales 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 satisfacción de restricciones y optimización. ^[14]

La principal barrera para lograr una aceleración a partir 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 de corto plazo. ^[15] Sin embargo, generaciones posteriores de computadoras cuánticas tolerantes a fallas con un mejor rendimiento de hardware pueden ser capaces de lograr estas aceleraciones para instancias prácticas 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 los índices de una base de datos, y f ( x ) = 1 si y solo si los datos a los que apunta x satisfacen el criterio de búsqueda. Además, suponemos que solo 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 un 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 dimensión , que se suministra mediante un registro con qubits . Esto se suele escribir 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, denotado aquí como U _f , utiliza un sistema de cúbits auxiliares . La operación representa entonces una inversión ( puerta NOT ) 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 uncomputation .

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 lo tanto, el algoritmo de Grover se puede ejecutar independientemente del oráculo proporcionado. ^[3] Si se proporciona 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 algoritmo de Grover en circuito cuántico

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

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 las siguientes iteraciones de Grover : ${\displaystyle r(N)}$
   1. Aplicar el operador ${\displaystyle U_{\omega }}$
   2. Aplicar el operador de difusión de Grover ${\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 correctamente elegido de , la salida tendrá una probabilidad cercana a 1 para N ≫ 1. El análisis muestra que este valor eventual para 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 un número de puertas lineal en el número 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 desprende 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 y ; equivalentemente, el plano generado 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 los vectores en el plano generado por y , es decir, actúa como una reflexión a través de . Esto se puede ver escribiendo en forma de una reflexión de Householder : ${\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 una reflexión a través de . Ambos operadores y toman estados en el plano abarcado por y a estados en el plano. Por lo 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 fácil comprobar que el operador de cada paso de iteración de Grover rota el vector de estado en un ángulo de . Por lo tanto, con suficientes iteraciones, se puede rotar desde el estado inicial hasta el 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 pasa cerca de ; después de esto, las iteraciones posteriores giran el vector de estado alejándolo de , lo que reduce 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 tiempo más temprano en el 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 averiguar 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}}.}$

Así que en la base (que no es ni ortogonal ni 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}}.}$

Resulta que esta matriz tiene una forma de 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 potencia r -ésima 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, se 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 el 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 cálculo breve muestra ahora 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 k es desconocido. ^[16] Una solución simple funciona óptimamente 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 para la 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 por iteración para alguna constante c . Por lo tanto, el número total de iteraciones realizadas 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 k es desconocido es derivarlo a través del algoritmo de conteo cuántico anterior.

Si (o el algoritmo tradicional marcado como el de Grover si se ejecuta con ), el algoritmo no proporcionará ninguna amplificación. Si , el aumento de 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 en 2004 una modificación del algoritmo de Grover llamada búsqueda parcial cuántica. ^[20] En la búsqueda parcial, no nos interesa encontrar la dirección exacta del elemento de destino, sino 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, una búsqueda de este tipo proporciona suficiente información si la dirección de destino contiene la información deseada. Por ejemplo, para utilizar el ejemplo dado por LK Grover, si tenemos una lista de estudiantes organizada por rango 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 dividida en bloques, cada uno de tamaño . El problema de la 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, entonces sabemos que está en el bloque que no buscamos. El número promedio de iteraciones disminuye 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 de la cantidad de bloques . La búsqueda parcial utiliza iteraciones globales e iteraciones locales. El operador de Grover global se designa y el operador de Grover local se designa . ${\textstyle {\frac {\pi }{4}}{\sqrt {N}}}$ ${\displaystyle K}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

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

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

Los valores óptimos de y se analizan en el artículo de Grover y Radhakrishnan. También cabe preguntarse qué sucede si se aplican búsquedas parciales sucesivas a 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ápida que realizar una única búsqueda parcial. ${\displaystyle j_{1}}$ ${\displaystyle j_{2}}$

Optimalidad

El algoritmo de Grover es óptimo hasta factores subconstantes. Es decir, cualquier algoritmo que acceda a la base de datos utilizando únicamente 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 fuera solucionable con log ^c N aplicaciones de U _ω , eso implicaría que NP está contenido en BQP , al transformar problemas en 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 con variables ocultas no locales podría implementar una búsqueda en una base de datos de 100 elementos en un máximo de 100 pasos, lo que es más rápido que los pasos que requiere el algoritmo de Grover. ^[22] ${\displaystyle N}$ ${\displaystyle O({\sqrt[{3}]{N}})}$ ${\displaystyle O({\sqrt {N}})}$

Véase 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 paseos cuánticos

Notas

1. Grover, Lov K. (1 de julio de 1996). "Un algoritmo mecánico cuántico rápido para búsquedas 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.S2CID207198067  .​
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: Cambridge University Press. pp. 276–305. ISBN 978-1-107-00217-3.OCLC 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. 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 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.
6. Ambainis, A. (1 de junio de 2004). "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. "Zoológico de algoritmos cuánticos". quantumalgorithmzoo.org . Consultado el 21 de abril de 2021 .
8. Cerf, Nicolas J.; Grover, Lov K.; Williams, Colin P. (1 de mayo de 2000). "Búsqueda cuántica anidada y problemas NP-difíciles". Álgebra aplicable en ingeniería, comunicación 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 paseo cuántico para distinción de elementos". Revista SIAM de informática . 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 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 clase en Ciencias de la Computación. Vol. 1380. Springer. 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 colisiones de hash: ¿Las computadoras cuánticas harán que SHARCS quede obsoleto?" (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 la partición". Physical Review 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; Boixo, Sergio; Neven, Hartmut (29 de marzo de 2021). "Enfoque más allá de las aceleraciones cuadráticas para obtener una ventaja cuántica con corrección de errores". 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 la clase de ciencia de la información cuántica" (PDF) .
17. Nielsen-Chuang
18. Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998), "Límites estrictos en la búsqueda cuántica", Fortschr. Phys. , 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 sencilla la búsqueda cuántica parcial de 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 . Código Bibliográfico :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 búsquedas en bases de datos , Actas, 28.º Simposio anual de la ACM sobre 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 hacer posible que las máquinas calculen millones de veces más rápido que hoy. 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

Enlaces externos

• Davy Wybiral. «Simulador de circuitos cuánticos». 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». Archivado desde el 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 la computación", 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 ordenadores cuánticos" . Consultado el 30 de abril de 2022. Implementado en /qcl-0.6.4/lib/grover.qcl