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 le da n y una función r a 1 y necesita encontrar dos entradas que f se asigne 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 aleatoriamente n ^1/3 entradas para f y se consulta f en todas ellas. Si hay una colisión entre estas entradas, devolvemos el par de entradas en colisión. De lo contrario, todas estas entradas se asignan a valores distintos mediante f . Luego se utiliza el algoritmo de Grover para encontrar una nueva entrada para f que colisione. Dado que hay n entradas para 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 para f . ^[3] ${\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}$

Ver 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) . Teoría de la Computación . 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 alcance pequeño". Teoría de la Computación . 1 (1): 29–36. doi : 10.4086/toc.2005.v001a002 .
3. Brassard, Gilles; Hoyer, Peter; Tapp, Alain (1998), "Algoritmo cuántico para el problema de colisión", en Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.), LATIN '98: Theoretical Informatics, 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