Проблема скрытого сдвига - Hidden shift problem

В Проблема скрытого сдвига заявляет: Учитывая оракул ${\displaystyle O}$ который кодирует две функции ${\displaystyle f}$ и ${\displaystyle g}$, есть n-битная строка ${\displaystyle s}$ для которого ${\displaystyle g(x)=f(x+s)}$ для всех ${\displaystyle x}$. найти ${\displaystyle s}$.^[1] Многие функции, такие как Символ Лежандра и Бент функции, удовлетворяют этим ограничениям.^[2] С квантовый алгоритм это определяется как "${\displaystyle |s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle }$" где ${\displaystyle H}$ это Ворота Адамара и ${\displaystyle {\hat {g}}}$ это преобразование Фурье из ${\displaystyle g}$, эта проблема может быть решена за полиномиальное количество запросов к ${\displaystyle U}$ при выполнении экспоненциальных запросов классическим алгоритмом. Разница между Проблема скрытой подгруппы а проблема скрытого сдвига заключается в том, что первая фокусируется на лежащих в основе группа в то время как последний фокусируется на основном кольцо или поле.^[1]

использованная литература

1. Дам, Вим ван; Халлгрен, Шон; ИП, Лоуренс (2002). «Квантовые алгоритмы для некоторых задач скрытого сдвига». Общество промышленной и прикладной математики. 36: 763–778. arXiv:Quant-ph / 0211140. Дои:10.1137 / S009753970343141X.
2. Рёттелер, Мартин (2008). «Квантовые алгоритмы для сильно нелинейных булевых функций». Общество промышленной и прикладной математики. 402: 448–457. arXiv:0811.3208. Дои:10.1137/1.9781611973075.37.