Algoritmo BHT

En computación cuántica , el algoritmo Brassard–Høyer–Tapp o algoritmo BHT es un algoritmo cuántico que resuelve el problema de colisión . En este problema, se da n y una función r -a-1 y se necesita encontrar dos entradas que f se mapee a la misma salida. El algoritmo BHT solo realiza consultas a f , que coincide con el límite inferior de en el modelo de caja negra . ^{[1] [2]} ${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}$ ${\displaystyle O(n^{1/3})}$ ${\displaystyle \Omega (n^{1/3})}$

El algoritmo fue descubierto por Gilles Brassard , Peter Høyer y Alain Tapp en 1997. ^[3] Utiliza el algoritmo de Grover , que fue descubierto el año anterior.

Algoritmo

Intuitivamente, el algoritmo combina la aceleración de la raíz cuadrada de la paradoja del cumpleaños usando aleatoriedad (clásica) con la aceleración de la raíz cuadrada del algoritmo (cuántico) de Grover.

Primero, se seleccionan n ^1/3 entradas de f al azar y se consulta f en todas ellas. Si hay una colisión entre estas entradas, entonces devolvemos el par de entradas en colisión. De lo contrario, todas estas entradas se asignan a valores distintos por f . Luego se utiliza el algoritmo de Grover para encontrar una nueva entrada de f que colisione. Dado que hay n entradas de f y n ^1/3 de ellas podrían formar una colisión con los valores ya consultados, el algoritmo de Grover puede encontrar una colisión con consultas adicionales a f . ^[3] ${\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}$

Véase también

• Problema de distinción de elementos
• Algoritmo de Grover

Referencias

1. Ambainis, A. (2005). "Grado polinomial y límites inferiores en complejidad cuántica: colisión y distinción de elementos con rango pequeño" (PDF) . Theory of Computing . 1 (1): 37–46. doi : 10.4086/toc.2005.v001a003 .
2. Kutin, S. (2005). "Límite inferior cuántico para el problema de colisión con rango pequeño". Teoría de la computación . 1 (1): 29–36. doi : 10.4086/toc.2005.v001a002 .
3. Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998), "Algoritmo cuántico para el problema de colisión", 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, págs. 163–169, arXiv : quant-ph/9705002 , doi :10.1007/BFb0054319, S2CID  3116149