Проблема скрытой подгруппы

Проблема скрытой подгруппы (HSP ) - тема исследования rch в математике и теоретической информатике. Платформа охватывает такие проблемы, как факторинг, дискретный логарифм, изоморфизм графа и задача кратчайшего вектора. Это делает его особенно важным в теории квантовых вычислений, поскольку квантовый алгоритм Шора для факторизации по существу эквивалентен проблеме скрытых подгрупп для конечных абелевых групп, в то время как другие проблемы соответствуют конечным группам. которые не абелевы.

• 1 Описание проблемы
• 2 Мотивация
• 3 Алгоритмы
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

Учитывая группа G, подгруппа H ≤ G и множество X, мы говорим, что функция f: G → X скрывает подгруппу H, если для всех g 1, g 2 ∈ G, f (g 1) = f (g 2) тогда и только тогда, когда g 1 H = g 2 H. Эквивалентно, функция f постоянна на смежных классах группы H, в то время как она различается между разными смежными классами H.

Проблема скрытой подгруппы : пусть G - группа, X - конечное множество., и f: G → X - функция, которая скрывает подгруппу H ≤ G. Функция f задается через oracle, который использует O (log | G | + log | X |) бит. Используя информацию, полученную в результате вычислений f через его оракул, определите порождающий набор для H.

Особым случаем является, когда X - группа, а f - групповой гомоморфизм, и в этом случае H соответствует к ядру f.

Проблема скрытых подгрупп особенно важна в теории квантовых вычислений по следующим причинам.

• Квантовый алгоритм Шора для факторизации и дискретного логарифма (а также некоторых его расширений) основан на способности квантовых компьютеров решать HSP для конечных абелевых групп.
• Существование эффективных квантовых алгоритмов для HSP для некоторых неабелевых групп предполагает наличие эффективных квантовых алгоритмов для решения двух основных проблем: проблемы изоморфизма графов и некоторых кратчайшие векторные задачи (SVP) в решетках. Точнее, эффективный квантовый алгоритм HSP для симметричной группы дал бы квантовый алгоритм для изоморфизма графов. Эффективный квантовый алгоритм для HSP для группы диэдра дал бы квантовый алгоритм для poly (n) уникального SVP.

Существует полиномиальное время квантовый алгоритм решения HSP над конечными абелевыми группами. (В случае проблемы со скрытой подгруппой «алгоритм полиномиального времени» означает алгоритм, время работы которого является полиномом от логарифма размера группы.) Алгоритм Шора применяет частный случай этого квантового алгоритма.

Для произвольных групп известно, что проблема скрытой подгруппы разрешима с использованием полиномиального числа оценок оракула. Этот результат, однако, позволяет квантовому алгоритму работать с экспоненциальным временем в log | G |. Чтобы разработать эффективные алгоритмы для изоморфизма графов и SVP, нужен алгоритм, для которого как количество вычислений оракула, так и время выполнения являются полиномиальными.

Существование такого алгоритма для произвольных групп открыто. Квантовые алгоритмы полиномиального времени существуют для определенных подклассов групп, таких как полупрямые произведения некоторых абелевых групп.

«Стандартный» подход к этой проблеме включает: создание квантового состояния $1\; |\; G\; |\; \sum \; x\; \in \; G\; |\; x⟩\; \otimes \; |\; е\; (х)⟩\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{|\; G\; |\}\}\}\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; G\}\; \{|\; x\; \backslash \; rangle\; \backslash \; otimes\; |\; f\; (x)\; \backslash \; rangle\}\}$, последующее квантовое преобразование Фурье в левый регистр, после которого производится выборка этого регистра. Было показано, что этого подхода недостаточно для решения проблемы скрытых подгрупп для симметричной группы.

• Двойная группа (квантовые вычисления)
• Проблема скрытого сдвига

1. ^Марк Эттингер ; Питер Хойер. «Квантовая наблюдаемая для проблемы изоморфизма графов». arXiv : Quant-ph / 9901029.
2. ^Одед Регев. «Квантовые вычисления и решеточные задачи». arXiv : cs / 0304005.
3. ^Марк Эттингер; Питер Хойер; Эмануэль Книл. «Сложность квантового запроса проблемы скрытой подгруппы полиномиальна». Письма об обработке информации. 91 : 43–48. arXiv : Quant-ph / 0401083. doi : 10.1016 / j.ipl.2004.01.024.
4. ^Шон Холлгрен; Мартин Роттелер; Пранаб Сен. "Ограничения квантовых состояний смежности для изоморфизма графов". arXiv : Quant-ph / 0511148.
5. ^Кристофер Мур, Александр Рассел, Леонард Дж. Шульман. «Симметричная группа не поддается строгой выборке Фурье: Часть I». arXiv : Quant-ph / 0501056. CS1 maint: несколько имен: список авторов (ссылка )

• Ричард Джозса: квантовый факторинг, дискретные логарифмы и проблема скрытой подгруппы
• Крис Ломонт: Проблема скрытой подгруппы - обзор и открытые проблемы
• Проблема скрытой подгруппы на arxiv.org