Проблема скрытых подгрупп ( HSP ) - это тема исследований в области математики и теоретической информатики . Фреймворк охватывает такие проблемы, как разложение на множители , дискретный логарифм , изоморфизм графов и задачу кратчайшего вектора . Это делает его особенно важным в теории квантовых вычислений, потому что квантовый алгоритм Шора для факторизации по существу эквивалентен проблеме скрытых подгрупп для конечных абелевых групп , в то время как другие проблемы соответствуют конечным группам, которые не являются абелевыми.
Формулировка проблемы [ править ]
Для группы G , подгруппы H ≤ G и множества X мы говорим, что функция f : G → X скрывает подгруппу H, если для всех g 1 , g 2 ∈ G , f ( g 1 ) = f ( g 2 ) тогда и только тогда , когда г 1 Н = г 2 H . Эквивалентно функция f постоянна на смежных классахиз H , в то время как она отличается между различными смежных классов H .
Скрытая проблема подгруппы : Пусть G является группой, X конечное множество, а F : G → X функция , которая скрывает подгруппа H ≤ G . Функция f задается оракулом , который использует O (log | G | + log | X |) бит. Используя информацию , полученную из оценок F через его оракул, определяет генераторную установку для H .
Особый случай, когда Х представляет собой группу , и е представляет собой гомоморфизм групп в этом случае H соответствует ядру из F .
Мотивация [ править ]
Проблема скрытых подгрупп особенно важна в теории квантовых вычислений по следующим причинам.
- Квантовый алгоритм Шора для факторизации и дискретного логарифма (а также несколько его расширений) основан на способности квантовых компьютеров решать HSP для конечных абелевых групп .
- Существование эффективных квантовых алгоритмов для HSP для некоторых неабелевых групп подразумевает эффективные квантовые алгоритмы для решения двух основных проблем: проблемы изоморфизма графов и некоторых задач наикратчайших векторов (SVP) в решетках. Точнее, эффективный квантовый алгоритм HSP для симметричной группы дал бы квантовый алгоритм для изоморфизма графов. [1] Эффективный квантовый алгоритм HSP для группы диэдра дал бы квантовый алгоритм для poly ( n ) уникального SVP. [2]
Алгоритмы [ править ]
Существует квантовый алгоритм с полиномиальным временем для решения HSP над конечными абелевыми группами . (В случае проблемы со скрытой подгруппой «алгоритм с полиномиальным временем» означает алгоритм, время работы которого является полиномом от логарифма размера группы.) Алгоритм Шора применяет частный случай этого квантового алгоритма.
Для произвольных групп известно, что проблема скрытых подгрупп разрешима, используя полиномиальное количество оценок оракула. [3] Этот результат, однако, позволяет квантовому алгоритму работать экспоненциально от log | G |, Чтобы разработать эффективные алгоритмы для изоморфизма графов и SVP, нужен алгоритм, для которого как количество вычислений оракула, так и время выполнения являются полиномиальными.
Существование такого алгоритма для произвольных групп открыто. Квантовые алгоритмы полиномиального времени существуют для определенных подклассов групп, таких как полупрямые произведения некоторых абелевых групп .
«Стандартный» подход к этой проблеме включает: создание квантового состояния , последующее квантовое преобразование Фурье в левый регистр, после чего этот регистр выбирается. Было показано, что этого подхода недостаточно для решения проблемы скрытых подгрупп для симметрической группы. [4] [5]
См. Также [ править ]
- Двойная группа (квантовые вычисления)
- Скрытая проблема смещения
Ссылки [ править ]
- ^ Марк Эттингер; Питер Хёйер. «Квантовая наблюдаемая для проблемы изоморфизма графов». arXiv : квант-ph / 9901029 .
- ↑ Одед Регев. «Квантовые вычисления и решеточные задачи». arXiv : cs / 0304005 .
- ^ Марк Эттингер; Питер Хойер; Эмануэль Книл. «Сложность квантового запроса проблемы скрытой подгруппы полиномиальна». Письма об обработке информации . 91 : 43–48. arXiv : квант-ph / 0401083 . DOI : 10.1016 / j.ipl.2004.01.024 .
- ^ Шон Холлгрен; Мартин Роттелер; Пранаб Сен. "Ограничения квантовых состояний смежности для изоморфизма графов". arXiv : квант-ph / 0511148 .
- ^ Кристофер Мур, Александр Рассел, Леонард Дж. Шульман . «Симметричная группа бросает вызов строгой выборке Фурье: Часть I». arXiv : квант-ph / 0501056 .CS1 maint: несколько имен: список авторов ( ссылка )
Внешние ссылки [ править ]
- Ричард Джозса: квантовое разложение, дискретные логарифмы и проблема скрытых подгрупп
- Крис Ломонт: Проблема скрытой подгруппы - обзор и открытые проблемы
- Проблема скрытой подгруппы на arxiv.org
