Algoritmus BHT - BHT algorithm

V kvantové práce na počítači je Brasard Hoyer Tappar-algoritmus nebo BHT algoritmus je kvantový algoritmus , který řeší problém kolize . V tomto problému je jeden dán funkci n a r -to -1 a potřebuje najít dva vstupy, které f mapuje na stejný výstup. Algoritmus BHT vytváří pouze dotazy na f , které odpovídají dolní hranici v modelu černé skříňky . ${\ Displaystyle f: \, \ {1, \ ldots, n \} \ rightarrow \ {1, \ ldots, n \}}$${\ Displaystyle O (n^{1/3})}$${\ Displaystyle \ Omega (n^{1/3})}$

Algoritmus objevil Gilles Brassard , Peter Hoyer a Alain Tapp v roce 1997. Používá Groverův algoritmus , který byl objeven v předchozím roce.

Algoritmus

Algoritmus intuitivně kombinuje zrychlení odmocniny z paradoxu narozenin pomocí (klasické) náhodnosti s zrychlením druhé odmocniny z Groverova (kvantového) algoritmu.

Nejprve se náhodně vybere n ^1/3 vstupů do f a na všechny se zadá dotaz f . Pokud mezi těmito vstupy dojde ke kolizi, pak vrátíme kolidující dvojici vstupů. Jinak se všechny tyto vstupy mapují na odlišné hodnoty pomocí f . Poté se Groverův algoritmus použije k nalezení nového vstupu do f, který koliduje. Protože existuje n vstupů pro f a n ^1/3 z nich by vytvořilo kolizi s již dotazovanými hodnotami, Groverův algoritmus dokáže najít kolizi s dalšími dotazy na f . ${\ Displaystyle O \ left ({\ sqrt {\ frac {n} {n^{1/3}}}} \ right) = O (n^{1/3})}$

Viz také

• Problém odlišnosti prvků

Reference