Skrytý problém řazení - Hidden shift problem

The Skrytý problém řazení uvádí: Vzhledem k tomu věštec ${ displaystyle O}$ který kóduje dvě funkce ${ displaystyle f}$ a ${ displaystyle g}$, existuje n-bitový řetězec ${ displaystyle s}$ pro který ${ displaystyle g (x) = f (x + s)}$ pro všechny ${ displaystyle x}$. Nalézt ${ displaystyle s}$.^[1] Mnoho funkcí, například Legendární symbol a Ohnuté funkce, uspokojte tato omezení.^[2] S kvantový algoritmus to je definováno jako „${ displaystyle | s rangle = H ^ { otimes n} O_ {f} H ^ { otimes n} O _ { hat {g}} H ^ { otimes n} | 0 ^ {n} rangle}$„kde ${ displaystyle H}$ je Hadamardova brána a ${ displaystyle { hat {g}}}$ je Fourierova transformace z ${ displaystyle g}$, tento problém lze vyřešit v polynomiálním počtu dotazů na ${ displaystyle U}$ při exponenciálních dotazech klasickým algoritmem. Rozdíl mezi Skrytý problém podskupiny a problém skrytého posunu spočívá v tom, že první se zaměřuje na základní skupina zatímco pozdější se zaměřuje na podkladové prsten nebo pole.^[1]

Reference