Скрытая проблема смены

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

Постановка задачи

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

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

Алгоритмы

С квантовым алгоритмом , который определяется как $|s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle$ , где $H$ это ворота Адамара и ${\hat {g}}$ представляет собой Фурье преобразование $g$ , некоторые реализации этой проблемы могут быть решены за полиномиальное число запросов к $O$ при выполнении экспоненциальных запросов с помощью классического алгоритма.

Ссылки

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

[CvD05-1] Чайлдс, Эндрю М.; ван Дам, Вим (2007), «Квантовый алгоритм для обобщенной задачи скрытого сдвига» , в Бансале, Нихил; Прус, Кирк; Стейн, Клиффорд (ред.), Труды восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2007, Новый Орлеан, Луизиана, США, 7–9 января 2007 г. , SIAM, стр. 1225–1232, arXiv : quant- тел./0507190

[2] Ломонт, Крис (4 ноября 2004 г.), Проблема скрытой подгруппы - обзор и открытые проблемы , arXiv : quant-ph/0411037

[3] Регев, Одед (январь 2004 г.). «Квантовые вычисления и проблемы решетки» . SIAM Journal по вычислительной технике . 33 (3): 738–760. дои : 10.1137/S0097539703440678 . ISSN 0097-5397 .

[WH02-4] Дам, Вим ван; Халлгрен, Шон; ИП, Лоуренс (2002). «Квантовые алгоритмы для некоторых задач скрытого сдвига». SIAM Journal по вычислительной технике . 36 (3): 763–778. arXiv : Quant-ph/0211140 . дои : 10.1137/S009753970343141X . S2CID 11122780 .

[5] Реттелер, Мартин (2008). «Квантовые алгоритмы для сильно нелинейных булевых функций». Материалы двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Том. 402. Общество промышленной и прикладной математики . стр. 448–457. arXiv : 0811.3208 . дои : 10.1137/1.9781611973075.37 . ISBN 978-0-89871-701-3 . S2CID 9615826 .

[1]

[2]

[3]

[4]

[5]