Скрытая проблема сдвига

Проблема по информатике

В квантовых вычислениях проблема скрытого сдвига является типом проблемы на основе оракула . ​​Различные версии этой проблемы имеют квантовые алгоритмы, которые могут работать намного быстрее, чем известные неквантовые методы для той же проблемы. В своей общей форме она эквивалентна проблеме скрытой подгруппы для группы диэдра . ^[1] Это крупная открытая проблема, чтобы понять, насколько хорошо квантовые алгоритмы могут выполнять эту задачу, поскольку ее можно применять для взлома криптографии на основе решетки . ^{[2] [3]}

Постановка проблемы

Задача скрытого сдвига гласит: дан оракул , который кодирует две функции и , существует -битная строка , для которой для всех . Найти . ^[4] ${\displaystyle O}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle g(x)=f(x+s)}$ ${\displaystyle x}$ ${\displaystyle s}$

Такие функции, как символ Лежандра и бент-функции , удовлетворяют этим ограничениям. ^[5]

Алгоритмы

С помощью квантового алгоритма , который определяется как , где — вентиль Адамара , а — преобразование Фурье , некоторые примеры этой задачи могут быть решены за полиномиальное число запросов, в то время как для классического алгоритма выполняются экспоненциальные запросы. ${\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. Чайлдс, Эндрю М.; ван Дам, Вим (2007), «Квантовый алгоритм для обобщенной проблемы скрытого сдвига», в Бансал, Нихил; Прухс, Кирк; Стайн, Клиффорд (ред.), Труды восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2007, Новый Орлеан, Луизиана, США, 7-9 января 2007 г. , SIAM, стр. 1225–1232, arXiv : quant-ph/0507190
2. Ломонт, Крис (4 ноября 2004 г.), Проблема скрытой подгруппы — обзор и открытые проблемы , arXiv : quant-ph/0411037
3. Регев, Одед (январь 2004 г.). «Квантовые вычисления и проблемы решеток». Журнал SIAM по вычислениям . 33 (3): 738–760. doi :10.1137/S0097539703440678. ISSN  0097-5397.
4. Дам, Вим ван; Холлгрен, Шон; Ип, Лоуренс (2002). «Квантовые алгоритмы для некоторых проблем скрытого сдвига». Журнал SIAM по вычислениям . 36 (3): 763–778. arXiv : quant-ph/0211140 . doi :10.1137/S009753970343141X. S2CID  11122780.
5. Рёттелер, Мартин (2008). «Квантовые алгоритмы для высоконелинейных булевых функций». Труды двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Том 402. Общество промышленной и прикладной математики . С. 448–457. arXiv : 0811.3208 . doi : 10.1137/1.9781611973075.37. ISBN 978-0-89871-701-3. S2CID  9615826.