Algoritmo BHT

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

El algoritmo fue descubierto por Gilles Brassard , Peter Hoyer 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 la aleatoriedad (clásica) con la aceleración de la raíz cuadrada del algoritmo (cuántico) de Grover.

Primero, n ^1/3 entradas af se seleccionan al azar y se consulta f en todas ellas. Si hay una colisión entre estas entradas, devolvemos el par de entradas que colisionan. De lo contrario, todas estas entradas se asignan a valores distintos mediante f . Luego, el algoritmo de Grover se usa para encontrar una nueva entrada af que colisiona. Dado que solo hay n ^{2/3 de} tales entradas af , el algoritmo de Grover puede encontrar una (si existe) haciendo solo ${\ Displaystyle O ({\ sqrt {n ^ {2/3}}}) = O (n ^ {1/3})}$ consultas a f .

Ver también

Problema de distinción de elementos

Referencias

^ Ambainis, A. (2005). "Grado de polinomio 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 .
^ Kutin, S. (2005). "Quantum Lower Bound 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 .
^ Brassard, Gilles; Hoyer, Peter; Tapp, Alain (1997). "Algoritmo cuántico para el problema de colisión" . Notas de la clase en Ciencias de la Computación : 163–169. arXiv : quant-ph / 9705002 . doi : 10.1007 / BFb0054319 .

[1] Ambainis, A. (2005). "Grado de polinomio 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). "Quantum Lower Bound 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; Hoyer, Peter; Tapp, Alain (1997). "Algoritmo cuántico para el problema de colisión" . Notas de la clase en Ciencias de la Computación : 163–169. arXiv : quant-ph / 9705002 . doi : 10.1007 / BFb0054319 .

[1]