BHT -algoritme - BHT algorithm

I kvanteberegning er Brasard-Hoyer-Tappar-algoritmen eller BHT-algoritmen en kvantealgoritme, der løser kollisionsproblemet . I dette problem får man en n og en r -til -1 -funktion og skal finde to indgange, som f kortes til det samme output. BHT -algoritmen foretager kun forespørgsler til f , som matcher den nedre grænse for i black box -modellen. ${\ displaystyle f: \, \ {1, \ ldots, n \} \ højrepil \ {1, \ ldots, n \}}$${\ displaystyle O (n^{1/3})}$${\ displaystyle \ Omega (n^{1/3})}$

Algoritmen blev opdaget af Gilles Brassard , Peter Hoyer og Alain Tapp i 1997. Den bruger Grovers algoritme , som blev opdaget i det foregående år.

Algoritme

Intuitivt kombinerer algoritmen kvadratrodens hastighed fra fødselsdagsparadokset ved hjælp af (klassisk) tilfældighed med kvadratrodens hastighed fra Grovers (kvante) algoritme.

Først vælges n ^1/3 input til f tilfældigt, og f forespørges på dem alle. Hvis der er en kollision blandt disse input, returnerer vi det kolliderende inputpar. Ellers kortlægges alle disse input til forskellige værdier ved f . Derefter bruges Grovers algoritme til at finde et nyt input til f, der kolliderer. Da der er n input til f og n ^1/3 af disse ville danne en kollision med de allerede forespurgte værdier, kan Grovers algoritme finde en kollision med ekstra forespørgsler til f . ${\ displaystyle O \ venstre ({\ sqrt {\ frac {n} {n^{1/3}}}} \ højre) = O (n^{1/3})}$

Se også

• Element distinktionsproblem

Referencer