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

Проблема скрытого сдвига гласит: дан оракул, который кодирует две функции, и существует n-битная строка, для которой для всех . Найди . ^[1] Многие функции, такие как символ Лежандра и функции Бента , удовлетворяют этим ограничениям. ^[2] С помощью квантового алгоритма , который определен как « » , где это ворота Адамара и является преобразование Фурье от , эта проблема может быть решена за полиномиальное количество запросов к${\ displaystyle O}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle s}$${\ Displaystyle г (х) = е (х + s)}$${\ displaystyle x}$${\ displaystyle s}$${\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 O}$при выполнении экспоненциальных запросов по классическому алгоритму. Разница между проблемой скрытой подгруппы и проблемой скрытого сдвига заключается в том, что первая фокусируется на базовой группе, а вторая - на нижележащем кольце или поле . ^[1]

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