Введение

Очень общая проблема в информатике

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

Заявление о проблеме

Для данной группы G, подгруппы H и множества X, мы говорим, что функция f скрывает подгруппу H, если для всех x, y из X выполняется f(x) = f(y) тогда и только тогда, когда x и y принадлежат одному и тому же коклассу H. Эквивалентно, f постоянна на коклассах H, но различна для разных коклассов H.

Задача скрытой подгруппы: Пусть G – группа, X – конечное множество, а f – функция, скрывающая подгруппу H. Функция f задана через оракул, использующий b битов. Используя информацию, полученную из вычислений f с помощью оракула, определите образующий набор для H.

Частным случаем является ситуация, когда G – группа, а f – групповой гомоморфизм, в этом случае H соответствует ядру f.

Мотивация

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

Алгоритмы

Существует эффективный квантовый алгоритм для решения HSP над конечными абелевыми группами за время, полиномиальное относительно размера группы. Для произвольных групп известно, что задача скрытой подгруппы разрешима, используя полиномиальное число запросов к оракулу. Однако схемы, реализующие это, могут быть экспоненциальными по размеру группы, что делает алгоритм в целом неэффективным; эффективные алгоритмы должны быть полиномиальными как по числу запросов к оракулу, так и по времени работы. Вопрос о существовании такого алгоритма для произвольных групп остаётся открытым. Квантовые алгоритмы полиномиального времени существуют для определенных подклассов групп, таких как полупрямые произведения некоторых абелевых групп.

Алгоритм для абелевых групп

Алгоритм для абелевых групп использует представления, то есть гомоморфизмы из в , общую линейную группу над комплексными числами. Представление называется неприводимым, если его нельзя представить в виде прямого произведения двух или более представлений . Для абелевой группы все неприводимые представления являются характерами, которые представляют собой представления размерности один; для абелевых групп не существует неприводимых представлений большей размерности.

Определение квантовой трансформации Фурье

Квантовое преобразование Фурье может быть определено в терминах аддитивной циклической группы порядка N. Вводя характер, квантовое преобразование Фурье имеет следующее определение: . Кроме того, мы определяем . Любую абелеву группу можно представить как прямую сумму нескольких циклических групп. На квантовом компьютере это представляется как тензорное произведение нескольких регистров размерности соответственно, а общее квантовое преобразование Фурье равно .